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

### Outline

課程說明，部份的矩陣可以執行diagonalization這件事，所謂的diagonalization就是指，$A = PDP^{-1}$，可以將matrix-$A$拆解成$PDP^{-1}$，其中$D$是一個nxn的diagonal matrix，而$P$是一個nxn的invertible matrix，這樣子的matrix稱為可對角化，也就是diagonalizable。

根據上一堂課複習到的silimar的定義，diagonalizable意謂著，$A, D$是similar，也就是$A$在另一個coordinate system下是比較簡單的一個存在，單純的就是一個diagonal matrix。

這就是diagonalization的妙用，可以將一個matrix轉為簡單的diagonal matrix。
### Diagonalizable

首先，並非所有的matrix都是可以被對角化，這可以利用反證法來證明：
* 假設，$A$是可對角化的，即$A=PDP^{-1}$
* $A^2 = PD^2P^{-1} = 0$
* 左右兩邊分別乘上$P^{-1}, P$消去，因此得到$D^2=0$
* $D^2 = 0 \rightarrow D = 0$
* 造成矛盾，因為$D$應該是diagonal matrix，如果$D=0$則$A=0$，但$A \neq 0$

### Diagonalizable

這邊說明對角化與eigenvector、eigenvalue之間的關係。

假設，matrix-$A$是diagonalizable，則：
* $A=PDP^{-1}$，其中$P$是一個n維的向量，$D$是一個nxn的diagonal matrix
* 左右都乘上一個$P$，變為$AP = PD$
* $AP = \left[ Ap_1 \cdots Ap_n \right]$
* $PD = P\left[ d_1e_1 \cdots d_ne_n \right] = \left[ Pd_1e_1 \cdots Pd_ne_n \right] = \left[ d_1Pe_1 \cdots d_nPe_n \right] = \left[ d_1p_1 \cdots d_np_n \right]$
* $e$為standard vector
* $d_1Pe_1$，$P$是vector，乘上standard vector-$e$就會變成該column的scalar，因此計算之後變為$d_1p_1$
* 我們知道，$AP=PD$，也就是$Ap_1=d_1p_1 \cdots Ap_n = d_np_n$，也就是$Ap_i=d_ip_i$，也就是說$P$就每一個column就是eigenvector，而$D$的值就是對應的eigenvalue
* 因為$P$是invertible，因此為independent
* 回憶上一堂課$Av = \lambda v$

### Diagonalizable

matrix-$A$是diagonalizable，則意味著：
* 我們可以找到n個eigenvector，而這n個eigenvector形成一個invertible matrix
* 有n個independent的eigenvectors
* 這n個independent的eigenvectors可以span整個$R^n$，也就是整個$R^n$的basis
### Diagonalizable

如何對角化matrix-$A$?
1. 找出n個independent的eigenvector
2. 每個eigenvector都會有相對應的eigenvalue，找到eigenvalue就找到$D$

### Diagonalizable

對應不同eigenvalue的eigenvector，它們之間是independent。假設我們將一個matrix-A的Characteristic Polynomial做因式分解，我們知道它有$k$個eigenvalues，而每一個eigenvalue都有一個eigenspace，背後都有一堆的eigenvector，這些eigenvector之間都是independent。也就是說，如果一個matrix有k個eigenvalue，那就代表你一定找的到k個eigenvector。

值得注意的是，同一個eigenspace取出兩個vector，它可能是independent也可能是dependent

### Diagonalizable

這邊利用反證說明不同的eigenvalue的eigenvector一定是independent：
* 假設，eigenvector是dependent(雖然課程中說明過它應該是independent)，這意味著可以找的到某一個vector-$v_k$，它是$v_1~v_{k-1}$的linear combination，則$v_k = c_1v_1 + c_2v_2 + \cdots + c_{k-1}v_{k-1}$
* 假設$v_1~v_{k-1}$是independent
* 利用eigenvector的性質調整數學式，即$Av_k = c_1Av_1 + c_2Av_2 + \cdots + c_{k-1}Av_{k-1}$，而依照eigenvector的性質，這個數學式又可以是$\lambda_kv_k = c_1\lambda_1v_1 + c_2\lambda_2v_2 + \cdots + c_{k-1}\lambda_{k-1}v_{k-1}$
* 將最原始的數學式中，左右各乘上$\lambda_k$，即$\lambda_kv_k = c_1\lambda_kv_1 + c_2\lambda_kv_2 + \cdots + c_{k-1}\lambda_kv_{k-1}$
* 兩個數學式相減，得到$0 = c_1(\lambda_1 - \lambda_k)v_1 + c_2(\lambda_2 - \lambda_k)v_2 + \cdots + c_{k-1}(\lambda_{k-1} - \lambda_k)v_{k-1}$
* 因為$v_1~v_m$是dependent，因此$c_1 ~ c_{k-1}$不全為0，可是$v_1~v_{k-1}$是independent，因此造成矛盾

