Linear Function

Linear Function

「一次函數」。多項式函數,變數不相乘,頂多一次方。

f(x, y, z) = 1 x + 2 y - 5 z - 5

數字的一次方呈直線line、二次方呈正方形quadrate、三次方呈正方體cube。因此一次取名linear、二次取名quadratic、三次取名cubic。

Linear Function

「線性函數」。僅由變數的加減、變數的倍率所構成的函數。

是線性函數的例子:
f(x, y, z) = 1 x + 2 y - 5 z
f(x, y, z) = 1 x + (2 y - 5 z) ⋅ 2   乘開就是了

不是線性函數的例子:
f(x, y) = xy        不包含變數乘法
f(x) = x²           不包含變數乘法
f(x, y) = x / y     不包含變數除法
f(x) = sqrt(x)      不包含變數的其他運算
f(x) = x + 2        不包含常數項

不是線性函數,但是硬是套用線性函數的例子:
f(x) = 1 x + 2 x² - 5 x³     把 x² 與 x³ 重新看作是變數 y 和 z
f(x) = x + 2                 2 後面乘上一個變數 y,讓 y 永遠是 1

線性代數開始流行之後,linear新添了其他意義。當數學家說linear,可能是一次,也可能是線性。

線性函數不等於一次函數,線性函數沒有常數項。取名線性是因為古人沒有考慮清楚。理想名稱應是「加倍函數」。

Matrix

Matrix

「矩陣」。大家應該學過吧?

⎡ 1 0 9 5 ⎤
⎢ 2 0 8 4 ⎥
⎣ 3 7 7 6 ⎦

矩陣表示成數學符號。

    ⎡ A₁₁ A₁₂ A₁₃ A₁₄ ⎤
A = ⎢ A₂₁ A₂₂ A₂₃ A₂₄ ⎥
    ⎣ A₃₁ A₃₂ A₃₃ A₃₄ ⎦

元素element、橫條row、直條column。

元素索引值,先數橫條、再數直條。

Linear Function改寫成矩陣

好久好久以前,矩陣主要用來存放大量數字。然而自從線性代數開始流行之後,矩陣的地位完全改變了──矩陣其實是線性函數。

線性函數,改寫成矩陣。

                                                      ⎡ x₁ ⎤
f(x,y,z) = 1 x + 2 y - 5 z  --->  [ y₁ ] = [ 1 2 -5 ] ⎢ x₂ ⎥
                                                      ⎣ x₃ ⎦
輸入變數們改名成 x₁ x₂ x₃
輸入變數們拼在一起,成為一個向量 x
輸出變數們改名成 y₁
輸出變數們拼在一起,成為一個向量 y

線性函數組,改寫成矩陣。

⎧ f₁(x,y,z) = 1 x + 2 y - 5 z        ⎡ y₁ ⎤   ⎡ 1 2 -5 ⎤ ⎡ x₁ ⎤
⎨ f₂(x,y,z) = 2 x + 4 y + 6 z  --->  ⎢ y₂ ⎥ = ⎢ 2 4  6 ⎥ ⎢ x₂ ⎥
⎩ f₃(x,y,z) = 3 x + 1 y + 7 z        ⎣ y₃ ⎦   ⎣ 3 1  7 ⎦ ⎣ x₃ ⎦

輸入變數、輸出變數,排成向量,而不是排成矩陣。如此一來,只要知道了矩陣,就能完全確定輸入變數、輸出變數各有多少個。

⎡ y₁ y₃ ⎤   ⎡ 1 2 -5 ⎤ ⎡ x₁ x₄ ⎤
⎣ y₂ y₄ ⎦ = ⎣ 2 4  6 ⎦ ⎢ x₂ x₅ ⎥     輸出變數、輸入變數,排成矩陣
                       ⎣ x₃ x₆ ⎦
    y     =     A          x    
    y     =     f      (   x   )
⎡ y₁ ⎤   ⎡ 1 2 -5 ⎤ ⎡ x₁ ⎤
⎣ y₂ ⎦ = ⎣ 2 4  6 ⎦ ⎢ x₂ ⎥     輸出變數、輸入變數,排成向量
                    ⎣ x₃ ⎦
  y    =     A        x
  y    =     f      ( x  )

一個矩陣,代表一個線性函數。

f(x)  --->  Ax
f     --->  A      省略x的部分

Linear Function的排版方式

線性函數的排版方式,源自於一次方程組的排版方式。

遙想當年,古人為了節省紙張空間,嘗試用矩陣表示一次方程組,並且抽出變數排成直條。

⎧ 1 x + 2 y - 5 z = 5        ⎡ 1 2 -5 ⎤ ⎡ x ⎤   ⎡ 5 ⎤
⎨ 2 x + 4 y - 6 z = 1  --->  ⎢ 2 4  6 ⎥ ⎢ y ⎥ = ⎢ 1 ⎥
⎩ 3 x + 1 y - 7 z = 4        ⎣ 3 1  7 ⎦ ⎣ z ⎦   ⎣ 4 ⎦

於是線性函數的排版方式,就模仿了這個排版方式。

因為這個排版方式,讓高斯消去法,變成橫條相消。

因為這個排版方式,讓向量變成直條。

因為這個排版方式,讓線性函數,變成橫條配直條。

因為這個排版方式,讓矩陣乘法,變成橫條配直條。

因為這個排版方式,讓矩陣連乘,是從式子的右端到左端。

因為這個排版方式,有些線性代數課本劈頭就介紹一次方程組,講解一堆求解技巧。然而一次方程組跟線性函數其實是兩碼子事,不適合參雜在一起。

Matrix資料結構

二維陣列。

UVa 10855 11360 11149

Matrix運算

矩陣運算本質上是函數運算,又額外增加了許多細項。

求值  evaluation   (乘法multiplication)
求解  resolution   (除法division)
加法  addition
減法  subtraction
倍率  scaling
複合  composition  (乘法multiplication)
分解  decomposition
疊代  iteration    (次方exponentiation)
反函數 inverse
轉置  transpose
秩   rank
行列式 determinant
跡   trace
積和式 permanent

求值(乘法)

y = f(x)  --->  y = Ax

矩陣取橫條,向量取直條,求點積,得到一個元素。取盡各種可能性,得到整個向量。

求解(除法)

f⁻¹(y) = x  --->  A⁻¹y = x

求值的反向操作。

演算法是「高斯消去法」,時間複雜度O(N³)。

加法、減法

(f+g)(x)  --->  (A+B)x
 f+g      --->   A+B       省略x的部分

兩個函數相加。兩個矩陣的對應位置相加。矩陣必須一樣大。

倍率

(k⋅f)(x)  --->  (k⋅A)x
 k⋅f      --->   k⋅A        省略x的部分

函數乘上倍率。矩陣元素一齊乘上相同倍率。

複合(乘法)

(f∘g)(x)  --->  (AB)x
 f∘g      --->   AB       省略x的部分

左矩陣取橫條、右矩陣取直條,求點積,得到一個元素;取盡各種可能性,得到整個矩陣。

大家不稱作複合,而是稱作乘法。啊就古人取名的時候沒想清楚,稱作乘法,成為歷史共業。

那麼有沒有真正的乘法呢?由於線性函數不包括變數的乘除,所以不能有矩陣乘法、矩陣除法。真正的矩陣乘法,必須跟多項式乘法有著相同的結果才行。

