Matrix

Matrix

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

[ 1 2 -5 ]
[ 2 4  6 ]
[ 3 1  7 ]

其中
A1,1 = 1    A1,2 = 2   A1,3 = -5
A2,1 = 2    A2,2 = 4   A2,3 = 6
A3,1 = 3    A3,2 = 1   A3,3 = 7

一個矩陣由許多個數字構成,排列整齊,呈現矩形。我們習慣把數字改稱為「元素element」。

水平一整條元素叫做row,垂直一整條元素叫做column。元素的編號,先編row,次編column。

Matrix資料結構

第一種方式,用一個二維陣列當作矩陣。如果你喜歡的話,也可以用一維陣列當作矩陣,然後自己算索引值。

另一種方式,把矩陣元素一個一個列出來。如果矩陣元素為零則不列出來。就這麼簡單。

UVa 10855 11360 11149

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

人類習慣將線性函數呈現為矩陣的模樣。

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

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

通常會把各個變數改名成 x₁ x₂ x₃ ...
所有輸入變數拼在一起,成為一個向量 x
輸出變數叫做 y

                      [ x₁ ]
    y    = [ 1 2 -5 ] [ x₂ ]
                      [ x₃ ]

    y    =     A        x
    y    =     f      ( x  )

一般提到函數,輸入可以是多重變數,但是輸出一定是單一變數。一旦有了矩陣相助,輸入與輸出都可以是多重變數。

[ y₁ ]   [ 1 2 -5 ] [ x₁ ]
[ y₂ ] = [ 2 4  6 ] [ x₂ ]
[ y₃ ]   [ 3 1  7 ] [ x₃ ]

  y    =     A        x
  y    =     f      ( x  )

約定俗成,我們會把x與y排列成向量,而非矩陣。如此一來,只要知道了線性函數的矩陣,就能完全確定函數的變數有多少個、完全確定函數是什麼。

輸出變數、輸入變數排列成矩陣:
[ 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  )

一個矩陣就代表一個函數、一個線性函數。

A x ⇔ f(x)

A ⇔ f   省略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運算

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

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

求值

A x ⇔ f(x)

求解(除法)

    y = A x   ⇔       y  = f(x)
A⁻¹ y =   x   ⇔   f⁻¹(y) =   x

求值的反運算。求解偶爾被稱為除法。

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

或者,先以「高斯喬登消去法」求反矩陣,再以反矩陣進行求值。時間複雜度也是O(N³),但是步驟數量較多。

加法、減法

A x + B x ⇔ f(x) + g(x)
(A + B) x ⇔ (f + g)(x)

A + B ⇔ f + g   省略x的部分

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

倍率

k ⋅ (A x) ⇔ k ⋅ f(x)
(k ⋅ A) x ⇔ (k ⋅ f)(x)

k ⋅ A ⇔ k ⋅ f   省略x的部分

函數乘上一個常數。矩陣的每個數字一齊乘上相同倍率。

複合(乘法)

A (B x) ⇔ f(g(x))
(A B) x ⇔ (f ∘ g)(x)

A B ⇔ f ∘ g   省略x的部分

複合的計算過程相當繁雜:第一個矩陣取水平一整條、第二個矩陣取垂直一整條,求「點積」,得到一個元素;取盡各種可能性,得到整個矩陣。

複合通常被稱做乘法。啊就古人取名的時候沒想清楚,成為歷史共業。

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

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

http://en.wikipedia.org/wiki/Strassen_algorithm

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

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

僅是單純的拆成小方陣相乘,仍然需要8次乘法,以及4次加法,把遞迴公式列出來後,運用Master Theorem,可以求出時間複雜度為O(N³)。根據遞迴公式,要讓時間複雜度變小,主要取決於乘法的次數,至於加法的次數不是主要影響因素。

經過一些詭異的調整方法,使用7次乘法,做些加加減減,就兜出了大方陣的乘積。時間複雜度變為O(Nlog₂7),實際取log一下,約為O(N2.81)。

複合(乘法)(Virginia-Vassilevska-Williams Algorithm)

http://www.cs.berkeley.edu/~virgi/matrixmult.pdf

當今世上最快的矩陣相乘演算法,時間複雜度為O(N2.3727)。方法相當複雜,我不懂。

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

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

至於上界就是剛剛提到的O(N2.3727)。

分解

C x         ⇔ h(x)
C x = A B x ⇔ h(x) = (f ∘ g)(x)

C = A B ⇔ h = f ∘ g   省略x的部分

複合的反向操作。複合:很多個矩陣連乘,併成一個矩陣。分解:一個矩陣,拆成很多個矩陣連乘。

經典的矩陣分解,諸如QR分解、LU分解、特徵分解、奇異值分解、極分解等等。

疊代(次方)

Aⁿ x ⇔ f(f(f(f(f(f(f(f(x))))))))
        \__________  __________/
                   \/
                   n次

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

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

Basis

Linear Function的第一種觀點

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

[ y₁ ]   [ 1 2 -5 ] [ x₁ ]
[ y₂ ] = [ 2 4  6 ] [ x₂ ]
[ y₃ ]   [ 3 1  7 ] [ x₃ ]

         [ 1 ]          [ 2 ]          [ -5 ]
       = [ 2 ] ⋅ x₁  +  [ 4 ] ⋅ x₂  +  [  6 ] ⋅ 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₁ ]
