李宏毅_Linear Algebra Lecture 26: Diagonalization

tags: Hung-yi Lee NTU Linear Algebra Lecture

課程撥放清單

Linear Algebra Lecture 26: Diagonalization

課程連結

Outline

課程說明，部份的矩陣可以執行diagonalization這件事，所謂的diagonalization就是指，

$A=PD{P}^{-1}$，可以將matrix-

$A$拆解成

$PD{P}^{-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=PD{P}^{-1}$
• $A^2=P{D}^2{P}^{-1}=0$
• 左右兩邊分別乘上
  $P^{-1},P$消去，因此得到
  $D^2=0$
• $D^2=0\to D=0$
• 造成矛盾，因為
  $D$應該是diagonal matrix，如果
  $D=0$則
  $A=0$，但
  $A\ne 0$

Diagonalizable

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

假設，matrix-

$A$是diagonalizable，則：

• $A=PD{P}^{-1}$，其中
  $P$是一個n維的向量，
  $D$是一個nxn的diagonal matrix
• 左右都乘上一個
  $P$，變為
  $AP=PD$
  • $AP=[A{p}_1\cdots A{p}_n]$
  • $PD=P[d_1{e}_1\cdots d_n{e}_n]=[P{d}_1{e}_1\cdots P{d}_n{e}_n]=[d_{1}P{e}_1\cdots d_{n}P{e}_n]=[d_1{p}_1\cdots d_n{p}_n]$
    • $e$為standard vector
    • $d_{1}P{e}_1$，
      $P$是vector，乘上standard vector-
      $e$就會變成該column的scalar，因此計算之後變為
      $d_1{p}_1$
• 我們知道，
  $AP=PD$，也就是
  $A{p}_1=d_1{p}_1\cdots A{p}_n=d_n{p}_n$，也就是
  $A{p}_i=d_i{p}_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_1{v}_1+c_2{v}_2+\cdots +c_{k-1}{v}_{k-1}$
• 假設
  $v_1{v}_{k-1}$是independent
• 利用eigenvector的性質調整數學式，即
  $A{v}_k=c_{1}A{v}_1+c_{2}A{v}_2+\cdots +c_{k-1}A{v}_{k-1}$，而依照eigenvector的性質，這個數學式又可以是
  ${\lambda }_k{v}_k=c_1{\lambda }_1{v}_1+c_2{\lambda }_2{v}_2+\cdots +c_{k-1}{\lambda }_{k-1}{v}_{k-1}$
• 將最原始的數學式中，左右各乘上
  ${\lambda }_k$，即
  ${\lambda }_k{v}_k=c_1{\lambda }_k{v}_1+c_2{\lambda }_k{v}_2+\cdots +c_{k-1}{\lambda }_k{v}_{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\le n$，而課程中說過，eigenspace的dimension-

$d_1$一定是小於等於

$m_1$，

$d_k$一定是小於等於

$m_k$，既然如此，

$m_1+m_2+m_k\le 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 =

$PD{P}^{-1}$

Application of Diagonalization

這邊說明對角化的應用。

我們已經知道$A =

$PD{P}^{-1}$，而對角化可以拿來解

$A^m$，因為

$A^m=P{D}^m{P}^{-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-t{I}_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次