# 李宏毅_Linear Algebra Lecture 25: Eigenvalues and Eigenvectors
###### tags: `Hung-yi Lee` `NTU` `Linear Algebra Lecture`
[課程撥放清單](https://www.youtube.com/playlist?list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW)
## Linear Algebra Lecture 25: Eigenvalues and Eigenvectors
[課程連結](https://www.youtube.com/watch?v=1RyHRIP8QGg&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=25)

課程會說明如何系統化的找出一個好的coordinate system
### Eigenvalues and Eigenvectors

如果有一個matrix-$A$、vector-$v$、scalar-$\lambda$，而$Av=\lambda v$，這意味著：
1. $v$為$A$的eigenvector
2. $v$對應的eigenvalue就是$\lambda$

有兩個重點
* matrix-$A$一定是nxn的matrix
* eigenvector並不考慮zero vector
### Eigenvalues and Eigenvectors

每一個matrix都對應一個linear function(linear opearator)-$T$，如果$T(v) = \lambda v$，則：
* $v$為$T$的eigenvector
* $v$對應的eigenvalue就是$\lambda$
* eigenvector並不考慮zero vector

### Eigenvalues and Eigenvectors

這是一個[Shear Transform](https://zh.wikipedia.org/zh-tw/%E9%94%99%E5%88%87)的案例說明：
* $T$只改變$x$座標，不改變$y$座標
* 點距離$x$軸愈遠，其變化愈大
* 藍色向量就是一個eigenvector，因為它帶入$T$之後還是自己，其eigenvalue=1
### Eigenvalues and Eigenvectors

假設有一個function，其功用就是對y=(1/2)x做reflection：
* 假設有一個vector-$b_1$就在這個函數上，那$T(b_1)=b_1$，這時候這個$b_1$就是eigenvector，其eigenvalue=1
* 假設有一個vector-$b_2$與函數垂直，那$T(b_2)=-b_2$，而$b_2$也是eigenvector，其eigenvalue=-1

### Eigenvalues and Eigenvectors

這個範例是將照片放大、縮小的例子。將每個pixel視為座標點，每個座標點都乘上2、或乘上0.5就可以達到放大、縮小的效果。

對Expansion與Compression而言，任意的vector都是eigenvector，但Expansion的eigenvalue為2，而Compression的eigenvalue為0.5。

### Eigenvalues and Eigenvectors

並非所有的nxn的matrix或linear operator都會有eigenvalues與eigenvectors。舉例來說，Rotation(旋轉)，它並不會是自己本身的n倍，任何位置旋轉之後都不會是自己的n倍，因此rotation這個linear operator不存在eigenvalues與eigenvectors。
### Eigenvalues and Eigenvectors

在給定eigenvalue的情況下該如何找出eigenvector?

Eigenvalues與Eigenvectors之間的一個關係：
* 每一個eigenvector都對應一個唯一的eigenvalue
* 但每一個eigenvalue可以對應無窮多的eigenvector

對應同一個eigenvalue的eigenvector是否為subspace?答案是否定的，因為稍早有提過，eigenvector是不存在zero vector。
### Eigenspace

假設我們知道matrix-A的eigenvalue-$\lambda$，找出所有對應$\lambda$的eigenvector：
* 定義：$Av=\lambda v$，即$Av - \lambda v 0$
* 調整：$Av - \lambda I_n v = 0$
* 提出$v$：$(A - \lambda I_n)v = 0$(matrix-A的對角線值減去$\lambda$)
* eigenvectors就是將這個式子的所有solution減去zero vector的集合
* 對應$\lambda$的eigenvector所成的集合就是$A - \lambda I_n$的null space扣掉zero vector，即$Null(A - \lambda I_n) - \left\{ 0 \right\}$
* $\lambda$的eigenspace就是$A - \lambda I_n$的null space + $\left\{ 0 \right\}$
* 並非所有eigenspace的vector都是eigenvector，因為eigenspace包含zero vector
* 課程中$\lambda$所對應的eigenspace就是所有對應到$\lambda$的eigenvectors再加上$\left\{ 0 \right\}$(zero vector)
### Check Eigenvalues

如何確定一個scalalr是否為eigenvalue：
* 這很簡單，只要確定eigenspace長什麼樣子，如果eigenspace只有zero vector，那它就一定不是，如果有著zero vector以外的東西存在，那它就是eigenvalue
* 可以判斷eigenspace的dimension，如果$Null(A - \lambda I_n) = 0$，那就代表它只存在zero vector，那就代表$\lambda$不是eigenvalue
* 這要用之前課程提過的檢查subspace的方法來確定，如果$A - \lambda I_n$的vector都是indenpendent，那就代表它的Null space只有zero vector
### Check Eigenvalues

這邊用範例說明如何檢查是否為eigenvalue：
* 3
* 首先計算$Null(A - 3 I_2)$，$A$對角線計算，其餘不變
* 空間中畫出，所有在線上的都是eigenvector
* 帶入$T$得證，3為matrix-$A$的eigenvalue
* 2
* 首先計算$Null(A + 2 I_2)$，$A$對角線計算，其餘不變
* 空間中畫出，所有在線上的都是eigenvector
* 帶入$T$得證，-2為matrix-$A$的eigenvalue
### Check Eigenvalues

這邊的問題是確認3是否為matrix-$B$的eigenvalue，如果是，那請找出它的eigenspace的basis：
* 首先計算$Null(B - 3 I_3)$，$B$對角線計算，其餘不變
* 檢查$B - 3 I_3$的null space有多大
* 確認column是否為dependent，因存在zero vector，因此為dependent，也因此其null space不會只有zero vector，因此3為$B$的eigenvalue
* 又或者可以利用determinant來確認，因為有一個row、column為0，因此其determinant=0，這意味著這個matrix是non-invertible，這種matrix的null space會包含zero vector以外的vector，因此3為$B$的eigenvalue
* 計算$B - 3 I_3$的RREF
* 寫出其parametric representation，得出其basis，(1, 0, 0; 0, 1, 1)，將這兩個vector做linear combination可以得到所有的eigenvector，記得扣掉zero vector
### Looking for Eigenvalues

剛才的問題是給定一個eigenvalue來確定是否為eigenvalue，現在是給出一個matrix，找出所有的eigenvalue。

假設某一個scalar-$t$為matrix-$A$的eigenvalue，那它會滿足幾個條件：
* 如果$t$是eigenvalue，那就存在一個向量-$v$(非zero vector)，其$Av = tv$
* 也就是$Av - tv = 0$，其中$v$(非zero vector)
* 也就是$v$乘上identity matrix，這不影響結果，即$(A - t I_n)v=0$，其中$v$(非zero vector)
* 也就是$(A - t I_n)v=0$要有多個解，因為最少會有一組zero的解
* 也就是$(A - t I_n)$的column為dependent
* 也就是$(A - t I_n)$是non-invertible
* 也就是det$(A - t I_n)=0$

所以我們只要解det$(A - t I_n)=0$就可以找到所有的eigenvalue
### Looking for Eigenvalues

上面給出一個範例，帶入公式，解determinant就可以得到$t=-3$或$t=5$，這邊我們發現到兩個特性：
1. 所有matrix的eigenvalues相乘會得到這個matrix的determinant
2. matrix的trace，即對角線值相加，會等於所有eigenvalues的和
### Looking for Eigenvalues

找出eigenvalues就可以找出它的eigenspace，舉例來說，假設我們已經確定-3就是eigenvalue，即$Ax=-3x$，其$(A + 3I)x = 0$的解即為eigenvalue=-3的eigenspace。

同理，當eigenvalue=5的時候，其$(A-5I)x = 0$的解即為eigenvalue=5的eigenspace
### Looking for Eigenvalues

範例是給定一個linear operator，找出這個linear operator的eigenvalue：
* 首先寫出這個linear operator的matrix-$A$
* 寫下$det(A-tI_n)=0$的數學式，展開之後就是將matrix-$A$的對角線都減$t$
* 計算其determinant，即$det(A - tI_n) = (-1 - t)^3$
* 得到$t = -1$為其解，即eigenvalue=-1
### Looking for Eigenvalues

範例說明的是，證明rotation是沒有eigenvalue：
* 寫下rotataion這個linear operator背後的matrix
* 寫下$det(A-tI_n)=0$的數學式，展開之後就是將matrix-$A$的對角線都減$t$
* 計算其determinant，即$t^2 + 1 = 0$
* 我們發現，這個數學式是沒有實數解的
* 得證，rotation是沒有eigenvalue，或稱沒有實數的eigenvalue，但是有虛數解，不過虛數超過課程範圍，不討論
### Characteristic Polynomial

稍早一連串範例所提的$det(A-tI_n)$的這個多項式，又稱為Characteristic Polynomial，而$det(A-tI_n)=0$則稱為Characteristic Equation。

要找出eigenvalue，就是找出characteristic polynomial的根(root)，或是找出characteristic equation的解。

### Characteristic Polynomial

在eigenvalue的章節中，RREF的作用並不大，由下面的特性說明。

Characteristic Polynomial的特性：
* matrix-A與其RREF-A的characteristic polynomials是不一樣的，因此也會有不一樣的eigen value
* 如果兩個matrix是similar，那它們就會有相同的characteristic polynomials，這意味著會有相同的eigenvalue(見簡報證明)
* 所謂的similar的matrix，即$B = P^{-1}AP$，當matrix$A$的左右乘上一個matrix-P與其inverse-$P^{-1}$會等於$B$的時候，則$A, B$為similar matrix

證明$det(B-tI) = dep(A-tI)$：
* 帶入$AB$之間的關係，即$B = P^{-1}AP$，得到$det(P^{-1}AP)$，而$tI$則帶入$P^{-1}(tI)P$，合併來看則為$det(B-tI) = det(P^{-1}AP - P^{-1}(tI)P)$
* 提出$P^{-1}$與$P$，得到$det(P^{-1}(A-tI)P)$
* determinant matrix相乘會等於先取determinant再相乘，即$det(P^{-1})det(a-tI)det(P)$
* $det(P^{-1})$與$det(P)$是可以消掉，相乘為1
* 得證$det(B-tI) = dep(A-tI)$

在說明coordinate system的時候提過similar，也就是同一個matrix在兩個不同的coordinate system下看待的結果，雖然看起來是兩個matrix，但其實是同一個。因此可以知道的是，一個matrix在不同的coordinate system下，它的eigenvalue是不變的，但eigenvector是會變的。
### Characteristic Polynomial

這邊繼續說明Characteristic Polynomial的特性：
* 假設你的matrix是nxn，其Characteristic Polynomial的order(degree)也會是n
* 這可以從$det(A-tI_n)$來看，以3x3矩陣為例，帶入公式可以發現，對角線一定會是一個未知系數乘上$t$的三次方，也就是n
* 一個nxn的矩陣會擁有多少個eigenvalue
* 我們已經知道，eigenvalue就是Characteristic Polynomial的root，一個order為n的Characteristic Polynomial，其root最多就是有n個。也就是一個nxn的matrix，其eigenvalue的數量一定小於等於n

### Characteristic Polynomial V.S. Eigenspace

對Characteristic Polynomial做因式分解(Factorization)，即$det(A-tI_n)=(t-\lambda_1)^{m_1}(t-\lambda_2)^{m_2}...(t-\lambda_k)^{m_k}(... ...)$，每一個$\lambda$都對應一個eigenvalue，每一個eigenvalue都對應一個eigenspace(dimension)，其中dimension一定會小於其multiplicity
### Characteristic Polynomial

這邊繼續說明Characteristic Polynomial的特性：
* 如果一個matrix為upper triangular(對角線以下為0的矩陣)或lower triangular，其Characteristic Polynomial就會單純的就是對角線相乘，因此其root即為對角線值，範例來看即為$a, b, c$