[ y₂ ] = [ 2 4  6 ] [ x₂ ]
[ y₃ ]   [ 3 1  7 ] [ x₃ ]

         [ (1 2 -5) ∙ (x₁ x₂ x₃) ]
       = [ (2 4  6) ∙ (x₁ x₂ 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 2 3 ]   transpose   [ 1 0 9 5 ]
[ 0 0 7 ]  ---------->  [ 2 0 8 4 ]
[ 9 8 7 ]  <----------  [ 3 7 7 6 ]
[ 5 4 6 ]   transpose

    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

Indentity Matrix

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

所有向量經過單位矩陣變換之後,紋風不動,完全不變。(identity是指相同個體。)

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

Orthonormal Matrix / Unitary Matrix

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

座標軸長度皆為1、角度互相垂直。(ortho-正交,normal正規,unitary么正。ortho-是指垂直,normal是指一單位量,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分解」可以求得容積與維度。

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

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

Timus 1041

QR Decomposition

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

把一個矩陣A分解成矩陣Q與矩陣R的乘積,A = QR。Q是互相垂直的單位向量(正規正交矩陣),R是扳動量(上三角矩陣)。

演算法(Gram-Schmidt Orthonormalization)

https://en.wikipedia.org/wiki/Gram–Schmidt_process

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

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

時間複雜度O(N³)。

演算法(Householder Triangularization)

http://faculty.ucmerced.edu/mhyang/course/eecs275/lectures/lecture12.pdf

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

不斷套用鏡射矩陣,逐步調整矩陣A的每個向量,直到變成上三角矩陣R。優點是向量的長度變化比較少、誤差比較小。

時間複雜度O(N³)。

演算法(Givens Triangularization)

http://www.cs.nthu.edu.tw/~cherung/teaching/2011anm/note07.pdf

Givens Rotation:在標準座標軸當中,挑選其中兩個軸,在其平面上旋轉。

不斷套用軸面旋轉矩陣,逐步調整矩陣A的每個向量,直到變成上三角矩陣R。優點是容易設計平行演算法。

時間複雜度O(N³)。

Eigenbasis (Root Finding)

本章主角是特徵向量與特徵值(真實版本)

概論

「特徵基底」來龍去脈盤根錯節,林林總總各有千秋。以下將從各種面向,描述「特徵基底」及演算法,分成數章介紹。

這些章節的標題都是我自己定的。這種章節架構僅供參考。這種章節架構著重數感直觀,但是不依循公理系統。數學系的線性代數教科書絕不會採用這種章節架構。

「特徵基底」性質優美,早年發展許多應用,亦有健全的函式庫如C++的eigen。然而演算法時間複雜度O(N³),太慢了不實用,近年已被打入冷宮。建議讀者淺嚐即止。

矩陣求根

本站文件「Root Finding」,介紹了「輸入、輸出只有一個變數」的函數,以及根、解、不動點、特徵點。

此處介紹「輸入、輸出有很多個變數」的線性函數,以及根、解、不動向量、特徵向量。

根(核):Ax = 0,符合條件的x。

線性函數必定有一個根:零向量x = 0,缺乏討論意義。

線性函數通常有許多個根,並且組成空間,空間維度等於A的座標軸數量減去A的rank。白話解釋:座標軸無法觸及之處,當然輸出0囉。另外rank、determinant可以判斷是否有許多個根。

解:Ax = b,符合條件的x。b是已知的、特定的向量。

類似於根。請見本站文件「Linear Equation」。

不動向量:Ax = x,符合條件的x。

線性函數必定有一個不動向量:零向量x = 0。

特徵向量:Ax = λx,符合條件的x。λ是任意一種倍率。

線性函數通常有許多個特徵向量,後續文章的主角。

Eigenvector / Eigenvalue

針對一個線性函數,從眾多的輸入向量當中,找到其中一些輸入向量,讓輸出向量恰是輸入向量的倍率,此時輸入向量稱做「特徵向量」,倍率稱做「特徵值」。

數學式子是Ax = λx。A是線性函數,x是輸入向量,λx是輸出向量。x是特徵向量,λ是特徵值。

特徵向量變換之後,長度伸縮,方向相同或相反。

特徵值可正、可負、可零。正的伸縮,負的伸縮兼翻轉,零的長度歸零。

特徵向量有無限多個

零向量必定是特徵向量,缺乏討論意義,大家習慣無視它。

特徵向量的任何一種倍率(方向相同或相反),也是特徵向量,也是相同特徵值。大家習慣取長度為一的特徵向量當作代表,方向則隨意。

方向不同的特徵向量,如果恰好擁有相同特徵值,那麼這些特徵向量構成的平面、空間、……當中的任何一個向量,也是特徵向量,也是相同特徵值。大家習慣取互相垂直的特徵向量當作代表,方向則隨意。

Characteristic Equation / Characteristic Polynomial

無邊無際、無窮無盡,如何找到特徵向量和特徵值呢?

嘗試解Ax = λx。移項Ax - λx = 0。合併(A - λI)x = 0。

若是唯一解,那麼x顯然是零向量。缺乏討論意義。

若有其他解,那麼令det(A - λI) = 0,稱做「特徵方程式」。展開det(A - λI),形成λ的多項式,稱作「特徵多項式」。

先求特徵值λ:展開det(A - λI) = 0,特徵多項式求根。

再求特徵向量x:特徵值代入(A - λI)x = 0,線性函數求根。

一種特徵值,得到一種特徵向量。

A = [ 1 -1 ]   A - λI = [ (1-λ)  -1   ]      det(A - λI) = 0
    [ 2  4 ]            [   2   (4-λ) ]   => (1-λ)(4-λ) + 2 = 0
                                          => λλ - 5λ + 6 = 0
                                          => λ = 2 or 3

when eigenvalue λ = 2        |   when eigenvalue λ = 3        
                             |                                
    (A - λI)      x  =  0    |       (A - λI)      x  =  0    
                             |                                
[ (1-2)  -1   ] [x₁] = [0]   |   [ (1-3)  -1   ] [x₁] = [0]   
[   2   (4-2) ] [x₂]   [0]   |   [   2   (4-3) ] [x₂]   [0]   
                             |                                
get { x₁ =  1k               |   get { x₁ =  1k               
    { x₂ = -1k               |       { x₂ = -2k               
                             |                                
then eigenvector x = [ 1]    |   then eigenvector x = [ 1]    
                     [-1]    |                        [-2]    

特徵向量最多N種

數學家藉由determinant與characteristic polynomial定義特徵值:N次多項式必有N個根,必得N個特徵值。N是方陣邊長。

這種定義方式,儘管湊出了N個特徵值,卻可能湊不出N種特徵向量。詳細分析如下:

一、相異特徵值,各自擁有相異特徵向量,構成相異維度。

二、相同特徵值(重根),不見得都有特徵向量,但至少一種。

縮放矩陣:特徵值和特徵向量都是實數。特徵向量確實存在。

旋轉矩陣:特徵值和特徵向量都是複數。特徵向量確實存在,卻無法作圖。

投影矩陣:特徵值有0。特徵向量確實存在。

歪斜矩陣:特徵向量不足N種。

特徵向量演算法(Characteristic Polynomial)

一、多項式函數求根,取得特徵值。

二、線性函數求根(求解),取得特徵向量。

然而無法克服:一、根的範圍不明;二、根可能是複數。

沒人用這種方法計算特徵值、特徵向量。

Eigenbasis (Optimization)

本章主角是特徵向量與特徵值(虛擬版本)

矩陣最佳化

本站文件「Optimization」,介紹了「輸入有許多個變數、輸出只有一個變數」的函數,以及極值。

本站文件「Linear Optimization」,介紹了「輸入、輸出有許多個變數」的線性函數,以及極值。

Pseudo-eigenvalue【目前稱作Rayleigh Quotient】

特徵向量擁有明確的特徵值。其他向量只能擁有虛擬的、近似的特徵值。如何得到近似的特徵值呢?利用最佳化的思維,嘗試讓Ax與λx兩者差異盡量小:對應項的差的平方的總和,越小越好。

(方便起見,x和Ax畫在同一個二維平面。)

minimize ‖Ax - λx‖²

∂           
―― ‖Ax - λx‖² = 0                      「一次微分等於零」的地方是極值、鞍點
∂λ                                      二次函數、開口向上,必是最小值
  ∂
[ ―― (Ax - λx) ] ∙ [ 2(Ax - λx) ] = 0   微分連鎖律
  ∂λ

[ -x ] ∙ [ 2(Ax - λx) ] = 0             微分


xᵀ A x = xᵀ λ x                         同除以-2、展開、移項

     xᵀ A x
λ = ――――――――                            Rayleigh Quotient
      xᵀ x

虛擬特徵值宛如向量投影公式:Ax投影到x,求得投影量!分子是Ax與x兩者點積,分母是x長度平方。

Pseudo-eigenvector【目前稱作Rayleigh Quotient導數】

有些矩陣不存在明確的特徵向量,只能擁有虛擬的、近似的特徵向量。如何得到近似的特徵向量呢?利用微分的思維,嘗試求得虛擬特徵值的導數。

微分,就是變化程度。一次微分等於零的地方,就是沒有變化的地方。虛擬特徵值沒有變化的地方,就是虛擬特徵向量。

限制向量長度不為零,避免得到沒有討論意義的虛擬特徵向量。

∂     xᵀ A x
―― [ ―――――――― ] = 0  and  ‖x‖² = xᵀ x ≠ 0   特徵向量長度不為零
∂x     xᵀ x

 (A + Aᵀ) x     (xᵀ A x) 2x
―――――――――――― - ――――――――――――― = 0    分式微分
    xᵀ x          (xᵀ x)²

                xᵀ A x 
(A + Aᵀ) x = 2 ―――――――― x           移項,同乘以 xᵀ x,重新整理
                 xᵀ x

(A + Aᵀ) x = 2 λ x                  虛擬特徵值

 A + Aᵀ
――――――― x = λ x                     移項,形成特徵向量的格式
   2

虛擬特徵向量即是(A+Aᵀ)/2的特徵向量。【尚待確認】

我不清楚(A+Aᵀ)/2有何功效,只知道它叫symmetric part,姑且略過吧。

特徵向量演算法(Rayleigh-Ritz Method)

重複處理一件事,計算學家弄成迴圈,數學家弄成矩陣。

大量向量,由左到右併成矩陣X。大量虛擬特徵值,由左到右併成對角線矩陣Λ。一口氣求得大量虛擬特徵值。

對整個矩陣微分,限制分母是1,以利微分。

                  2               T
minimize ‖AX - ΛX‖  , subject to X X = I  (X is orthonormal)

     T   
Λ = X A X

XᵀAX的計算結果,通常不是對角線矩陣,必須再求特徵值。

一、隨機生成一組正規正交基底X。
二、計算XᵀAX。
三、求特徵值們:求得XᵀAX的特徵值。
四、求特徵向量們:每一個特徵值,分別解Ax = λx。

畫蛇添足。與其求XᵀAX的特徵值,不如直接求A的特徵值。

沒人用這種方法計算特徵值、特徵向量。主要用途是挑選特定幾個向量作為X,估計特定小空間的特徵值。

Eigenbasis (Vectorization)

本章主角是特徵分解(宏觀視角)

矩陣向量化【尚無正式名稱】

函數向量化:數值併成向量。輸入數值們從上往下併成輸入向量,輸出數值們從上往下併成輸出向量。

{ y₁ = f(x₁)        [y₁]      [x₁]
{ y₂ = f(x₂)  ―――→  [y₂] = f( [x₂] )  ,  y⃗ = f(x⃗)
{ y₃ = f(x₃)        [y₃]      [x₃]

線性函數向量化:向量併成矩陣。輸入向量從左到右併成輸入矩陣,輸出向量從左到右併成輸出矩陣。

{ y₁ = Fx₁
{ y₂ = Fx₂  ―――→  Y = FX
{ y₃ = Fx₃
[ |  ]   [       ] [ |  ]
[ y₁ ] = [   F   ] [ x₁ ]
[ |  ]   [       ] [ |  ]

[ |  ]   [       ] [ |  ]        [ |  |  |  ]   [       ] [ |  |  |  ]
[ y₂ ] = [   F   ] [ x₂ ]  ―――→  [ y₁ y₂ y₃ ] = [   F   ] [ x₁ x₂ x₃ ]
[ |  ]   [       ] [ |  ]        [ |  |  |  ]   [       ] [ |  |  |  ]

[ |  ]   [       ] [ |  ]
[ y₃ ] = [   F   ] [ x₃ ]
[ |  ]   [       ] [ |  ]

Eigendecomposition(Diagonalization)

Ax = λx,λ是數值。亦可寫成Ax = xλ,λ是1×1矩陣。

當特徵向量恰好N種,一口氣考慮所有特徵向量、特徵值。特徵向量們併成矩陣E,特徵值們併成矩陣Λ,得到AE = EΛ。

移項得到A = EΛE⁻¹,稱做「特徵分解」或「對角化」。

Λ是縮放矩陣。對角線是特徵值,其餘元素是0。

                                                     -1
[  4 -1  0 ]   [ |  |  |  ] [ λ₁ 0  0  ] [ |  |  |  ]
[  0  5 -2 ] = [ v₁ v₂ v₃ ] [ 0  λ₂ 0  ] [ v₁ v₂ v₃ ]
[ -3  9 -3 ]   [ |  |  |  ] [ 0  0  λ₃ ] [ |  |  |  ]
      A             E            Λ            E⁻¹
J = [3 0 0; 0 2 0; 0 0 1]; E = [1 1 1; 1 2 3; 1 3 6]; A = E * J * inverse(E)

當特徵向量恰好N種,就可以特徵分解。舉例來說,單位矩陣、旋轉矩陣、鏡射矩陣、縮放矩陣、投影矩陣可以特徵分解,歪斜矩陣、移位矩陣不可以特徵分解。

Jordan-Chevalley Decomposition

當特徵向量不足N種,事情比較複雜:一、補足成N種特徵向量,對應到N種特徵值。二、利用移位,消滅補足的特徵向量。謹慎選擇特徵向量的長度。三、縮放矩陣Λ、移位矩陣S,相加成矩陣J,得到AE = EJ。

移項得到A = EJE⁻¹,稱做「喬登分解」。

J稱做「喬登標準型」,縮放矩陣Λ加上移位矩陣S。對角線是特徵值。次對角線只有0或1,一個1用來消滅一個特徵向量。

                                                    -1
[ 1  1 -2 ]   [ |  |  |  ] [ λ₁ 1  0  ] [ |  |  |  ]
[ 0  1  0 ] = [ v₁ v₂ v₃ ] [ 0  λ₂ 0  ] [ v₁ v₂ v₃ ]
[ 0  0  1 ]   [ |  |  |  ] [ 0  0  λ₃ ] [ |  |  |  ]
     A             E            J            E⁻¹
J = [1 1 0; 0 1 0; 0 0 1]; E = [1 1 1; 0 1 2; 0 0 1]; A = E * J * inverse(E)

數學家證明任意矩陣都可以喬登分解。此處省略證明。

特徵值矩陣Λ、喬登標準型J,只有唯一一種。特徵基底E,通常有許多種;舉例來說,相同特徵值,乘上排列矩陣,交換次序,仍是正解。

可對角化(存在N種特徵向量):已有演算法,我沒有學會。
特徵分解(找出N種特徵向量):已有演算法,後續章節陸續介紹。
喬登分解(補足N種特徵向量):尚無演算法。

Eigenbasis (Vectorization)

本章主角是特徵分解(微觀視角)

矩陣向量化【尚無正式名稱】

另一種截然不同的定義:矩陣拆成向量。

[ |  |  |  ]
[ v₁ v₂ v₃ ]  ―――→  {v₁ , v₂ , v₃}
[ |  |  |  ]

Eigendecomposition

以座標軸的觀點來重新看待特徵分解。

當輸入向量與特徵向量的方向相同,那麼輸出向量就是輸入向量乘上特徵值,長度伸縮,方向不變。

當輸入向量與特徵向量的方向不同,那麼可以運用分量的概念:Ax = A(x₁+x₂) = Ax₁ + Ax₂。輸入向量,在特徵向量上面的分量,分別乘上特徵值,最後合而為一,得到輸出向量。

拆成三個步驟,嘗試改成矩陣:

一、「輸入向量,在特徵向量上面的分量」:套用反矩陣,座標軸是特徵向量。
二、「各個分量分別按照特徵值來縮放」:套用縮放矩陣,縮放比例是特徵值。
三、「各個分量合而為一,得到輸出向量」:套用矩陣,座標軸是特徵向量。

矩陣連乘要從右往左乘:

                                                     -1
[  4 -1  0 ]   [ |  |  |  ] [ λ₁ 0  0  ] [ |  |  |  ]
[  0  5 -2 ] = [ v₁ v₂ v₃ ] [ 0  λ₂ 0  ] [ v₁ v₂ v₃ ]
[ -3  9 -3 ]   [ |  |  |  ] [ 0  0  λ₃ ] [ |  |  |  ]
      A             E            Λ            E⁻¹

特徵向量們,宛如座標軸,稱作「特徵基底eigenbasis」。

特徵分解A = EΛE⁻¹:分量、座標、合量。

喬登分解A = EJE⁻¹:分量、座標與移位、合量。

Linear Function的本質:縮放、旋轉、移位

一、主對角線:
 甲、特徵值的實部:縮放。
 乙、特徵值的虛部:旋轉。
二、次對角線:
 甲、元素0:無作用。
 乙、元素1:移位。

Eigenbasis (Transformation)

本章主角是相似矩陣:特徵值相同(嚴格來說是喬登標準型相同)

矩陣變換【尚無正式名稱】

本站文件「Transformation」,介紹了數據的變換。

此處介紹線性函數的變換。事情稍微複雜一點。

一、數據:此處是向量x。

二、數據變換:此處採用線性函數F,向量x變換成向量Fx。

三、為了還原數據,於是令變換函數F擁有反函數F⁻¹。

x ―――F―――> Fx
  <――F⁻¹――   

四、函數:此處是線性函數A。

五、為了對應運算,於是令函數A擁有對應運算B。

六、函數變換:函數A變換成函數B,推導得到B = FAF⁻¹。

  ―――F―――>
x <――F⁻¹―― Fx      { y = A(x)
|           |      { Fy = B(Fx)
A ―――?―――>  B     => FAx = BFx
↓           ↓     => FA = BF
y ―――F―――> Fy     => B = FAF⁻¹ , A = F⁻¹BF
  <――F⁻¹――

也有人改寫成A = F⁻¹BF。意義是繞一圈回來仍是A。矩陣連乘要從右往左讀。

|          |
| ―――F―――> | 
A          B      A = F⁻¹BF
| <――F⁻¹―― |
↓          ↓ 

Similar Matrices

方才的A與B稱作「相似矩陣」,功效一模一樣的矩陣。

特徵分解、喬登分解,都是矩陣變換。

特徵分解是矩陣變換:線性函數A,變換函數E⁻¹,對應運算Λ。A和Λ是相似矩陣,功效一模一樣!喬登分解亦然。

|          |
| ―――E⁻¹―> |
A          Λ      A = EΛE⁻¹
| <――E―――― |
↓          ↓

矩陣變換,特徵值不變。

相似矩陣,其喬登標準型相同(於是特徵值也相同)。

{ B = FAF⁻¹
{ A = EJE⁻¹
=> B = F(EJE⁻¹)F⁻¹ = (FE)J(E⁻¹F⁻¹) = (FE)J(FE)⁻¹

特徵向量演算法(QR Iteration)

Ak+1 = Qk⁻¹ Ak Qk    = Qk⁻¹ Qk Rk Qk = Rk Qk

以QR分解的Q⁻¹,實施矩陣變換。

採用Q⁻¹的好處:一、恰好能湊出R,精簡計算過程。二、正規正交矩陣,只會旋轉暨鏡射,不會縮放。矩陣變換之後,元素數值大小落在一定範圍,不會溢位。

不斷實施矩陣變換,碰碰運氣,看看會不會變成上三角矩陣。

相似矩陣,特徵值相同。原本矩陣的特徵值即是上三角矩陣的特徵值,而上三角矩陣的對角線即是特徵值。

遞推一次的時間複雜度是O(N³)。總時間複雜度為O(N³K),N是矩陣邊長,K是遞推次數。

特徵向量演算法(Hessenberg QR Iteration)

http://persson.berkeley.edu/18.335/lec14handout6pp.pdf

幾乎上三角矩陣Hessenberg Matrix:上三角、次對角線,除此以外的元素都是零。

事先變成幾乎上三角矩陣,爾後容易變成上三角矩陣:

一、以鏡射矩陣Householder Matrix,實施N-1次矩陣變換,變成幾乎上三角矩陣。遞推一次O(N²),總時間複雜度O(N³)。

二、以QR分解的正規正交矩陣Q⁻¹,實施K次矩陣變換,盡量變成上三角矩陣。遞推一次O(N²),總時間複雜度O(N²K)。

幾乎上三角矩陣,擁有很多零,得以節省計算時間:

甲、步驟二當中,矩陣一直都是幾乎上三角矩陣。幾乎上三角矩陣,乘以上三角矩陣R,仍然是幾乎上三角矩陣。

乙、步驟二當中,幾乎上三角矩陣的QR分解,採用軸面旋轉矩陣Givens Matrix,遞推一次的時間複雜度從O(N³)降為O(N²)。

步驟一有人稱做Hessenberg Decomposition:A = QHQ⁻¹。

步驟二有人稱做Schur Decomposition:A = QUQ⁻¹。

H是幾乎上三角矩陣,U是上三角矩陣,Q是正規正交矩陣。

Eigenbasis (Composition)

本章主角是可交換矩陣:特徵向量相同(嚴格來說是特徵空間相同)

矩陣複合

https://ccjou.wordpress.com/2009/03/14/

Commuting Matrices

「可交換矩陣」。AB = BA。複合順序隨意。特徵向量相同。

也許可以順便介紹一下廣義特徵值。

Transpose與Inverse的運算

想要順便講一下基本運算,但是還沒想到幾何證明方式。

(AB)ᵀ = BᵀAᵀ
(AB)⁻¹ = B⁻¹A⁻¹
(A⁻¹)ᵀ = (Aᵀ)⁻¹

Eigenbasis (Symmetry)

本章主角是對稱矩陣:特徵向量互相垂直,特徵值為實數

矩陣對稱(矩陣轉置)

複數的反面:複數共軛,得到共軛複數。

線性函數的反面:矩陣轉置,得到轉置矩陣。

注意到,矩陣轉置Aᵀ、矩陣變號-A,兩者不同。

Normal Matrix

「正規矩陣」。AᵀA = AAᵀ。A與Aᵀ可交換。

特徵向量互相垂直。真.正規正交矩陣。

名稱不太到位,讓人誤以為是一單位長度。

Symmetric Matrix

「對稱矩陣」。A = Aᵀ。

特徵向量互相垂直,特徵值是實數。真.縮放矩陣。

Skew-symmetric Matrix

「反對稱矩陣」。A = -Aᵀ。

特徵向量互相垂直,特徵值是虛數。真.旋轉矩陣。

Symmetric Decomposition【尚無專有名詞】

「對稱分解」。任意矩陣可以拆開成兩個矩陣相加:真.縮放矩陣、真.旋轉矩陣。

複數的實部與虛部:原本複數加減共軛複數再除以二。

函數的偶函數與奇函數:原本函數加減鏡射函數再除以二。

線性函數的的偶部與奇部:原本矩陣加減轉置矩陣再除以二。

A = S + R     where S = (A + Aᵀ) / 2   symmetric part
                    R = (A - Aᵀ) / 2   skew-symmetric part

眼尖的讀者應該注意到了,虛擬特徵向量源自偶部(A+Aᵀ)/2。

一階泰勒展開:平移、縮放、旋轉。

http://www.math.ku.edu/~lerner/LAnotes/Chapter22.pdf

Spectral Decomposition

「譜分解」。正規矩陣的特徵分解。

正規矩陣(包含了對稱矩陣、反對稱矩陣)一定可以特徵分解。其特徵向量互相垂直,再令特徵向量長度為一,如此一來特徵基底正規正交:反矩陣等於轉置矩陣。

AᵀA = AAᵀ
A = EΛE⁻¹ = EΛEᵀ

此分解可以視作「傅立葉轉換」的推廣,輸入與輸出從數列推廣成正規矩陣A與Λ,變換函數從傅立葉矩陣推廣成正規正交矩陣E。由於Λ可以視作頻譜,因而得名「譜分解」。

註:下圖的傅立葉矩陣Ei,j,次方無負號。正向傅立葉轉換視作除法、視作分量。逆向傅立葉轉換視作乘法、視作合量。

  |  forward   |     
  | ――――E⁻¹――→ |     A = EΛE⁻¹ = EΛEᵀ  (E⁻¹ = Eᵀ)
  A            Λ     example: Ei,j = ei⋅(2π/N)⋅i⋅j 
  | ←―――E――――― |
  ↓  backward  ↓
 time       frequency
domain       domain

備忘

想要順便講一下特殊觀念,但是還沒想到如何整合思路。

1. A and Aᵀ are similar.
2. An odd sized skew-symmetric matrix cannot be invertible.
3. skew-symmetric matrix A exhibits xᵀAx = 0.

Eigenbasis (Absolute Value)

本章主角是正定矩陣:特徵值為正數

矩陣絕對值平方(矩陣長度平方)

複數的長度平方:原本複數乘以共軛複數。

線性函數的長度平方:原本矩陣乘以轉置矩陣。

注意到,矩陣長度平方‖A‖² = AᵀA、矩陣平方A² = AA,兩者不同。

Positive Definite Matrix / Positive Semidefinite Matrix

「正定矩陣」。xᵀAx > 0,不討論x = 0。

「半正定矩陣」。xᵀAx ≥ 0,不討論x = 0。

這是仿照dot(x, Ax) > 0的概念,幾何意義是Ax投影到x上面,投影量總是大於0,無論哪種x。換句話說,向量經過線性變換,轉彎幅度少於±90˚,未達半個面。

眼尖的讀者應該注意到了,dot(x, Ax)再除以x的長度平方,就是虛擬特徵值。正定矩陣的虛擬特徵值恆正,於是特徵值恆正。

Symmetric Matrix

「對稱矩陣」。yᵀAx = xᵀAy。

這是仿照dot(y, Ax) = dot(x, Ay)的概念,幾何意義是兩個向量x與y,無論取哪一個實施線性變換,點積仍相同。

對稱矩陣可以特徵分解,表示成矩陣長度平方。

A = EΛE⁻¹ = EΛEᵀ = E√Λ√ΛEᵀ = E√Λᵀ√ΛEᵀ = (√ΛEᵀ)ᵀ(√ΛE) = ‖√ΛE‖²

這是仿照a = ‖kb‖²的概念,代數意義是長度平方、恆正。

Symmetric Positive Definite Matrix(SPD Matrix)

「對稱正定矩陣」。既對稱,又正定。

另一種等價的定義方式:A = MᵀM。

原本定義可以改寫成xᵀAx = xᵀMᵀMx = (Mx)ᵀMx = ‖Mx‖² > 0。代數意義是線性變換之後的長度的平方、恆正。

正定矩陣:特徵值皆是正數。對稱矩陣:特徵向量正規正交,特徵值皆是實數。對稱正定矩陣:同時具備兩者性質。

A-orthogonal

「矩陣正交」。yᵀAx = 0。xᵀAy = 0。兩式等價。

Ax與y互相垂直;x經過A變換之後,與y互相垂直。

知名範例:切線速度與加速度互相垂直;一次微分與二次微分互相垂直。

定義y與Ax的內積空間,A必須是對稱正定矩陣。內積空間開根號可以定義距離。

Length / Distance

l(x) = ‖x‖ = √xᵀx   |   d(x,y) = ‖x - y‖ = √(x-y)ᵀ(x-y)     
lᴍ(x) = ‖Mx‖        |   dᴍ(x,y) = ‖Mx - My‖ = ‖M(x - y)‖
      = √(Mx)ᵀMx    |           = √(M(x-y))ᵀM(x-y)
      = √xᵀMᵀMx     |           = √(x-y)ᵀMᵀM(x-y)
      = √xᵀAx       |           = √(x-y)ᵀA(x-y)

長度:元素平方和開根號。自己與自己的點積、再開根號。

線性變換之後的長度:恰是二次型開根號,且是對稱正定矩陣。

距離:相減之後的長度。

線性變換之後的距離:宛如二次型開根號,且是對稱正定矩陣。

Gram Matrix / Distance Matrix

「內積矩陣」。矩陣儲存兩兩點積,矩陣元素Aᵢⱼ是i點與j點的點積。Gram是人名。

當點座標視作向量、併作矩陣X,則內積矩陣是XᵀX。

「距離矩陣」。矩陣儲存兩兩距離,矩陣元素Aᵢⱼ是i點到j點的距離。

當點座標視作向量、併作矩陣X,則距離矩陣無法寫成矩陣運算,於是缺乏相關討論。

Polar Decomposition

把一個矩陣A分解成矩陣Q與矩陣P的乘積,A = QP。Q是互相垂直的單位向量(正規正交矩陣)。P是非負的縮放倍率(半正定矩陣)。

Q是旋轉暨鏡射,P是縮放。P設定為半正定矩陣,是為了把鏡射(縮放倍率為負值)的部分,硬是移動到Q。

如果矩陣A是實數矩陣,那麼P是對稱半正定矩陣。

比擬為極座標,Q與P宛如角度與長度,因而得名「極分解」。

Eigenbasis (Power)

本章主角是線性動態系統(特徵分解的應用)

矩陣次方

藉由特徵分解、喬登分解,矩陣次方化作特徵值次方。

A  = EΛE⁻¹
A² = EΛE⁻¹EΛE⁻¹ = EΛ²E⁻¹
A³ = EΛE⁻¹EΛE⁻¹EΛE⁻¹ = EΛ³E⁻¹

特徵值矩陣Λ的次方,就是對角線元素們的次方。

喬登標準型J的次方,請參考:

https://math.stackexchange.com/questions/2198671/

UVa 10753

Linear Function可以畫成箭矢圖

本站文件「Function」,介紹了「輸入有很多個變數,輸出只有一個變數」的函數,也畫出了函數圖形。

此處介紹「輸入有很多個變數,輸出有很多個變數」的線性函數,並且畫出函數圖形。

此處以ℝ² ⇨ ℝ²線性函數為例,輸入是兩個變數、輸出是兩個變數,畫在二維平面。為了節省紙張,改成畫在同一個二維平面。

一組輸入輸出仍可辨識,多組輸入輸出就看不清了。因此改成「從輸入往輸出的箭頭:輸出減輸入」。

窮舉所有輸入輸出,繪圖結果一片滿,看不出任何意義。因此改成「輸入等距取樣、保持間隔」。

線性函數是一種特別的函數,函數圖形有著一種難以言喻的整齊。有時是一致朝外,有時是一致螺旋。

這樣的函數圖形,可以用來解釋真實世界的物理現象!例如磁場、氣旋──不過這是後話了。先讓我們專注於線性函數吧!

Linear Function的本質:朝著目標向前進

整齊的原因是什麼呢?數學家已經初步解決了這個問題!

數學家猜測,所謂的整齊,也許是指:「大家有著共識,方向一致。」再進一步猜測:「這當中有沒有堪稱表率,讓大家群起效尤的輸入輸出呢?是不是有人一路以來始終如一,堅持走在正確的道路上?」於是數學家嘗試尋找:「有哪些輸入向量,套用線性函數之後,方向保持不變。」

套用線性函數。特徵值為實數則縮放,虛數則旋轉,零則消滅,負則翻轉。

反覆套用線性函數。特徵值絕對值小於1則趨近原點,等於1則保持不動,大於1則趨近無限遠,越小則縮短越快,越大則伸長越快。特徵值為正數則連貫移動,負數則來回翻轉、交互跳躍,而整體趨勢仍與正數相同。向量漸漸偏向特徵值絕對值最大的方向。

Trace-Determinant Diagram

以trace和determinant判斷流向。

特徵向量演算法(Power Iteration)

只能求出「絕對值最大的特徵值的特徵向量」。

反覆套用線性函數,向量朝向「絕對值最大的特徵值的特徵向量」的方向。就這麼簡單。

反覆套用線性函數,向量越來越長或越來越短,超出浮點數範圍。解法是隨時將向量長度縮放為1。這麼做不會影響方向。

時間複雜度O(N²K),N是矩陣邊長,K是遞推次數。

收斂速度,取決於最大、次大特徵值的絕對值的比值|λ₁|/|λ₂|。比值越大,收斂速度越快,遞推次數越少。

特徵向量演算法(Inverse Iteration)

有兩種手法可以調整特徵值大小:

一、矩陣對角線加上同一個值,則特徵值們也會加上同一個值:(A + aI)x = Ax + ax = λx + ax = (λ + a)x。

二、矩陣倒數(反矩陣),則特徵值們也會倒數。

猜測特徵值,再將該特徵值調整成無限大,成為最大的特徵值。如此一來Power Iteration就能得到其特徵向量。

eigenvalues of A: {λ₁, λ₂, λ₃, ...}   ( |λ₁| ≥ |λ₂| ≥ |λ₃| ≥ ... )
let B = (A - αI)⁻¹
eigenvalues of B: {1/(λ₁-α), 1/(λ₂-α), 1/(λ₃-α), ...}

α猜得準,足夠靠近λᵢ,讓1/(λᵢ-α)很大,成為B的絕對值最大的特徵值。
此時B套用Power Iteration即可得到1/(λᵢ-α)的特徵向量,進而算出λᵢ。

xk+1 = B xk = (A - αI)⁻¹ xk

錦上添花,可以使用LU Decomposition加速。遞推一次的時間複雜度從O(N³)降為O(N²)。

xk+1 = (A - αI)⁻¹ xk
(A - αI) xk+1 = xk
find LU decomposition of (A - αI)

然而特徵值該怎麼猜呢?你還記得虛擬特徵值嗎?

特徵向量演算法(Rayleigh Iteration)

每一步以Rayleigh Quotient重新估計特徵值。

αk = (xkᵀ A xk) / (xkᵀ xk)
xk+1 = B xk = (A - αkI)⁻¹ xk

遺珠之憾,不能使用LU Decomposition加速。遞推一次的時間複雜度為O(N³)。

然而初始向量該怎麼猜呢?我也不知道,嘻嘻。

【查無專有名詞】

反覆套用線性函數,有時收斂至某處,有時發散至無限遠,有時不斷繞圈。端看起點在哪裡。

若已知特徵值、初始向量,則可以判斷起始向量何去何從。

A = [ a  b ]   p₀ = [ x₁ ]   p₁ = [ y₁ ]
    [ c  d ]        [ x₂ ]        [ y₂ ]

eigenvalues of A: {λ₁, λ₂}     ( |λ₁| ≥ |λ₂| )

考慮A p₀ = p₁的過程,觀察特徵向量的影響力。

解  [  1  1 ] [ m₁ ] = [ x₁ ] = [ x₁        ]     --> p₀
    [ λ₁ λ₂ ] [ m₂ ]   [ y₁ ]   [ ax₁ + bx₂ ]     --> A p₀ = p₁

    [x₁] 與 [y₁] 在兩個特徵向量上面的分量,座標是 m₁ m₂。
    [0 ]    [0 ]

解  [  1  1 ] [ n₁ ] = [ x₂ ] = [ x₂        ]     --> p₀
    [ λ₁ λ₂ ] [ n₂ ]   [ y₂ ]   [ cx₁ + dx₂ ]     --> A p₀ = p₁

    [0 ] 與 [0 ] 在兩個特徵向量上面的分量,座標是 n₁ n₂。
    [x₂]    [y₂]

因為最後一定是朝向eigenvalue絕對值最大的eigenvector方向,
所以要判斷 x₁ 最終朝向哪個方向,只需看 m₁ 的正負號。
所以要判斷 x₂ 最終朝向哪個方向,只需看 n₁ 的正負號。

UVa 720

Eigenbasis (Root)

本章主角是奇異值分解(特徵分解的推廣)

矩陣根號

矩陣平方根:

A = EΛE⁻¹ = E√Λ√ΛE⁻¹ = E√ΛE⁻¹E√ΛE⁻¹ = (E√ΛE⁻¹)²
√A = E√ΛE⁻¹

矩陣立方根:

A = EΛE⁻¹ = E∛Λ∛Λ∛ΛE⁻¹ = E∛ΛE⁻¹E∛ΛE⁻¹E∛ΛE⁻¹ = (E∛ΛE⁻¹)³
∛A = E∛ΛE⁻¹

總之硬湊就對了!

特徵值矩陣Λ的根號,就是對角線元素們的根號。

喬登標準型J的根號,請參考:

https://math.stackexchange.com/questions/2659611/

Singular Value Decomposition(SVD)

無法特徵分解的矩陣,可以先平方再開根號,硬是分解。

大家不使用平方A²,而是使用內積AᵀA、外積AAᵀ:

一、兩者都是對稱矩陣:特徵向量正規正交、特徵值是實數。

二、兩者都是正定矩陣:特徵值是正數。

AᵀA = VΛVᵀ = VΣᵀΣVᵀ = VΣᵀUᵀUΣVᵀ = (UΣVᵀ)ᵀ(UΣVᵀ)
AAᵀ = UΛUᵀ = UΣΣᵀUᵀ = UΣVᵀVΣᵀUᵀ = (UΣVᵀ)(UΣVᵀ)ᵀ
A = UΣVᵀ     (let Λ = ΣᵀΣ = ΣΣᵀ = Σ², Σ = √Λ )

硬湊出A = UΣVᵀ,稱做「奇異值分解」。

U是AAᵀ特徵向量,V是AᵀA特徵向量,稱做「奇異向量」。

Σ是AAᵀ亦可說是AᵀA的特徵值開根號,稱作「奇異值」。

名稱非常奇異,應該是古代數學家非常奇異的緣故。

無論哪種矩陣,旋轉矩陣(虛數特徵向量)、歪斜矩陣(缺少特徵向量)、不是方陣(沒有特徵向量),通通可以奇異值分解,得到實數奇異向量、實數奇異值。超級歡樂!

「奇異值分解」好比「複數取絕對值」。複數,先共軛相乘再開根號,變成了實數。複數特徵值,先內積外積再開根號,變成了實數奇異值。

奇異值分解演算法

大可不必預先計算AᵀA和AAᵀ。

http://www.cs.utexas.edu/users/inderjit/public_papers/HLA_SVD.pdf

Eigenbasis (Polynomial)

本章主角是特徵方程式

矩陣多項式

https://en.wikipedia.org/wiki/Matrix_polynomial

多項式,變數x原本是實數(複數),現在改成實數矩陣(複數矩陣)。

Cayley-Hamilton Theorem

https://en.wikipedia.org/wiki/Cayley–Hamilton_theorem

一個矩陣A的特徵多項式,變數本來是特徵值λ,現在改成矩陣A,結果仍是零。

一、考慮特徵分解Aᵏ = EΛᵏE⁻¹。多項式每一項使用了相同的特徵基底E,可以提項出來,乘在括號外面。

特徵值們併成對角線矩陣,一口氣考慮所有特徵值。特徵多項式變成矩陣多項式,再補上特徵基底,即得此定理。

二、考慮喬登分解Aᵏ = EJᵏE⁻¹。Jᵏ每個元素分別處理即可。

Krylov Subspace

https://en.wikipedia.org/wiki/Krylov_subspace

Cayley-Hamilton theorem:
(A - λ₁I) (A - λ₂I) ... (A - λₙI) = 0 
c₀A⁰ + c₁A¹ + ... + cₙAⁿ = 0            展開
c₀A⁻¹ + c₁A⁰ + ... + cₙAⁿ⁻¹ = 0         同乘A⁻¹
A⁻¹ = (-c₁/c₀)A⁰ + ... + (-cₙ/c₀)Aⁿ⁻¹   移項
也就是說,A⁻¹是A⁰...Aⁿ⁻¹的線性組合,只有唯一解,A⁻¹的維度是n。

Krylov subspace:
Ax = b  =>  x = A⁻¹b  =>  x = (-c₁/c₀)A⁰b + ... + (-cₙ/c₀)Aⁿ⁻¹b
Krylov(A, b) = span(A⁰b, A¹b, ... , Aⁿ⁻¹b)

特徵向量演算法(Arnoldi Iteration)

https://en.wikipedia.org/wiki/Arnoldi_iteration

Eigenbasis (Residue)

本章主角不知從何講起

矩陣餘數

我還沒搞懂,大家自己揣摩吧。

Jordan-Chevalley Decomposition

A = S + N where S and N commute
S is semisimple (complex diagonalizable)
N is nilpotent
特徵基底:整數x
主對角線矩陣(縮放暨旋轉):倍率c
上對角線矩陣(移位):餘數r
喬登分解:n = cx + r
可交換:互質
( (A - λI) + λI )
  ^^^^^^^^   ^^
  nilpotent  diagonal

如何換基底  換到左邊剛好變成 shift matrix   目前沒有演算法

Nilpotent Matrix / Semisimple Matrix

「冪零矩陣」。特徵值皆零。對角線皆零、上三角非零。

「半單矩陣」。特徵值皆異。最小多項式不含重根。

A matrix is diagonalizable over C
iff its minimal polynomial has distinct roots.
雖然特徵空間以外的空間,可以隨便找基底,然後對應的倍率設成零。
但是冪零矩陣,特徵值矩陣的對角線都是零,怎麼乘都乘不出上三角元素。

Nilpotent Matrix / Unipotent Matrix

「冪零矩陣」。Aᵏ = 0。特徵值都是0。不可逆。

「冪么矩陣」。(A - I)ᵏ = 0。特徵值都是1。可逆。

兩者皆不可對角化(除非是零矩陣、單位矩陣)。

Nilpotent Matrix / Permutation Matrix

「冪零矩陣」。Aᵏ = 0。

「排列矩陣」。Aᵏ = I。

冪零矩陣不含循環節,於是消滅座標軸。N步之後座標軸必盡數消滅。

排列矩陣都是循環節,於是不消滅座標軸。大家各自自轉,總有一天(最小公倍數)回到原點。

也有同時擁有兩者特性的矩陣。例如設計一種分塊矩陣,一部分冪零、一部分排列。

Idempotent Matrix

「冪等矩陣」。A² = A。特徵值都是0或1。可對角化。

鏡射矩陣相乘,等同向量角度相加,等同旋轉。

3 shear matrix = 1 rotation matrix.
http://www.matrix67.com/blog/archives/5453

Unimodular Matrix

integer matrix
https://math.stackexchange.com/questions/64461/

Companion Matrix

Cayley-Hamilton Theorem:矩陣多項式的根,就是特徵值!

Companion Matrix:多項式的係數與變數,化作矩陣與輸入向量。多項式的根,化作矩陣的特徵值。

特徵多項式就是原本多項式。

特徵向量是(λ⁰, λ¹, ... , λⁿ⁻¹)。

Eigenbasis綜合結論

特殊的定理

eigenvalue的乘積是determinant。

eigenvalue皆不為零則有inverse。

eigen(QA) ≠ eigen(A)。任意矩陣經過正規正交矩陣變換,特徵向量和特徵值都會改變。除非遇到特例。

eigen(AB) ≠ eigen(A) eigen(B)。矩陣複合,那就改變更多。除非遇到特例。

eigenvector(A²) = eigenvector(A)。連續變換兩次,特徵向量一樣,特徵值連乘兩次。

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

eigenvalue(Aᵀ) = eigenvalue(A)。轉置矩陣,特徵向量改變,但是特徵值一樣。我想不出直觀的解釋方式。

特殊的矩陣

(複數版本)么正矩陣unitary matrix:特徵向量形成么正矩陣,特徵值的絕對值都是1。

(實數版本)正規正交矩陣orthonormal matrix:特徵向量形成正規正交矩陣,特徵值的絕對值都是1。注意到特徵值可為複數,例如旋轉矩陣。

    unitary matrix A : Aᴴ = A⁻¹
orthonormal matrix A : Aᵀ = A⁻¹

(複數版本)共軛對稱矩陣Hermitian matrix:特徵向量形成么正矩陣,特徵值都是實數。

(實數版本)對稱矩陣symmetric matrix:特徵向量形成正規正交矩陣,特徵值都是實數。

Hermitian matrix A : Aᴴ = A
symmetric matrix A : Aᵀ = A

(複數版本)反共軛對稱矩陣skew-Hermitian matrix:特徵向量形成么正矩陣,特徵值都是虛數。

(實數版本)反對稱矩陣skew-symmetric matrix:特徵向量形成正規正交矩陣,特徵值都是虛數。

skew-Hermitian matrix A : Aᴴ = -A
skew-symmetric matrix A : Aᵀ = -A

正規矩陣normal matrix:特徵向量形成么正矩陣。

normal matrix A : Aᴴ A = A Aᴴ

半正定矩陣positive semidefinite matrix:特徵值都是正數或零。

正定矩陣positive definite matrix:特徵值都是正數。

positive semidefinite matrix A : xᴴAx ≥ 0
    positive definite matrix A : xᴴAx > 0 when x ≠ 0
symmetric positive semidefinite matrix A : A = Mᴴ M
    symmetric positive definite matrix A : A = Mᴴ M and M⁻¹ exists

可交換矩陣commuting matrices:特徵向量相同。

commuting matrices A and B : AB = BA

相似矩陣similar matrices:特徵值相同。這是單向推論。例外是單位矩陣和歪斜矩陣,特徵值都是兩個1,但是不相似。

similar matrices A and B : A = M⁻¹ B M

對角線矩陣diagonal matrix:特徵向量即是矩陣本身,特徵值即是對角線。這是單向推論。

diagonal matrix A : Ai,j = 0 when i ≠ j

三角矩陣triangular matrix:特徵值即是對角線。這是單向推論。

upper triangular matrix A : Ai,j = 0 when i > j
lower triangular matrix A : Ai,j = 0 when i < j

特殊的分解

特徵分解:特徵向量矩陣(合量).特徵值矩陣(座標).特徵向量矩陣的反矩陣(分量)。

A = E Λ E⁻¹

喬登分解:半單矩陣(倍數)+冪零矩陣(餘數)。

A = M + N     where MN = NM    (commuting)
                    M  = EΛE⁻¹ (semisimple) (diagonalizable)
                    Nᵏ = 0     (nilpotent)

奇異值分解:內積與外積的特徵分解,融合之後開根號。

A = U Σ Vᵀ    where AᵀA = VΛVᵀ
                    AAᵀ = UΛUᵀ
                    Λ = ΣΣᵀ = ΣᵀΣ = Σ²

對稱分解:對稱矩陣(真.縮放)+反對稱矩陣(真.旋轉)。

A = S + R     where S = (A + Aᵀ) / 2
                    R = (A - Aᵀ) / 2

極分解:正規正交矩陣(旋轉翻轉).正定矩陣(縮放)。

A = Q P

幾何意義

對角線   =縮放/鏡射
正規正交  =旋轉/鏡射(兩鏡射=一旋轉)
次對角線  =移位
可逆    =N維
特徵值無零 =可逆
特徵值實數 =特徵基底縮放/鏡射
特徵值虛數 =特徵基底旋轉/鏡射
特徵值負號 =特徵基底鏡射
可對角化  =特徵基底N維
可交換   =特徵基底相同
正規    =特徵基底垂直
對稱    =特徵基底垂直、特徵值實數
反對稱   =特徵基底垂直、特徵值虛數
轉置    =投影(測量向量長度?)
三角/冪零  =歪斜(改變基底夾角?)

複數矩陣  =特徵基底N維縮放旋轉歪斜        喬登分解
複數可對角化=特徵基底N維縮放旋轉          特徵分解
實數可對角化=特徵基底N維縮放            特徵分解

實數矩陣=正規正交.喬登標準型.正規正交       喬登分解
實數矩陣=正規正交.對角線.正規正交         特徵分解
實數矩陣=正規正交.實數對稱半正定          極分解
實數矩陣=正規正交.上三角              QR分解(N次鏡射)
實數矩陣=下三角.上三角               LU分解(N次歪斜)

複數矩陣=特徵正交基底縮放+特徵正交基底旋轉     對稱分解
實數矩陣=特徵正交基底剛體旋轉.特徵正交基底正向縮放 極分解

Representation

Representation

先前介紹一個向量的變換,現在介紹大量向量的變換。

本篇文章從線性函數的角度,簡單介紹一次。順便藉此機會,讓讀者更加瞭解線性函數的功效。之後於「Representation」章節將詳細介紹。

Principal Component Analysis

「主成分分析」。大量向量X實施變換,讓橫條們正規正交。

奇異值分解X = UΣVᵀ。左端逐個移項Σ⁻¹UᵀX = Vᵀ。變換矩陣Σ⁻¹Uᵀ,乘在X的左邊;變換結果Vᵀ,橫條們正規正交。

下圖把大量向量X畫成座標點。

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))

Independent Component Analysis

「獨立成分分析」。大量向量X實施變換,讓直條們正規正交。

奇異值分解X = UΣVᵀ。右端逐個移項XVΣ⁻¹ = U。變換矩陣VΣ⁻¹,乘在X的右邊;變換結果U,直條們正規正交。

下圖把大量向量X畫成座標點。

C = X' * X; [E D] = eig(C); Y = X * E * inv(sqrt(D));

Principal Component Pursuit

「主成分追蹤」不是線性函數!變換矩陣加在後面,讓變換矩陣是元素很少的矩陣(稀疏矩陣),讓變換之後是rank很小的矩陣。

目前充滿謎團。也不知道是否能夠仿效「位移」增加維度。

Linear Function

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 7   集合   --> 整數  (可以推廣至餘數 mod ɸ(7))
加法運算 --> 餘數乘法     加法運算 --> 整數加法
倍率運算 --> 餘數次方     乘法運算 --> 整數乘法

向量空間之加法運算的規定         (u = 2, v = 3, w = 4, a = 5, b = 6)
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(bv) = (ab)v              |  (2 ^ 6) ^ 5 ≡ 2 ^ (5 × 6)
6. a(u + v) = au + av         |  (2 × 3) ^ 5 ≡ (2 ^ 5) × (3 ^ 5)
7. (a + b)v = av + bv         |  3 ^ (5 + 6) ≡ (3 ^ 5) × (3 ^ 6)
8. 1v = v                     |  3 ^ 1 ≡ 3           符號1設定成整數1

Inner Product Space

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

內積空間真要取名的話也該叫做「加倍內空間」,不過這名稱有點拗口。

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

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

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

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

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

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

抽象化

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

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

Basis / Coordinate

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

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

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

vector space: V
element v of V: v ∈ V
basis of V: {v1, v2, ..., vN}
linear combination: v = c1v1 + c2v2 + ... + cNvN
coordinate of v: {c1, c2, ..., cN}

Axiom of Choice = Vector Space has Basis

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

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

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

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

Linear Function廣義版本

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

additive function:
                        additive
y1 + y2 = f(x1) + f(x2) ======== f(x1 + x2)

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

線性函數與直線無關。取名線性是因為古人沒有考慮清楚。真要取名的話也該叫做「加倍性函數」,不過這名稱有點拗口。

為了迎合定義、為了能夠運算,輸入輸出必須是向量空間。

廣義版本的新功能

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

例如微積分的極限運算lim、機率論的期望值運算E[]。

廣義版本的功效

linear function f: V -> W
basis(V) = {v1, v2, ..., vN}   coordinate(v) = {c1, c2, ..., cN}
basis(W) = {w1, w2, ..., wN}   coordinate(w) = ???

linear combination:
v = c1v1 + c2v2 + ... + cNvN

linear function:
w = f(v)
w = f(c1v1 + c2v2 + ... + cNvN)
w = c1 f(v1) + c2 f(v2) + ... + cN f(vN)
w = c1   w1  + c2   w2  + ... + cN   wN

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

線性函數有什麼功效呢?輸入形成座標系統,輸出也形成座標系統。輸入輸出一一對應,座標一一相等!

w = f(v)
coordinate(v) = {c1, c2, ..., cN}
coordinate(w) = {c1, c2, ..., cN}

廣義版本的特色

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

Change of Basis / Similar Matrices

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

輸入輸出的座標軸,恰好是相似矩陣。

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

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

https://ccjou.wordpress.com/2009/10/09/基底變換/

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

Linearization

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

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

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

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

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

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

Matrix

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

linear combination c1v1 + c2v2 + ... + cNvN
[ | ]   [  |  |  |      | ] [ | ]
[ v ] = [ v1 v2 v3 ... vN ] [ c ]
[ | ]   [  |  |  |      | ] [ | ]

linear combination c1w1 + c2w2 + ... + cNwN
[ | ]   [  |  |  |      | ] [ | ]
[ w ] = [ w1 w2 w3 ... wN ] [ c ]
[ | ]   [  |  |  |      | ] [ | ]

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

linear function f: V -> W
[ | ]   [   |     |     |         |  ] [ | ]   [  |  |  |      | ] [ | ]
[ w ] = [ f(v1) f(v2) f(v3) ... f(vN)] [ c ] = [ w1 w2 w3 ... wN ] [ c ]
[ | ]   [   |     |     |         |  ] [ | ]   [  |  |  |      | ] [ | ]

狹義版本是特例:輸入的座標軸v1...vN恰好是單位矩陣I。