### Diagonalizable

現在可以依據剛才所證明的，不同的eigenvalue的eigenvector一定是independent這件事來知道一個matrix是否可以被對角化：
* 寫出Characteristic Polynomial，找出eigenvalue，接著找出eigenvalue的eigenspace，再找出eigenspace的basis，也就是找出eigenspace最多的independent vector，假設它的dimension=3，那它最多的independent vector就是3
* 將所有的basis放在一起，它們一定是independent，如果matrix-$A$是一個nxn的matrix，且將所有的basis放在一起的vector set有n個vector，那這個matrix就可以被對角化

值得注意的是，這個vector set最多最多就是只會擁有n個vector，不可能超過，因為nxn的matrix-$A$，對應的$P$最多就是n維，在n維空間中你不可能找出超過n個independent的vector。另一個角度來看，Characteristic Polynomial的order(最高次方)就是n，因此$m_1 + m_2 + m_k \leq n$，而課程中說過，eigenspace的dimension-$d_1$一定是小於等於$m_1$，$d_k$一定是小於等於$m_k$，既然如此，$m_1 + m_2 + m_k \leq n$，那$d_1 + d_2 + \cdots + d_k$更是一定小於等於n，就不可能找出超過n個independent的eigenvector。
### Diagonalizable - Example

這邊用範例說明：
* 寫出Characteristic Polynomial，將對角線的值都-t，計算其determinant，得到$-(t+1)^2(t-3)$，因此這個matrix的eigenvalue是3、-1，如果有三個eigenvalue，那它一定可以被對角化，但只有兩個，雖然不一定可以被對角化，但不代表不能被對角化
* 找eigenvalue對應的eigenspace裡面有幾個independent vector
* 找3的null space，也就是$(A-3I_n)$的null space，得到其eigenspace的basis，因為$(t-3)$是1次方，因此它的dimension一定是小於等於1
* 找-1的null space，因為$(t+1)^2$是2次方，因此它對應的dimension一定是小於等於2，找出它的null space-$(A+I_n)$，確認其dimension為2
* 將得到的vector排程一個matrix，也就是$P$
* 將$P$對應的eigenvalue寫出來，也就是$D$，寫在對角線，因為$D$是一個diagonal matrix

另外，$P$的順序是可以調整的。不管如何，最終就是$A = $PDP^{-1}$
### Application of Diagonalization

這邊說明對角化的應用。

我們已經知道$A = $PDP^{-1}$，而對角化可以拿來解$A^m$，因為$A^m = PD^mP^{-1}$，這可以從紅字手寫上得到一個簡單的證明。

舉例來說，假設你的人生就是學習跟臉書，我們想知道，一直到m個時間點之後，你在各狀態的機率是多少：
* 假設，當你在學習的時候還會持續學習的機率是0.85，然後從學習跳到臉書的機率是0.15，從臉書再跳回學習的機率是0.03，而持續臉書的機率是0.97

如果我們想要計算你在m個時間點之後的狀態機率，那就必需要不斷的計算下去，但這很麻煩，因此我們可以利用對角化的概念來處理。
### Application of Diagonalization

處理流程：
1. 首先，將狀態之間的轉換機率寫成一個矩陣-$A$
2. 假設，出生的時候就是處於學習狀態
3. 將2的向量乘上1的矩陣，得到一個time step之後的向量
4. 將3得到的向量再乘上1的矩陣，得到下一個time step之後的向量
5. 不斷的計算

### Diagonalizable

對角化處理流程：
1. 首先寫下matrix-$A$的Characteristic Polynomial-$det(A-tI_2)$，得到它的determinant，$(t-0.82t)(t-1)$
2. 得到兩個eigenvalue，因此一定找的到兩個independent eigenvector，也因此一定可以對角化matrix-$A$
3. 列出null space-$A-0.82I_2$，也就是eigenvalue=0.82的eigenspace，計算其RREF得到eigenvector-$p_1$
4. 列出null space-$A-I_2$，也就是eigenvalue=1的eigenspace，計算其RREF得到eigenvector-$p_2$
5. 合併兩個vector得到$P$，依序寫下它的$D$

### Application of Diagonalization

已經可以成功的對角化$A$，將它連成m次，其實就是將$D$的對角線值做m次的計算。這邊特別注意到的是，將一個matrix滿足某些特性的時候，它的eigenvalue的最大值就會是1，這後續會有說明。

計算之後得到矩陣，其中$(0.82)^m$會趨近於0，因此忽略不看：
1. 如果你出生的時候是在學習的，(1, 0)，那你在未來會有1/6的機率在學習，5/6的機率在臉書
2. 如果你出生的時候是在臉書的，(0, 1)，那你的未來還是一樣不變

這個範例主要說明的是對角化可以應用在將matrix連成m次