複合(乘法)(Strassen's Algorithm)

首先把兩個矩陣改成兩個一樣大的方陣。把矩陣改成稍大的方陣,長寬是2的次方,多出來的元素全部補零。

原理是Divide-and-Conquer Method,欲相乘的兩個方陣,各自切割成四塊小方陣,然後利用小方陣的乘積,兜出大方陣的乘積。

僅是單純的拆成小方陣相乘,仍然需要8次乘法、4次加法,列出遞迴公式,運用Master Theorem,時間複雜度O(Nlog₂8) = O(N³)。時間複雜度主要取決於乘法次數,至於加法次數不是主要因素。

經過一些詭異的調整方法,變成需要7次乘法、許多次加法減法。時間複雜度降為O(Nlog₂7) = O(N2.81)。

複合(乘法)(Alman–Williams Algorithm)

矩陣乘法的速度究竟可以到達多快?這是懸案。

時間複雜度的上界目前是O(N2.3728596)。

時間複雜度的下界顯然是Ω(N²)。兩個方陣一共有2N²個元素,這些元素不得不處理一次。目前尚未有人找出更高的下界。

分解

h(x) = (f∘g)(x)  --->  Cx = (AB)x
h    =  f∘g      --->  C  =  AB       省略x的部分

複合的反向操作。

複合:很多個矩陣連乘,併成一個矩陣。

分解:一個矩陣,拆成很多個矩陣連乘。

疊代(次方)

f(f(f(f(f(f(f(f(x))))))))  --->  Aⁿx
\__________  __________/
           \/
           n次

f∘f∘f∘f∘f∘f∘f∘f   --->  Aⁿ     省略x的部分
\_____  _____/
      \/
      n次

Divide-and-Conquer Method。如同整數次方的演算法。

大家不稱作疊代,而是稱作次方。啊就歷史共業。

Basis

Linear Function的第一種觀點

數學家發明了兩種看待線性函數的觀點:一種是矩陣切成直條、另一種是矩陣切成橫條。先談直條吧!

⎡ y₁ ⎤   ⎡ 1 2 -5 ⎤ ⎡ x₁ ⎤      ⎡ 1 ⎤      ⎡ 2 ⎤      ⎡ -5 ⎤
⎢ y₂ ⎥ = ⎢ 2 4  6 ⎥ ⎢ x₂ ⎥ = x₁ ⎢ 2 ⎥ + x₂ ⎢ 4 ⎥ + x₃ ⎢  6 ⎥
⎣ y₃ ⎦   ⎣ 3 1  7 ⎦ ⎣ x₃ ⎦      ⎣ 3 ⎦      ⎣ 1 ⎦      ⎣  7 ⎦

外觀看起來,彷彿是向量乘上倍率、再相加。我想大家已經相當熟悉向量的作圖方式了。

以這些向量當作座標軸,畫出座標格線。「向量乘上倍率、再相加」就變成了數格子。

線性函數可以看成:給定座標軸、座標值,然後求向量。座標軸是矩陣裡面的各個向量,座標值是輸入向量。

有時候座標軸剛好是零向量、共線、共面、共空間、……,無法畫出座標格線。儘管如此,線性函數仍然可以朦朧地看成:給定座標軸、座標值,然後求向量。

這樣的座標軸,稱作「基底basis」。

Inverse

「反函數」。一般是入境隨俗翻譯為「反矩陣」。演算法是「高斯喬登消去法」。

⎡ 1 2 -5 ⎤   inverse   ⎡  22/80 -19/80  32/80 ⎤
⎢ 2 4  6 ⎥  -------->  ⎢   4/80  22/80 -16/80 ⎥
⎣ 3 1  7 ⎦  <--------  ⎣ -10/80   5/80      0 ⎦ 
             inverse
    A                             A⁻¹

採用第一種觀點,反矩陣可以看成是:以原本矩陣的直條當作座標軸,給定座標軸、向量,求得座標值。

y = A⁻¹x

Inverse的存在條件

原函數擁有反函數的條件:

一、輸入與輸出一樣多。

二、不同輸入得到不同輸出。

原函數是如此,反函數亦是如此。

原矩陣擁有反矩陣的條件:

一、輸入變數與輸出變數一樣多。矩陣是方陣。

二、座標軸沒有零向量、共線、共面、共空間、……,得以順利畫出座標格線,讓不同座標值得到不同向量。

簡單來說:一個座標軸產生一個維度,必須剛好產生所有維度。

原矩陣是如此,反矩陣亦是如此。

Linear Function的第二種觀點

⎡ y₁ ⎤   ⎡ 1 2 -5 ⎤ ⎡ x₁ ⎤   ⎡ (1 2 -5) ∙ (x₁ x₂ x₃) ⎤
⎢ y₂ ⎥ = ⎢ 2 4  6 ⎥ ⎢ x₂ ⎥ = ⎢ (2 4  6) ∙ (x₁ x₂ x₃) ⎥
⎣ y₃ ⎦   ⎣ 3 1  7 ⎦ ⎣ x₃ ⎦   ⎣ (3 1  7) ∙ (x₁ x₂ x₃) ⎦

線性函數也可以看成:以橫條當作座標軸,輸入向量與各座標軸的點積。換句話說,輸入向量在各座標軸上面的投影量(另乘上座標軸長度)。

因為已經規定直條是座標軸,所以橫條當作座標軸挺彆扭。數學家就想到,把矩陣翻轉一下、繼續討論。

Transpose

「轉置矩陣」。以左上右下對角線為對稱軸,所有矩陣元素對稱地調換位置。也可以想成是橫的變直的。也可以想成是直的變橫的。

⎡ 1 2 -5 ⎤   transpose   ⎡  1 2 3 ⎤
⎢ 2 4  6 ⎥  ---------->  ⎢  2 4 1 ⎥
⎣ 3 1  7 ⎦  <----------  ⎣ -5 6 7 ⎦
             transpose
    A                         Aᵀ
⎡ 1 0 9 5 ⎤   transpose   ⎡ 1 2 3 ⎤
⎢ 2 0 8 4 ⎥  ---------->  ⎢ 0 0 7 ⎥
⎣ 3 7 7 6 ⎦  <----------  ⎢ 9 8 7 ⎥
              transpose   ⎣ 5 4 6 ⎦
     A                        Aᵀ

採用第二種觀點,轉置矩陣可以看成:以原本矩陣的直條當作座標軸,輸入向量分別投影到各座標軸,求得投影量(另乘上座標軸長度)。

y = Aᵀx

UVa 10895 11349

Transpose與Inverse的差別

轉置矩陣跟反矩陣有些相似,主要有三個地方不同:

一、轉置矩陣是垂直投影;反矩陣是沿著座標軸平行投影。

二、轉置矩陣的輸出,受到座標軸的長度影響,長度越長則輸出數值越大;反矩陣剛好顛倒,是越小。

三、轉置矩陣可以是一對一函數,也可以是收束的函數;反矩陣只能是一對一函數。

當轉置矩陣和反矩陣一樣的時候,座標軸必須互相垂直、座標軸的長度都是一、矩陣是方陣,就是所謂的(實數版本)正規正交矩陣orthonormal matrix、(複數版本)么正矩陣unitary matrix。此時轉置矩陣和反矩陣都是垂直投影、都是在求座標值。

Transformation

Transformation

本站文章「Transformation」已經詳細介紹過幾何變換。本篇文章從線性函數的觀點,再度介紹一次。順便藉此機會,讓讀者更加瞭解線性函數的功效。

這些二維平面上的動作,其實都是線性函數,每種動作都有對應的矩陣。想要實施動作,那就乘上矩陣(函數求值)。想要還原動作,那就乘上反矩陣(反函數求值)。想要實施一連串的動作,那就乘上一連串的矩陣。

new        step 3             step 2  step 1  original
coordinate rotate             scale   shear   coordinate
⎡ x' ⎤  =  ⎡ cos45° -sin45° ⎤ ⎡ 2 0 ⎤ ⎡ 1 1 ⎤ ⎡ x ⎤
⎣ y' ⎦     ⎣ sin45°  cos45° ⎦ ⎣ 0 3 ⎦ ⎣ 0 1 ⎦ ⎣ y ⎦

甚至可以預先把一連串的矩陣相乘起來(函數複合),變成一個矩陣。一個矩陣代表一連串的動作,相當方便!

new        step 1 & 2 & 3              original
coordinate shear, scale, rotate        coordinate
⎡ x' ⎤  =  ⎡ 2cos45° 2cos45°-3sin45° ⎤ ⎡ x ⎤
⎣ y' ⎦     ⎣ 2sin45° 2sin45°+3cos45° ⎦ ⎣ y ⎦

以座標軸的觀點來思考

線性函數常常以座標軸的觀點來思考。以座標軸為主角,縮放、旋轉、投影這些動作都是在改動座標軸。

先從最基礎的紋風不動開始介紹起吧!以原點為中心,座標軸方向設定為X軸正向和Y軸正向,座標軸長度是1。

⎡ 1 0 ⎤
⎣ 0 1 ⎦

Scale

「縮放」。以原點為中心,縮放座標軸。X軸、Y軸可以分別縮放不同倍率。

⎡ sx   0 ⎤
⎣  0  sy ⎦

Shear(Skew)

「歪斜」。以原點為中心,改變其中一個座標軸。

⎡  1 0 ⎤ upward / downward
⎣ ty 1 ⎦

⎡ 1 tx ⎤ rightward / leftward
⎣ 0  1 ⎦

另一種方式是設定歪斜角度。

⎡    1 0 ⎤ upward / downward
⎣ tanθ 1 ⎦

⎡ 1 tanθ ⎤ rightward / leftward
⎣ 0    1 ⎦

Rotate

「旋轉」。以原點為中心,旋轉座標軸。

⎡ cosθ -sinθ ⎤
⎣ sinθ  cosθ ⎦

Project

「投影」。一個座標軸當作投影線,另一個座標軸變成零向量。

⎡ 1 0 ⎤
⎣ 0 0 ⎦

Reflect

「鏡射」。一個座標軸當作對稱線,另一個座標軸顛倒方向。

⎡ 1  0 ⎤
⎣ 0 -1 ⎦

Permutation

「排列」。標準座標軸更動次序。輸出向量的座標更動次序。

⎡ 0 1 ⎤
⎣ 1 0 ⎦

Shift

「移位」。標準座標軸次序加一。輸出向量的座標次序減一。

⎡ 0 1 ⎤
⎣ 0 0 ⎦

Translate

「位移」不是線性函數!不過「位移」可以套用線性函數:座標增加一個維度,數值固定為1;矩陣增加一個維度,將位移量填在新維度。

以幾何的觀點來看,就是把二維位移變成三維歪斜:將原本的xy平面固定放在z=1的高度,沿著平面滑動。

⎡ x' ⎤   ⎡ 1 0 tx ⎤ ⎡ x ⎤
⎢ y' ⎥ = ⎢ 0 1 ty ⎥ ⎢ y ⎥
⎣ 1  ⎦   ⎣ 0 0 1  ⎦ ⎣ 1 ⎦

前面介紹的矩陣,通通跟著改成三維,如此一來位移矩陣就能和其他矩陣相乘了。增加一個維度,以便讓位移融入大團體──這個手法稱作「齊次座標Homogeneous Coordinates」。

線性函數、位移,合稱「仿射函數Affine Function」。

UVa 12303

Orthonormal Matrix

Identity Matrix

「恆等矩陣」。第一座標軸的第一個值是1,其餘是0;第二座標軸的第二個值是1,其餘是0;以此類推。標準的座標軸。

所有向量經過恆等矩陣變換之後,紋風不動,完全不變。

註:identity是指相同個體。

逆向變換(反矩陣)顯然還是恆等矩陣,不必另外計算。

Orthonormal Matrix / Unitary Matrix

「正規正交矩陣」是實數版本。「么正矩陣」是複數版本。

座標軸長度皆為1、夾角互相垂直。

註:normal正規、ortho-正交、unitary么正。normal是指長度為1,ortho-是指夾角垂直,unitary是指基本單元。

想要判斷一個矩陣是不是正規正交矩陣,可以利用點積:長度為1,自己與自己的點積為1;夾角垂直,自己與別人的點積為0。

所有向量們經過正規正交矩陣變換之後,長度不變、夾角不變。即是形狀不變。相當好用!

逆向變換(反矩陣)恰好是轉置,不必另外以高斯消去法計算。

舉例來說,恆等矩陣、旋轉矩陣、鏡射矩陣是正規正交矩陣,縮放矩陣、歪斜矩陣、投影矩陣不是正規正交矩陣(除非恰好等於恆等矩陣)。

正規正交矩陣的功效是旋轉暨鏡射。

Rank

座標軸所構成的超平行體的維度。消除導致零向量、共線、共面、共空間、……的座標軸,剩下的座標軸數量就是維度。

嘗試將各個座標軸乘上倍率、互相加減抵消,就能消除多餘的座標軸了。通常會有許多種消除方式。

Rank相關定理

rank(AB) ≤ min(rank(A), rank(B))。矩陣複合,消失的維度回不來了。

rank(A⁻¹) = N。反矩陣的條件就是座標軸必須剛好產生所有維度,維度顯然是N。如果有反矩陣的話。

rank(Aᵀ) = rank(A)。矩陣轉置,維度一樣。

Determinant

座標軸所構成的超平行體的容積。一維是長度、二維是平行四邊形的面積、三維是平行六面體的體積。

一、消滅分量,令座標軸互相垂直,此時所有座標軸的長度相乘,就是容積。簡單來說,這就是中學數學「底乘以高」的概念。

二、座標軸所構成的維度、即超平行體的維度,必須跟空間維度一致,否則容積被定義為0。這跟反矩陣的條件是一樣的。

當座標軸有零向量、共線、共面、共空間、……,容積是0。當座標軸數量大於或小於空間維度,容積是0。只有N×N方陣、且rank為N,才有討論意義。

因此inverse、rank、determinant總是被相提並論:有反矩陣,維度是N,容積不是0;無反矩陣,維度小於N,容積是0。

三、容積有正負號。當其中一個座標軸顛倒方向,容積將變號。當其中兩個座標軸交換次序,容積將變號。

舉例來說,恆等矩陣的容積是1。正規正交矩陣可能是1、可能是-1。旋轉矩陣是1。鏡射矩陣是-1。縮放矩陣、歪斜矩陣是左上右下對角線元素的乘積。投影矩陣是0。

Determinant相關定理

det(AB) = det(A) det(B)。矩陣複合,容積相乘。

det(A⁻¹) = 1/det(A)。反矩陣的容積是倒數。如果有反矩陣的話。

det(Aᵀ) = det(A)。矩陣轉置之後,容積不變!幾何意義:依序取出每個向量的X座標組成一個新向量、依序取出每個向量的Y座標組成一個新向量、……,所形成的容積仍然相同!我想不出直觀的證明方式,也想不出如何應用。

求得Rank與Determinant

消滅分量,令座標軸互相垂直,以求得容積與維度。例如稍後提到的「QR分解」可以求得容積與維度。

另外,轉置矩陣的容積與維度不變,於是原本矩陣的橫條,亦得視作座標軸。這使得「高斯消去法」也可以求得容積與維度。

另外,由於高斯消去法的關係,容積、維度、反矩陣經常被聯繫到一次方程組的唯一解、多解、無解判定。

QR Decomposition

「QR分解」。把一個矩陣的座標軸扳成互相垂直的單位向量,讓座標軸長得正、長得帥。

A = QR。Q是正規正交矩陣(新座標軸),R是上三角矩陣(新座標值)。

⎡  |  |  | ⎤   ⎡  |  |  | ⎤ ⎡ R₁₁ R₁₂ R₁₃ ⎤
⎢ v₁ v₂ v₃ ⎥ = ⎢ q₁ q₂ q₃ ⎥ ⎢  0  R₂₂ R₂₃ ⎥
⎣  |  |  | ⎦   ⎣  |  |  | ⎦ ⎣  0   0  R₃₃ ⎦
      A              Q             R

A切成直條、R切成直條,依序對應。

v₁ = R₁₁q₁                     (1st column of R)
v₂ = R₁₂q₁ + R₂₂q₂             (2nd column of R)
v₃ = R₁₃q₁ + R₂₃q₂ + R₃₃q₃     (3rd column of R)
where Rᵢⱼ = vⱼ∙qᵢ

正規正交矩陣,照理來說符號是O。因為O是零矩陣,所以改用看起來差不多的Q。

上三角矩陣,照理來說符號是T或U。不知為何是R。

演算法(Gram–Schmidt Orthonormalization)

一、從中隨便挑出一個向量(通常是第一個,以便讓R成為上三角矩陣),
  作為第一座標軸,向量長度調整成1。
二、所有剩餘向量們,各自減掉在第一座標軸上的分量,徹底消滅該維度。
  所有剩餘向量們,現在顯然都垂直於第一座標軸。
三、所有剩餘向量們,遞迴處理下去。

藉由投影、相減、縮放,逐步調整每個向量,直到變成正規正交矩陣。

時間複雜度O(N³)。

演算法(Householder Reflection)

「鏡射矩陣」。設置一個過原點平面,作為鏡面;平面法向量,作為鏡射方向。

R = I - vvᵀ   where ‖v‖ = 1     Householder matrix

鏡射矩陣有一個特殊用處:把一個向量鏡射到標準座標軸(鏡子位於角平分線),該向量變成只有一個元素有值(即是向量長度),其餘元素都是零。

鏡射矩陣恰是正規正交矩陣。不斷套用鏡射矩陣,讓向量底部元素歸零,直到變成上三角矩陣。優點是向量的長度變化比較少、誤差比較小。

時間複雜度O(N³)。

演算法(Givens Rotation)

「軸面旋轉矩陣」。標準座標軸當中,挑選其中兩個軸,在其平面上旋轉。旋轉矩陣覆蓋在恆等矩陣上面。

    ⎡ 1  0  0   0  0   0   0 ⎤
    ⎢ 0  1  0   0  0   0   0 ⎥
    ⎢ 0  0 cosθ 0  0 -sinθ 0 ⎥
G = ⎢ 0  0  0   1  0   0   0 ⎥     Givens matrix
    ⎢ 0  0  0   0  1   0   0 ⎥
    ⎢ 0  0 sinθ 0  0  cosθ 0 ⎥
    ⎣ 0  0  0   0  0   0   1 ⎦

軸面旋轉矩陣有一個特殊用處:把一個向量旋轉到標準座標軸,該向量變成一個維度有值(即是向量長度),另一個維度為零。

軸面旋轉矩陣恰是正規正交矩陣。不斷套用軸面旋轉矩陣,讓左下角元素歸零,直到變成上三角矩陣。優點是容易設計平行演算法。

時間複雜度O(N³)。

Eigenbasis (Eigenvalue)

Eigenvector與Eigenvalue

數學式子Ax = λx,λ是特徵值,x是特徵向量。

當輸入恰是特徵向量,則輸出恰是特徵向量的λ倍。

⎡  4 -1  0 ⎤ ⎡ 1 ⎤     ⎡ 1 ⎤
⎢  0  5 -2 ⎥ ⎢ 1 ⎥ = 3 ⎢ 1 ⎥
⎣ -3  9 -3 ⎦ ⎣ 1 ⎦     ⎣ 1 ⎦
      A        x     λ   x

特徵向量長度無所謂,可以自由縮放,可以縮放為1。

特徵向量方位無所謂,可以自由顛倒,可以乘上倍率-1。

⎡  4 -1  0 ⎤ ⎡ 1/√3 ⎤     ⎡ 1/√3 ⎤
⎢  0  5 -2 ⎥ ⎢ 1/√3 ⎥ = 3 ⎢ 1/√3 ⎥
⎣ -3  9 -3 ⎦ ⎣ 1/√3 ⎦     ⎣ 1/√3 ⎦
      A          x      λ    x

長寬相同的方陣,才有特徵向量與特徵值。

長寬不同的矩陣,沒有特徵向量與特徵值。

⎡  4 -1  0 ⎤ ⎡ 1 ⎤     ⎡ 1 ⎤
⎢  0  5 -2 ⎥ ⎢ 1 ⎥ = 3 ⎢ 1 ⎥   ✘
⎢ -3  9 -3 ⎥ ⎣ 1 ⎦     ⎢ 1 ⎥
⎣  0  0  0 ⎦           ⎣ 0 ⎦

特徵向量通常有無限多個。消除導致零向量、共線、共面、共空間、 …… 的特徵向量,特徵向量最少0種、最多N種。

這樣的特徵向量,稱作「特徵基底eigenbasis」。

特徵值跟特徵向量一一對應、數量相符。然而數學家強制定義特徵值必須剛好N個。

此處略過細節,詳情請見本站文件「Eigenbasis」。

Eigenvector與Eigenvalue相關定理

rank(A) = num≠0 {eigval(A)}。非零特徵值數量等於維度。

det(A) = prod {eigval(A)}。所有特徵值相乘等於容積。

A⁻¹ ⇔ prod {eigval(A)} ≠ 0。特徵值皆不為零,則有反矩陣。

Eigenvector與Eigenvalue相關定理

eig(AB) ≠ eig(A) ≠ eig(B)。矩陣複合,特徵向量與特徵值都會改變。除非遇到特例。

eigvec(Aⁿ) = eigvec(A)。eigval(Aⁿ) = eigval(A)ⁿ。變換n次,特徵向量一樣,特徵值乘n次。

eigvec(A⁻¹) = eigvec(A)。eigval(A⁻¹) = 1/eigval(A)。反矩陣,伸與縮顛倒,特徵向量一樣,特徵值變倒數。

eigvec(Aᵀ) ≠ eigvec(A)。eigval(Aᵀ) = eigval(A)。轉置矩陣,特徵向量改變,但是特徵值一樣。

Eigenvector與Eigenvalue演算法

詳情請見本站文件「Eigenbasis」。

演算法是不動點遞推法,分為兩大類型。一、向量的變換:向量反覆代入矩陣。二、矩陣的變換:QR分解三個演算法的改良版本。時間複雜度O(N²(N+T)),T是遞推次數。

當特徵向量不足N種,可能無法順利找到所有特徵向量。

特殊矩陣的Eigenvector與Eigenvalue

一般矩陣:特徵向量是複數、最多N種。特徵值是複數、強制N個。

對稱矩陣:特徵向量是實數、正規正交、恰好N種。特徵值是實數、恰好N個。大家喜歡對稱矩陣,順利找到N種特徵向量。

對稱半正定矩陣:特徵向量是實數、正規正交、恰好N種。特徵值是非負實數、恰好N個。特徵向量等於奇異向量。特徵值等於奇異值!可以改用奇異向量與奇異值的演算法。

現實世界經常使用對稱矩陣、對稱半正定矩陣,例如物理學的質量矩陣、統計學的共變異數矩陣。

Eigendecomposition

「特徵分解」。A = EΛE⁻¹。特徵向量們E、特徵值們Λ。

特徵向量與特徵值,雙雙對對,依序排列。

⎡  4 -1  0 ⎤   ⎡ 1 1 1 ⎤ ⎡ 3 0 0 ⎤ ⎡ 1 1 1 ⎤⁻¹
⎢  0  5 -2 ⎥ = ⎢ 1 2 3 ⎥ ⎢ 0 2 0 ⎥ ⎢ 1 2 3 ⎥
⎣ -3  9 -3 ⎦   ⎣ 1 3 6 ⎦ ⎣ 0 0 1 ⎦ ⎣ 1 3 6 ⎦
      A            E         Λ         E⁻¹

⎡ A₁₁ A₁₂ A₁₃ ⎤   ⎡ |  |  |  ⎤ ⎡ λ₁ 0  0  ⎤ ⎡ |  |  |  ⎤⁻¹
⎢ A₂₁ A₂₂ A₂₃ ⎥ = ⎢ x₁ x₂ x₃ ⎥ ⎢ 0  λ₂ 0  ⎥ ⎢ x₁ x₂ x₃ ⎥
⎣ A₃₁ A₃₂ A₃₃ ⎦   ⎣ |  |  |  ⎦ ⎣ 0  0  λ₃ ⎦ ⎣ |  |  |  ⎦
      A                E            Λ            E⁻¹

特徵向量次序無所謂,可以自由對調(連同特徵值),可以按照特徵值大小排序。

⎡  4 -1  0 ⎤   ⎡ 1 1 1 ⎤ ⎡ 2 0 0 ⎤ ⎡ 1 1 1 ⎤⁻¹
⎢  0  5 -2 ⎥ = ⎢ 2 1 3 ⎥ ⎢ 0 3 0 ⎥ ⎢ 2 1 3 ⎥
⎣ -3  9 -3 ⎦   ⎣ 3 1 6 ⎦ ⎣ 0 0 1 ⎦ ⎣ 3 1 6 ⎦
      A            E         Λ         E⁻¹

⎡ A₁₁ A₁₂ A₁₃ ⎤   ⎡ |  |  |  ⎤ ⎡ λ₂ 0  0  ⎤ ⎡ |  |  |  ⎤⁻¹
⎢ A₂₁ A₂₂ A₂₃ ⎥ = ⎢ x₂ x₁ x₃ ⎥ ⎢ 0  λ₁ 0  ⎥ ⎢ x₂ x₁ x₃ ⎥
⎣ A₃₁ A₃₂ A₃₃ ⎦   ⎣ |  |  |  ⎦ ⎣ 0  0  λ₃ ⎦ ⎣ |  |  |  ⎦
      A                E            Λ            E⁻¹

另外,對稱矩陣A = Aᵀ,特徵向量將正規正交E⁻¹ = Eᵀ,特徵分解可以改寫成A = EΛEᵀ。

可以直接使用函式庫eigenSLEPc

二維、三維,有著複雜的數學公式。

Eigendecomposition不一定存在

不足N種特徵向量,沒有特徵分解。集滿N種特徵向量,才有特徵分解。

長寬不同的矩陣,沒有特徵分解。長寬相同的方陣,才有機會擁有特徵分解,但也可能沒有特徵分解。

一個方陣是否擁有特徵分解,判斷過程相當複雜。因此大家轉為使用對稱矩陣,保證擁有特徵分解;或者轉為使用奇異值分解。

Invertible ≠ Diagonalizable

可逆(擁有反矩陣)、可對角化(擁有特徵分解),兩者沒有任何關聯。舉幾個範例:

shear matrix ⎡ 1 1 ⎤ is invertible but not diagonalizable.
             ⎣ 0 1 ⎦
project matrix ⎡ 1 0 ⎤ is diagonalizable but not invertible.
               ⎣ 0 0 ⎦
zero matrix ⎡ 0 0 ⎤ is diagonalizable but not invertible.
            ⎣ 0 0 ⎦

Eigendecomposition的用途

一、反矩陣:A⁻¹ = (EΛE⁻¹)⁻¹ = EΛ⁻¹E⁻¹。

展開倒數,EΛE⁻¹順序翻轉,EΛE⁻¹各自添上⁻¹,矩陣倒數化作特徵值倒數。

值得一提的是,對稱矩陣的反矩陣A⁻¹ = EΛ⁻¹E⁻¹ = EΛ⁻¹Eᵀ。求反矩陣一般採用高斯喬登消去法;如果已經做好特徵分解,那麼特徵向量轉置、特徵值倒數,即可順便求得反矩陣。

二、矩陣次方:Aⁿ = (EΛE⁻¹)ⁿ = EΛⁿE⁻¹。

展開次方,相鄰的E與E⁻¹相消,矩陣次方化作特徵值次方。

數論領域有一個經典演算法:「利用傅立葉轉換O(NlogN),數列卷積O(N²)改成頻譜點乘O(N)」。此處是進階版本:「利用特徵分解O(N²(N+T)),矩陣乘法O(N³)改成特徵值點乘O(N)」。當次方很大,演算法得以發揮功效,加速矩陣次方運算。

三、對稱半正定矩陣的共軛分解:⟌A = √ΛEᵀ。

A = EΛEᵀ = (E√Λ)(√ΛEᵀ) = (√ΛEᵀ)ᵀ(√ΛEᵀ) = BᵀB。

共軛分解有許多種方式,其中特徵分解是應用最廣的方式。共軛分解是相當重要的矩陣運算,卻未受到數學家的重視,沒有正式學術名稱,只有少數文獻稱作「共軛分解conjugate decomposition」。運算符號是我瞎掰的。

Eigenbasis (Singular Value)

Singular Vector與Singular Value

數學式子AᵀAv = σ²v,σ是奇異值,v是右奇異向量。

數學式子AAᵀu = σ²u,σ是奇異值,u是左奇異向量。

無論A是哪種矩陣,AᵀA和AAᵀ都是對稱半正定矩陣。奇異向量是實數、正規正交、恰好N種。奇異值是實數、恰好N個。數學家強制定義奇異值必須非負。

AᵀA和AAᵀ可以看成:共軛複數相乘,得到長度平方(絕對值平方),從複數變成了非負實數。

Singular Vector與Singular Value演算法

詳情請見本站文件「Eigenbasis」。

QR分解三個演算法的改良版本。時間複雜度O(min(N²M,NM²)),通常簡單寫成O(N³)。

特殊矩陣的Singular Vector與Singular Value

一般矩陣:奇異向量是實數、正規正交、恰好N種。奇異值是非負實數、恰好N個。

對稱矩陣:承上。左右奇異向量相同。特徵向量與奇異向量各自相差一個正號或負號。特徵值與奇異值各自相差一個正號或負號。

對稱半正定矩陣:承上。左右奇異向量相同。特徵向量等於奇異向量。特徵值等於奇異值!

Singular Value Decomposition(SVD)

「奇異值分解」。A = UΣVᵀ。左奇異向量們U、奇異值們Σ、右奇異向量們V。Σ和A長寬相同。U和V是方陣。

為什麼名稱多了一個Value呢?我也不知道。

⎡ 2 1 ⎤   ⎡ -0.82  0.39 -0.40 ⎤ ⎡ 2.67 0    ⎤ ⎡ -0.81  0.58 ⎤ᵀ
⎢ 0 1 ⎥ = ⎢ -0.21 -0.88 -0.40 ⎥ ⎢ 0    0.91 ⎥ ⎣ -0.58 -0.81 ⎦
⎣ 1 1 ⎦   ⎣ -0.52 -0.24  0.81 ⎦ ⎣ 0    0    ⎦
   A                 U                Σ              Vᵀ

⎡ A₁₁ A₁₂ ⎤   ⎡ |  |  |  ⎤ ⎡ σ₁ 0  ⎤ ⎡ |  |  ⎤ᵀ
⎢ A₂₁ A₂₂ ⎥ = ⎢ u₁ u₂ u₃ ⎥ ⎢ 0  σ₂ ⎥ ⎣ v₁ v₂ ⎦
⎣ A₃₁ A₃₂ ⎦   ⎣ |  |  |  ⎦ ⎣ 0  0  ⎦
     A             U           Σ         Vᵀ

奇異向量長度,在奇異值分解當中必須左右配合,縮放為1!

奇異向量方位,在奇異值分解當中必須左右配合,固定方向!

奇異向量次序無所謂,可以自由對調(連同奇異值),可以按照奇異值大小排序。

⎡ 2 1 ⎤   ⎡  0.39 -0.82 -0.40 ⎤ ⎡ 0.91 0    ⎤ ⎡  0.58 -0.81 ⎤ᵀ
⎢ 0 1 ⎥ = ⎢ -0.88 -0.21 -0.40 ⎥ ⎢ 0    2.67 ⎥ ⎣ -0.81 -0.58 ⎦
⎣ 1 1 ⎦   ⎣ -0.24 -0.52  0.81 ⎦ ⎣ 0    0    ⎦
   A                 U                Σ              Vᵀ

⎡ A₁₁ A₁₂ ⎤   ⎡ |  |  |  ⎤ ⎡ σ₂ 0  ⎤ ⎡ |  |  ⎤ᵀ
⎢ A₂₁ A₂₂ ⎥ = ⎢ u₂ u₁ u₃ ⎥ ⎢ 0  σ₁ ⎥ ⎣ v₂ v₁ ⎦
⎣ A₃₁ A₃₂ ⎦   ⎣ |  |  |  ⎦ ⎣ 0  0  ⎦
     A             U           Σ         Vᵀ

二維、三維,有著複雜的數學公式。

Singular Value Decomposition一定存在

無論哪種矩陣,通通擁有奇異值分解!如果沒有特徵分解,那就使用奇異值分解!

奇異值分解彷彿是特徵分解取絕對值:向量扳正、數值轉正。

Singular Value Decomposition的用途

一、虛擬反矩陣:A⁺ = VΣ⁻¹Uᵀ。

反矩陣可用來求解:solve Ax = b則x = A⁻¹b。虛擬反矩陣可用來求最小平方解:min ‖Ax - b‖²則x = A⁺b。

二、對稱半正定矩陣的二次型谷線:min‖x‖=1 xᵀAx。

最小值位置:最小的奇異值的奇異向量。最小值:最小的奇異值的平方。稜線則是最大值。

三、頻譜範數:max‖x‖≠0 ‖Ax‖ / ‖x‖。

取平方、指定長度,如同二次型谷線。答案:最大的奇異值。

四、矩陣降維:argminrank(X)≤k ‖X - A‖ꜰ²。

已知原矩陣A,求新矩陣X,指定維度為k,平方誤差盡量小。答案:奇異值分解,保留前k大的奇異值,其餘奇異值歸零。詳情請見「Eckart–Young Theorem」。

五、矩陣正規化:⧚A⧛ = UVᵀ。

向量正規化,讓向量長度變成1。矩陣正規化,讓奇異值們變成1。矩陣正規化是相當重要的矩陣運算,卻未受到數學家的重視,沒有正式學術名稱。運算符號是我瞎掰的。

六、一次矩陣方程式的最小平方解:argminXᵀX=I ‖AX - B‖ꜰ²。

已知一次項係數矩陣A、常數項矩陣B,求未知數矩陣X,指定X為正規正交矩陣,平方誤差盡量小。答案:⧚AᵀB⧛。詳情請見「Orthogonal Procrustes Problem」。

七、最佳交叉投影:argmaxXᵀX=I ‖XᵀA‖ꜰ²。

已知矩陣A,求得正規正交矩陣X。A每個向量投影到X每個向量,投影之後,向量長度平方總和盡量大。答案:左奇異向量U。詳情請見「Principal Component Analysis」。

Representation🚧

Representation

本站文章「Correlation」和「Factoring」已經詳細介紹過經典的重新表示。本篇文章從線性函數的觀點,再度介紹一次。順便藉此機會,讓讀者更加瞭解線性函數的功效。

矩陣變換AX = Y,已知矩陣X,尋找變換矩陣A,也尋找新矩陣Y,使得Y是特殊矩陣。

不相關化:使得YYᵀ是對角線矩陣
簡易白化:使得YYᵀ是恆等矩陣(假設X已經中心化)
進階白化:使得YYᵀ是恆等矩陣,而且X與Y的奇異向量保持相同(假設X已經中心化)
不相關化矩陣A =     Uᵀ = ⧚XXᵀ⧛⁻¹ = ⟌⧚XXᵀ⧛
簡易白化矩陣A =  Σ⁻¹Uᵀ = ⟌(XXᵀ)⁻¹
進階白化矩陣A = UΣ⁻¹Uᵀ = √(XXᵀ)⁻¹ = √XXᵀ⁻¹
不相關化結果Y = ΣVᵀ = ⟌XᵀX
簡易白化結果Y =  Vᵀ = ⧚XᵀX⧛
進階白化結果Y = UVᵀ = ⧚X⧛

注意到⧚XᵀX⧛ = ⧚XXᵀ⧛ = I,⟌⧚XXᵀ⧛⁻¹和⟌⧚XᵀX⧛無法得到奇異向量。我故意寫出來,是為了讓數學式子外觀工整。

Decorrelation

「不相關化」。矩陣X實施變換,使得YYᵀ是對角線矩陣。

奇異值分解X = UΣVᵀ,移項UᵀX = ΣVᵀ,對應AX = Y。

變換矩陣A = Uᵀ。新矩陣Y = ΣVᵀ。

Whitening

「簡易白化」。矩陣X實施變換,使得YYᵀ是恆等矩陣。(假設X已經中心化。)

奇異值分解X = UΣVᵀ,移項Σ⁻¹UᵀX = Vᵀ,對應AX = Y。

變換矩陣A = Σ⁻¹Uᵀ。新矩陣Y = Vᵀ。

Whitening

「進階白化」。矩陣X實施變換,使得YYᵀ是恆等矩陣,且X與Y的奇異向量保持相同。(假設X已經中心化。)

奇異值分解X = UΣVᵀ,移項Σ⁻¹UᵀX = Vᵀ,同乘一個矩陣UΣ⁻¹UᵀX = UVᵀ。

變換矩陣A = UΣ⁻¹Uᵀ。新矩陣Y = UVᵀ。

Multidimensional Scaling

「多維度縮放」。已知內積矩陣XᵀX,求得原本矩陣X。

奇異值分解X = UΣVᵀ,內積矩陣XᵀX = VΣ²Vᵀ。

共軛分解得到原本矩陣X = ΣVᵀ。

不相關化=多維度縮放(奇異值分解的共軛分解)。

Principal Component Analysis

「主成分分析」。已知矩陣X,求得正規正交矩陣Q,交叉投影長度平方總和盡量大argmaxQᵀQ=I ‖QᵀX‖ꜰ²。

答案是奇異向量Q = U。投影之後得到QᵀX = ΣVᵀ。

不相關化=主成分分析(投影之後的結果)。

X = [4 5 ; 16 4 ; 9 8 ; 3 16 ; 8 14 ; 17 11; 23 9 ; 8 19 ; 16 16; 23 14; 5 24 ; 13 25; 19 22; 26 21; 29 16; 13 30; 22 31; 28 27; 32 23; 38 19; 30 32; 37 28]'; X -= mean(X,2); C = X * X'; [E D] = eig(C); Y = inv(sqrt(D)) * E' * X; Y = Y'; scatter(Y(:,1),Y(:,2)) X = X'; scatter(X(:,1),X(:,2))

Linear Function

楔子

計算學家重視數值,本站以變數的加減、變數的倍率來介紹「線性函數(狹義版本)」。

數學家重視性質,以函數的加法性、函數的倍率性來定義「線性函數(廣義版本)」。

儘管本站的介紹方式比較直覺,卻是非常偏頗的介紹方式。為了端正視聽,以下簡述數學家的介紹方式。完全是另外一種世界觀。

Vector Space的由來

變數的加減、變數的倍率,變數可以是各種東西。

f(x) = 2 ⋅ x      + 3 ⋅ y        + 5 ⋅ z       線性函數(狹義版本)
f(x) = 2 ⋅ 1.414  + 3 ⋅ 3.14     + 5 ⋅ 2.71    變數是實數
f(x) = 2 ⋅ (x²+x) + 3 ⋅ (x²+x+1) + 5 ⋅ (x-1)   變數是多項式
f(x) = 2 ⋅ ↗      + 3 ⋅ ↖        + 5 ⋅ →       變數是施力
f(x) = 2 ⋅ 🍎     + 3 ⋅ 🍓       + 5 ⋅ 🍒      變數是水果

於是數學家創造了「向量空間」這個泛稱!

Vector Space

「向量空間」由一個集合、兩個運算組成。兩個運算分別是加法運算、倍率運算。

理想名稱應是「加倍空間」。古人將加法、倍率聯想到物理向量,所以才取名「向量空間」。

集合:可以設定成實數、整數、餘數、多項式、向量、函數、……。

加法運算、倍率運算:泛指一切適當的運算。可以設定成實數加法與實數倍率,也可以設定成實數乘法與實數次方。設定方式通常不只一種。

為了釐清加法運算與倍率運算的責任,數學家做了詳細規定:

向量空間之加法運算的規定
1. Associativity 加法結合律
   u + (v + w) = (u + v) + w
2. Commutativity 加法交換律
   u + v = v + u
3. Identity element 加法單位元素
   v + 0 = v
4. Inverse element 加法反元素(負數、減法)
   v + (-v) = 0

向量空間之倍率運算的規定
5. Associativity 倍率結合律
   a ⋅ (b ⋅ v) = (a ⋅ b) ⋅ v
6. Distributivity of vector sum 倍率分配律,針對向量部分
   a ⋅ (u + v) = (a ⋅ u) + (a ⋅ v)
7. Distributivity of scalar sum 倍率分配律,針對倍率部分
   (a + b) ⋅ v = (a ⋅ v) + (b ⋅ v)
8. Identity element 倍率單位元素
   1 ⋅ v = v

集合當中所有元素,必須符合所有規定。

符號uvw0:向量空間的集合的元素。符號ab1:倍率。符號01:泛指符合規定的元素,而且至少要有一個、必須存在。

倍率運算的倍率值,通常設定成「體field」。體由一個集合、兩個運算組成。兩個運算分別是加法運算、乘法運算。數學家也做了詳細規定,不過此處省略。

Vector Space實際範例

集合設定成多項式,加法運算設定成多項式加法,倍率運算設定成多項式倍率。

倍率的集合設定成實數,倍率的加法運算設定成實數加法,倍率的乘法運算設定成實數乘法。

0是零多項式,1是實數1。此例的0和1剛好是單一元素,而且非常直覺;但是當集合設定成其他特殊的集合,0和1就可能有多種元素。

Vector Space實際範例

再舉一個複雜的例子。

向量空間
 集合   --> 餘數 mod n
 加法運算 --> 餘數乘法×
 倍率運算 --> 餘數次方^

體(倍率運算的倍率值)
 集合   --> 整數  	(甚至推廣為餘數 mod φ(n))
 加法運算 --> 整數加法+	(甚至推廣為餘數加法)
 乘法運算 --> 整數乘法×	(甚至推廣為餘數乘法)

向量空間之加法運算的規定    	   let u=2, v=3, w=4, a=5, b=6, n=7
1. u + (v + w) = (u + v) + w	|  2 × (3 × 4) ≡ (2 × 3) × 4
2. u + v = v + u            	|  2 × 3 ≡ 3 × 2
3. v + 0 = v                	|  3 × 1 ≡ 3          符號0是餘數1
4. v + (-v) = 0             	|  3 × 3 ≡ 3 × 5 ≡ 1  倒數

向量空間之倍率運算的規定
5. a ⋅ (b ⋅ v) = (a ⋅ b) ⋅ v  	|  (2 ^ 6) ^ 5 ≡ 2 ^ (5 × 6)
6. a ⋅ (u + v) = a ⋅ u + a ⋅ v	|  (2 × 3) ^ 5 ≡ (2 ^ 5) × (3 ^ 5)
7. (a + b) ⋅ v = a ⋅ v + b ⋅ v	|  3 ^ (5 + 6) ≡ (3 ^ 5) × (3 ^ 6)
8. 1 ⋅ v = v                 	|  3 ^ 1 ≡ 3          符號1是整數1

Inner Product Space

「內積空間」由一個集合、三個運算組成。三個運算分別是加法運算、倍率運算、內積運算。

理想名稱應是「加倍內空間」,不過這名稱有點拗口。

內積運算:泛指一切適當的運算。例如集合設定成向量、加法運算設定成向量加法、倍率運算設定成向量倍率、內積運算設定成向量點積。設定方式通常不只一種。

為了釐清內積運算的責任,數學家做了詳細規定:

內積空間之內積運算的規定
9.  Additivity 加法分配律
    (u + v) ∙ w = (u ∙ w) + (v ∙ w)
10. Homogeneity of degree 1 倍率結合律
    (a ⋅ u) ∙ w = a ⋅ (u ∙ w)
11. Commutativity 內積交換律
    u ∙ v = v ∙ u
12. Positive Definiteness 正定
    u ∙ u ≥ 0
    u ∙ u = 0 iff u = 0

內積空間是向量空間的延伸版本。數學家之所以發明內積空間,是因為有了內積運算之後,可以引入長度和角度的概念。

「範數norm」泛指一切「自己與自己的內積、再開根號」的情況。如果集合設定成向量,內積運算設定成向量點積,那麼範數是指向量長度。

「正交orthogonality」泛指一切「內積等於零」的情況。如果採用方才的設定,那麼正交是指向量垂直。

抽象化

汽車、貨車、公車、聯結車,泛稱為「車」。由實際名稱變成泛稱的這個過程,叫做「抽象化abstraction」。

數學家非常喜歡抽象化。上述名詞,諸如加法運算、倍率運算、內積運算、向量空間、內積空間、範數、正交,都是泛稱,都是經過抽象化的名稱。

Basis / Coordinate

向量空間,從中選定一組元素們,當作座標軸(基底)。座標軸互相「線性獨立linear independent」,座標軸數量(維度)足以生成所有元素。符合條件的座標軸有無限多組。

選定座標軸之後,座標軸各自利用倍率運算進行縮放,然後利用加法運算進行合成,就可以得到向量空間當中每一個元素。得到一個元素的過程稱作「線性組合linear combination」,得到每一個元素的過程稱作「生成span」。

反過來說,向量空間的每一個元素,也可以利用分量的概念,分散到每個座標軸上面,得到一個座標,座標其實就是倍率。每一個元素各自擁有獨一無二的座標。

vector space: V
element v of V: v ∈ V
basis of V: {v₁, v₂, ..., vɴ}
linear combination: v = c₁v₁ + c₂v₂ + ... + cɴvɴ
span: V = span(v₁, v₂, ..., vɴ)
coordinate of v: {c₁, c₂, ..., cɴ}

Axiom of Choice = Vector Space has Basis

符合條件的座標軸,一定存在嗎?數學家訂立公設,聲稱存在。

數學家訂立「選擇公設」,假設向量空間必有一組線性獨立的元素、假設向量空間必有座標軸(基底)、假設向量空間每個元素的線性組合可以有唯一方式。這些事情都等價,此處省略證明。

線性組合有唯一方式(函數的概念),理應是主角,理應命名與定義。然而數學家卻讓主角變旁白,將之塞入向量空間(變數的概念),利用「選擇公設」聲稱它存在。

這部作品的世界觀設定,實在是太複雜了。

Linear Function

終於來到正題。狹義版本推廣成廣義版本。加法分配律、倍率結合律推廣成加性函數、倍性函數。

additive function:
                        additive
y₁ + y₂ = f(x₁) + f(x₂) ======== f(x₁ + x₂)

homogeneous function of degree 1:
                 homogeneous
k ⋅ y = k ⋅ f(x) =========== f(k ⋅ x)
linear function f:              affine function g:
1. f(x₁+x₂) = f(x₁) + f(x₂)     1. f(x₁+x₂) = f(x₁) + f(x₂)
2. f(kx) = k f(x)               2. f(kx) = k f(x)
                                3. g(x) = f(x) + c
加性函數:輸入相加等同輸出相加。先相加再代入,等於先代入再相加。
倍性函數:輸入倍率等同輸出倍率。先乘上倍率再代入,等於先代入再乘上倍率。
線性函數:加性函數暨倍性函數。
仿射函數:線性函數納入常數加法。

線性函數跟直線無關。取名線性是因為古人沒有考慮清楚。理想名稱應是「加倍函數」。

為了迎合定義、為了能夠運算,輸入輸出必須是向量空間,或者是內積空間。理想名稱應是「加倍空間」、「加倍內空間」。

廣義版本的新功能

一、輸入與輸出可以是不同類型的東西。
二、函數可以有加法和倍率以外的運算。

例如微積分的極限運算lim、機率論的期望值運算E[],都是線性函數。

廣義版本的功效

由於加性函數、倍性函數,使得座標軸的線性組合、再實施變換,等同座標軸實施變換、再線性組合。

linear function f: X -> Y
basis(X) = {x₁, x₂, ..., xɴ}   coordinate(x) = {c₁, c₂, ..., cɴ}
basis(Y) = {y₁, y₂, ..., yɴ}   coordinate(y) = {c₁, c₂, ..., cɴ}

linear combination:
x = c₁x₁ + c₂x₂ + ... + cɴxɴ

linear function:
y = f(x)
y = f(c₁x₁ + c₂x₂ + ... + cɴxɴ)
y = c₁ f(x₁) + c₂ f(x₂) + ... + cɴ f(xɴ)
y = c₁   y₁  + c₂   y₂  + ... + cɴ   yɴ

線性函數有什麼功效呢?分別觀察座標軸和座標:

輸入的座標軸,套用函數,實施變換,得到輸出的座標軸!

basis(X) = {x₁, x₂, ..., xɴ}
basis(Y) = {f(x₁), f(x₂), ..., f(xɴ)}

輸入形成座標系統,輸出也形成座標系統。輸入輸出一一對應,座標一一相等!

coordinate(x) = {c₁, c₂, ..., cɴ}
coordinate(y) = {c₁, c₂, ..., cɴ}

廣義版本的特色

一、輸入輸出各自擁有座標軸。輸入的座標軸,套用函數,得到輸出的座標軸。
二、座標軸有無限多種選擇,隨便一種都行。
三、輸入輸出的座標軸通常不同,但是座標一定相同。
四、線性函數是座標不變、座標軸改變。

Change of Basis / Similar Matrices

輸入的座標軸進行更換。輸出的座標軸也隨之更換。

輸入的座標軸、輸出的座標軸,互為相似矩陣。

本站文件曾經提到:「更換座標系」的其中一種方式是「套用函數組」。當然也可以「套用線性函數」。

然而數學家卻採用了中古奇幻世界觀設定:因為是「線性函數」所以才能「更換座標系」。有興趣的讀者請自行穿越異世界:

在異世界當中,「更換座標系」是初學者最難掌握的線性代數主題之一。如果你既不是主角更沒有外掛,那麼請你自己保重。

Linearization(Linear Approximation)【尚無正式名稱】

狹義線性函數求值,可以拆成兩個步驟:

一、函數視作座標軸。(線性獨立、維度足夠)
二、輸入元素視作座標,求輸出元素。

廣義線性函數求值,可以拆成四個步驟:

一、選定輸入的座標軸。(線性獨立、維度足夠)
二、求得輸出的座標軸。(輸入的座標軸,一一套用函數)
三、輸入元素,求座標。(根據輸入的座標軸)
四、座標,求輸出元素。(根據輸出的座標軸)

「線性化」。非線性函數硬是改成線性函數。雖然不是線性函數,卻硬是用上述手法計算,求得近似值。

為了方便求得座標,輸入的座標軸習慣選擇正規正交矩陣,以投影公式求得座標:輸入元素與座標軸的內積(不必除以座標軸長度平方)。

Matrix

線性組合可以寫成矩陣乘法的格式。

linear combination x = c₁x₁ + c₂x₂ + ... + cɴxɴ
⎡ | ⎤   ⎡  |  |  |      | ⎤ ⎡ | ⎤
⎢ x ⎥ = ⎢ x₁ x₂ x₃ ... xɴ ⎥ ⎢ c ⎥
⎣ | ⎦   ⎣  |  |  |      | ⎦ ⎣ | ⎦

linear combination y = c₁y₁ + c₂y₂ + ... + cɴyɴ
⎡ | ⎤   ⎡  |  |  |      | ⎤ ⎡ | ⎤
⎢ y ⎥ = ⎢ y₁ y₂ y₃ ... yɴ ⎥ ⎢ c ⎥
⎣ | ⎦   ⎣  |  |  |      | ⎦ ⎣ | ⎦

線性函數可以寫成矩陣乘法的格式。然而輸入被替換成座標了。

linear function f: X -> Y
⎡ | ⎤   ⎡   |     |     |         |   ⎤ ⎡ | ⎤
⎢ y ⎥ = ⎢ f(x₁) f(x₂) f(x₃) ... f(xɴ) ⎥ ⎢ c ⎥
⎣ | ⎦   ⎣   |     |     |         |   ⎦ ⎣ | ⎦

狹義版本是特例:輸入的座標軸x₁...xɴ恰好是恆等矩陣I。