2010年8月29日 星期日

[線性系統] 對角化 與 Eigenvalues and Eigenvectors

首先我們給出相關定義

============================
Definition (Eigenvalue and Eigenvector)
設 $A$ 為 $n \times n$ 方陣,若存在一非零向量 $x \in \mathbb{R}^n$ (or $\in \mathbb{C}^n$) 與 純量 $\lambda \in \mathbb{R}^1$ (or $\in \mathbb{C}^1$)滿足
\[
Ax = \lambda x
\]則我們稱 $\lambda$ 為 $A$ 的 特徵值 (eigenvalue) 且 $x$ 為 $A$對應於 $\lambda $ 的特徵向量(eigenvector)。
============================
Comments:
1. 上述定義中 $Ax = \lambda x$ 又稱 eigenvalue-eigenvector 關係: $( \lambda I - A)x =0$,注意! $0$ 為 零向量!!。
2. 若 $A$ 為 $n \times n$ 方陣,則我們稱下式
\[\det (\lambda I - A)\]為 $A$ 矩陣的 特徵多項式(characteristic polynomial) 且 $\det(\lambda I -A)=0$ 為特徵方程(characteristic equation)。

現在考慮 LTI 系統 (但無考慮外力 $u=0$) 以狀態空間表示
\[
\dot {x} = Ax,
\]其中 $x$ 為 $n \times 1$ 狀態向量,$A$ 為 $n \times n$ 常數矩陣。現在對上式取拉式轉換 且令初值為零,
\[sX\left( s \right) = AX\left( s \right) \Rightarrow \left( {sI - A} \right)X\left( s \right) = 0
\] 亦即對上述系統而言,其解特徵方程 (characteristic polynomial) 可寫為
\[
\det( s I - A) =0
\]且 特徵方程式的根 即為 eigenvalue。


對角化 (Diagonalization)

考慮  $A$ 為 $n$ 階方陣 ,且 $A$ 與 一個 對角矩陣(diagonal matrix) $ \Lambda$ 相似 (亦即有相同的 eigenvalue),則稱此 $A$ 矩陣為可對角化 (diagonalizable);亦即存在一個 non-singular transformation matrix $T$ 使得
\[
\Lambda = T^{-1}AT
\]

FACT: 若 $n$ 階方陣 $A$ 為可對角化(Diagonalizable),則必須具備 $n$個線性獨立的 eigenvector。
Proof: omitted
NOTE: $n$個線性獨立的 eigenvector 具有 $n$ 個對應的 相異 eigenvalue


由於矩陣的對角化可借助 eigenvalue 與 eigenvector 來達成,且依照 eigenvalue 的不同情況(共有三種情況)會有所各自不同的衍生討論,我們將各種情況總結如下:
  1. 矩陣 $A$ 具有 相異特徵值 (distinct eigenvalues)
  2. 矩陣 $A$ 具有 重複特徵值 (repeated eigenvalues)
  3. 矩陣 $A$ 具有 複數特徵值 (complex eigenvalues)

以下我們逐項討論:

Case I: 相異特徵值 (Distinct eigenvalues)
考慮  $A$ 為 $n \times n$ 方陣,其特性方程
\[
\det(\lambda_iI - A) =0, \; \forall i
\]且 $\lambda_1 \neq \lambda_2 \neq ... \neq \lambda_n$。那麼對於 第 i 個 eigenvalue $\lambda_i$而言,其對應的 eigenvector 定為 $v_i$,且滿足 eigenvalue-eigenvector 關係
\[({\lambda _i}I - A){v_i} = 0\]那麼對任意 $i$ 而言,我們有
\[({\lambda _i}I - A){v_i} = 0 \Rightarrow {\lambda _i}{v_i} = A{v_i}\]亦即
\[ \Rightarrow \left\{ \begin{array}{l}
{\lambda _1}{v_1} = A{v_1}\\
{\lambda _2}{v_2} = A{v_2}\\
 \vdots \\
{\lambda _n}{v_n} = A{v_n}
\end{array} \right.
\]現在將上述結果寫成矩陣形式:
\[\begin{array}{*{20}{l}}
{\left[ {\begin{array}{*{20}{c}}
{{\lambda _1}{v_1}}&{{\lambda _2}{v_2}}& \cdots &{{\lambda _n}{v_n}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{A{v_1}}&{A{v_2}}& \cdots &{A{v_n}}
\end{array}} \right]}\\
{ \Rightarrow \underbrace {\left[ {\begin{array}{*{20}{c}}
{{v_1}}&{{v_2}}& \cdots &{{v_n}}
\end{array}} \right]}_{n \times n}\underbrace {\left[ {\begin{array}{*{20}{c}}
{{\lambda _1}}&0& \cdots &0\\
0&{{\lambda _2}}&{}& \vdots \\
 \vdots &{}& \ddots &0\\
0& \cdots &0&{{\lambda _n}}
\end{array}} \right]}_{n \times n} = A\underbrace {\left[ {\begin{array}{*{20}{c}}
{{v_1}}&{{v_2}}& \cdots &{{v_n}}
\end{array}} \right]}_{n \times n}}
\end{array}\]令 $T: = \left[ {\begin{array}{*{20}{c}}
{{v_1}}&{{v_2}}& \cdots &{{v_n}}
\end{array}} \right]$ 且
\[
\Lambda := {\left[ {\begin{array}{*{20}{c}}
{{\lambda _1}}&0& \cdots &0\\
0&{{\lambda _2}}&{}& \vdots \\
 \vdots &{}& \ddots &0\\
0& \cdots &0&{{\lambda _n}}
\end{array}} \right]}
\]則我們有
\[\begin{array}{l}
T\Lambda  = AT \Rightarrow \Lambda  = {T^{ - 1}}AT
\end{array}\]若 $T$ 為 nonsingular (i.e., $T$ 有 $n$ 個線性獨立的 row or columns 亦即 eigenvectors 之間彼此線性獨立)。

那麼現在我們證明 $T$ 確實為 nonsingular matrix。
Proof
用歸納法:令 $n=2$ 對任意兩個 eigenvector $v_i, v_j$ 而言,我們要證明此兩者為線性獨立,亦即由線性獨立的定義,對下式
\[
\alpha_i v_i + \alpha_j v_j =0 \ \ \ \ (*)
\]其係數 $\alpha_i = \alpha_j =0$。

故現在觀察 $(*)$ 式,兩邊同乘 $(\lambda_i I - A)$
\[\begin{array}{l}
{\alpha _i}\underbrace {({\lambda _i}I - A){v_i}}_{ = 0\begin{array}{*{20}{c}}
{}
\end{array}by\begin{array}{*{20}{c}}
{}
\end{array}def.} + {\alpha _j}({\lambda _i}I - A){v_j} = 0\\
 \Rightarrow {\alpha _j}({\lambda _i}I - A){v_j} = 0\\
 \Rightarrow {\alpha _j}({\lambda _i}I - A - {\lambda _j}I + {\lambda _j}I){v_j} = 0\\
 \Rightarrow {\alpha _j}({\lambda _i}I - {\lambda _j}I + \left( {{\lambda _j}I - A} \right)){v_j} = 0\\
 \Rightarrow {\alpha _j}\left( {{\lambda _i}I - {\lambda _j}I} \right){v_j} + \underbrace {{\alpha _j}\left( {{\lambda _j}I - A} \right){v_j}}_{ = 0\begin{array}{*{20}{c}}
{}
\end{array}by\begin{array}{*{20}{c}}
{}
\end{array}def.} = 0\\
 \Rightarrow {\alpha _j}\left[ {\left( {{\lambda _i} - {\lambda _j}} \right)I} \right]{v_j} = 0
\end{array}\]又因為 $\lambda_i \neq \lambda_j$ (因為我們假設相異特徵值),且特徵向量 $ v_j \neq 0$ 故必然 $\alpha_j = 0$。
同理可推至 $n$個情況,這邊留給讀者自行證明。 $\square$


透過以上討論我們知道對相異 eigenvalue的情況必定存在 nonsingular matrix $T$ 使得 $A$ 可被對角化 (亦即由 彼此線性獨立 eigenvector 建構 $T$ 矩陣),但若我們有矩陣並不具有 $n$ 個獨立 eigenvector 該怎麼辦呢?  這個情況將會發生在 $A$ 矩陣有重根的時候:


Case II: 重複特徵值 (Repeated eigenvalues) 
考慮矩陣 $A$ 為 $n \times n$ 矩陣且具有 $m$ 個重複特徵值,亦即
\[
\lambda_1 = \lambda_2 = ... = \lambda_m
\]那麼這些重複的特徵值仍必須滿足特徵方程,亦即我們有
\[
\det(\lambda_m I - A) =0
\]且由於出現重根,在此情況下我們不再具有 $n$ 個線性獨立的 eigenvectors;故我們想知道到底剩下幾個 eigenvector 仍是線性獨立,故我們計算 rank: 若
\[
\text{rank}\{ \lambda_m I - A\} =i
\] 則 我們具有 $n -i$ 個 對應於 $\lambda_m$ 的線性獨立 eigenvectors。

重根的情況其實頗為複雜,現在我們看一些例子:

Example 1
\[A: = \left[ {\begin{array}{*{20}{c}}
{{\lambda _m}}&0&0\\
0&{{\lambda _m}}&0\\
0&0&{{\lambda _m}}
\end{array}} \right]\]此時 $A$ 矩陣具有三重根  $\lambda_m$ ,且 $\text{rank} \{\lambda_m I - A \} =0$ 故此三重根 $\lambda_m$ 會對應 $3 - 0 = 3$ 個各自獨立的 eigenvectors。

Example 2
\[A: = \left[ {\begin{array}{*{20}{c}}
{{\lambda _m}}&0&0\\
0&{{\lambda _m}}&1\\
0&0&{{\lambda _m}}
\end{array}} \right]\]此時 $A$ 矩陣具有三重根  $\lambda_m$ ,但 $\text{rank} \{\lambda_m I - A \} = 1$ 故此三重根 $\lambda_m$ 會對應 $3 - 1 = 2$ 個各自獨立的 eigenvectors。

Example 2
\[A: = \left[ {\begin{array}{*{20}{c}}
{{\lambda _m}}&1&0\\
0&{{\lambda _m}}&1\\
0&0&{{\lambda _m}}
\end{array}} \right]\]此時 $A$ 矩陣具有三重根  $\lambda_m$ ,但 $\text{rank} \{\lambda_m I - A \} = 2$故此三重根 $\lambda_m$ 會對應 $3 - 2 = 1$ 個各自獨立的 eigenvectors。


那麼當矩陣 $A$ 不具備足夠的線性獨立 eigenvector 時,我們需引入新的概念,稱作廣義特徵向量(Generalized eigenvector)。且 eigenvector 與 generalized eigenvector 可以建構一個
 non-singular matrix $T$ 使得 $J:= T^{-1}AT$ 且我們稱此 $J$ 矩陣為 Jordan matrix。
=============================
Definition: Generalized eigenvector
我們稱向量 $v$ 為 矩陣 $A$ 對應於 eigenvalue, $\lambda$ 的 rank $k$ 廣義特徵向量(generalized eigenvector) 若下列條件成立
\[\left\{ \begin{array}{l}
{\left( {\lambda I - A} \right)^k}v = 0\\
{\left( {\lambda I - A} \right)^{k - 1}}v \ne 0
\end{array} \right.
\]其中 $k$ 為矩陣 $A$ 的重根數目
=============================
NOTE: $k=1$ 即為原本的 eigenvalue 與 eigenvector。 (無重根)


Example
試求 $A$ 矩陣的 Jordan matrix 。
\[A = \left[ {\begin{array}{*{20}{c}}
1&1&2\\
0&1&3\\
0&0&2
\end{array}} \right]
\]
Solution
首先求解 $A$ 矩陣對應的 eigenvalue:注意由於此矩陣為上三角矩陣,eigenvalue 直接就是對角線元素。或者讀者亦可由特徵方程 $\det(\lambda I - A) =0$ 可解得 $\lambda_i = 1,1,2, \;\; i=1,2,3$ (雙重根 $\lambda_1 = \lambda_2 = 1$)。

我們可先計算單根 $\lambda_3 = 2$ 部分對應的 eigenvector :由 eigenvalue-eigenvector 關係
\[\begin{array}{l}
\left( {{\lambda _3}I - A} \right){v_3} = 0\\
 \Rightarrow \left( {2\left[ {\begin{array}{*{20}{c}}
1&0&0\\
0&1&0\\
0&0&1
\end{array}} \right] - \left[ {\begin{array}{*{20}{c}}
1&1&2\\
0&1&3\\
0&0&2
\end{array}} \right]} \right){v_3} = 0\\
 \Rightarrow \left[ {\begin{array}{*{20}{c}}
1&{ - 1}&{ - 2}\\
0&1&{ - 3}\\
0&0&0
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{v_{31}}}\\
{{v_{32}}}\\
{{v_{33}}}
\end{array}} \right] = 0\\
 \Rightarrow \left[ {\begin{array}{*{20}{c}}
{{v_{31}}}\\
{{v_{32}}}\\
{{v_{33}}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
5\\
3\\
1
\end{array}} \right]
\end{array}\]接著我們回頭對付重根 $( \lambda_1 = \lambda_2 = 1)$,先計算 $\text{rank}\{ \lambda_1 I - A\} = \text{rank}\{ \left[ {\begin{array}{*{20}{c}}
0&{ - 1}&{ - 2}\\
0&0&{ - 3}\\
0&0&{ - 1}
\end{array}} \right] = 2 \}$ 故重根對應的線性獨立 eigenvector 數目為 $3 - 2 = 1$。我們先求此 eigenvector:
\[\begin{array}{*{20}{l}}
{\left[ {\begin{array}{*{20}{c}}
0&{ - 1}&{ - 2}\\
0&0&{ - 3}\\
0&0&{ - 1}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{v_{11}}}\\
{{v_{12}}}\\
{{v_{13}}}
\end{array}} \right] = 0}\\
{ \Rightarrow \left\{ {\begin{array}{*{20}{l}}
{ - {v_{12}} - 2{v_{13}} = 0}\\
{ - 3{v_{13}} = 0}\\
{ - {v_{13}} = 0}
\end{array}} \right. \Rightarrow \left\{ {\begin{array}{*{20}{l}}
{{v_{12}} = 0}\\
{{v_{13}} = 0}
\end{array}} \right.}
\end{array}\]三個未知數,兩條方程式,故 $v_{11}$ 為自由變數,令 $v_{11} =1 $ 可得 $\lambda_m$ 對應的一組 eigenvector 為
\[\left[ {\begin{array}{*{20}{c}}
{{v_{11}}}\\
{{v_{12}}}\\
{{v_{13}}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{\rm{1}}\\
{\rm{0}}\\
{\rm{0}}
\end{array}} \right]\]接著我們利用此eigenvector 產生 generalized eigenvector 且滿足
\[\begin{array}{l}
\left( {{\lambda _2}I - A} \right){v_2} =  - {v_1}\\
 \Rightarrow \left[ {\begin{array}{*{20}{c}}
0&{ - 1}&{ - 2}\\
0&0&{ - 3}\\
0&0&{ - 1}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{v_{21}}}\\
{{v_{22}}}\\
{{v_{23}}}
\end{array}} \right] =  - \left[ {\begin{array}{*{20}{c}}
1\\
0\\
0
\end{array}} \right]\\
 \Rightarrow \left\{ \begin{array}{l}
 - {v_{22}} - 2{v_{23}} =  - 1\\
{v_{23}} = 0
\end{array} \right. \Rightarrow \left\{ \begin{array}{l}
{v_{22}} = 1\\
{v_{23}} = 0
\end{array} \right.
\end{array}\]故我們選 $v_{22} = 1$ 亦即
\[\left\{ {\begin{array}{*{20}{l}}
{{\lambda _1} = 1 \Rightarrow \left[ {\begin{array}{*{20}{c}}
{{v_{11}}}\\
{{v_{12}}}\\
{{v_{13}}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{\rm{1}}\\
{\rm{0}}\\
{\rm{0}}
\end{array}} \right];{\lambda _2} = 1 \Rightarrow \left[ {\begin{array}{*{20}{c}}
{{v_{21}}}\\
{{v_{22}}}\\
{{v_{23}}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{\rm{0}}\\
{\rm{1}}\\
{\rm{0}}
\end{array}} \right]}\\
{{\lambda _3} = 2 \Rightarrow \left[ {\begin{array}{*{20}{c}}
{{v_{11}}}\\
{{v_{12}}}\\
{{v_{13}}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{\rm{5}}\\
{\rm{3}}\\
{\rm{1}}
\end{array}} \right]}
\end{array}} \right.\]故其 nonsingular transformation matrix
\[T = \left[ {\begin{array}{*{20}{c}}
1&0&5\\
0&1&3\\
0&0&1
\end{array}} \right]\]
 Jordan matrix
\[
J = T^{-1} A T =\left[ {\begin{array}{*{20}{c}}
1&1&0\\
0&1&0\\
0&0&2
\end{array}} \right]
\]

Case III: Complex eigenvalues
考慮 $A$ 為 $2 \times 2$ 方陣,其特性方程滿足
\[
\det(\lambda_i - A) = 0
\]且 eigenvalue $\lambda = \sigma + j \omega$ 為 complex number 。

由上述可知 eigenvalue-eigenvector 關係
\[
(\lambda I - A) v_i =0
\] eigenvalue 為 complex value,其對應的 eigenvector $v_i$ 亦為 complex vector。

Example
考慮矩陣
\[A = \left[ {\begin{array}{*{20}{c}}
a&b\\
{ - b}&a
\end{array}} \right]\]$a,b \in \mathbb{R}, b \ne 0$。則我們可對此矩陣先求 eigenvalue,利用特性方程式可知
\[\begin{array}{l}
\det \left( {\lambda I - A} \right) = 0 \Rightarrow \det \left( {\left[ {\begin{array}{*{20}{c}}
{\lambda  - a}&{ - b}\\
b&{\lambda  - a}
\end{array}} \right]} \right) = 0\\
 \Rightarrow {\left( {\lambda  - a} \right)^2} + {b^2} = 0\\
 \Rightarrow {\lambda ^2} - 2a\lambda  + \left( {{a^2} + {b^2}} \right) = 0\\
 \Rightarrow \lambda  = a \pm jb
\end{array}\]現在我們求對應的 eigenvectors:

對 ${\lambda _1} = a + jb$ 我們可計算其 eigenvector 為
\[\begin{array}{l}
\left( {{\lambda _1}I - A} \right){v_1} = 0 \Rightarrow \left( {\left( {a + jb} \right)I - A} \right){v_1} = 0\\
 \Rightarrow \left[ {\begin{array}{*{20}{c}}
{\left( {a + jb} \right) - a}&{ - b}\\
b&{\left( {a + jb} \right) - a}
\end{array}} \right]{v_1} = 0\\
 \Rightarrow b\left[ {\begin{array}{*{20}{c}}
j&{ - 1}\\
1&j
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{v_{11}}}\\
{{v_{12}}}
\end{array}} \right] = 0\\
 \Rightarrow \left\{ \begin{array}{l}
j{v_{11}} - {v_{12}} = 0\\
{v_{11}} + j{v_{12}} = 0
\end{array} \right. \Rightarrow \left[ {\begin{array}{*{20}{c}}
{{v_{11}}}\\
{{v_{12}}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
1\\
j
\end{array}} \right]
\end{array}\]
接著對 ${\lambda _2} = a - jb$
\[\begin{array}{l}
\left( {{\lambda _2}I - A} \right){v_2} = 0 \Rightarrow \left( {\left( {a - jb} \right)I - A} \right){v_2} = 0\\
 \Rightarrow \left[ {\begin{array}{*{20}{c}}
{\left( {a - jb} \right) - a}&{ - b}\\
b&{\left( {a - jb} \right) - a}
\end{array}} \right]{v_2} = 0\\
 \Rightarrow b\left[ {\begin{array}{*{20}{c}}
{ - j}&{ - 1}\\
1&{ - j}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{v_{11}}}\\
{{v_{12}}}
\end{array}} \right] = 0\\
 \Rightarrow \left\{ \begin{array}{l}
 - j{v_{11}} - {v_{12}} = 0\\
{v_{11}} - j{v_{12}} = 0
\end{array} \right. \Rightarrow \left[ {\begin{array}{*{20}{c}}
{{v_{11}}}\\
{{v_{12}}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
j\\
1
\end{array}} \right]
\end{array}\]故 nonsingular transformation matrix $T$ 為
\[T = \left[ {\begin{array}{*{20}{c}}
1&j\\
j&1
\end{array}} \right]\]且
\[\begin{array}{l}
{T^{ - 1}}AT = {\left[ {\begin{array}{*{20}{c}}
1&j\\
j&1
\end{array}} \right]^{ - 1}}\left[ {\begin{array}{*{20}{c}}
a&b\\
{ - b}&a
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
1&j\\
j&1
\end{array}} \right] = \frac{1}{2}\left[ {\begin{array}{*{20}{c}}
1&{ - j}\\
{ - j}&1
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
a&b\\
{ - b}&a
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
1&j\\
j&1
\end{array}} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = \frac{1}{2}\left[ {\begin{array}{*{20}{c}}
1&{ - j}\\
{ - j}&1
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{a + bj}&{aj + b}\\
{ - b + aj}&{ - bj + a}
\end{array}} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = \frac{1}{2}\left[ {\begin{array}{*{20}{c}}
{\left( {a + bj} \right) - j\left( { - b + aj} \right)}&{aj + b - j\left( { - bj + a} \right)}\\
{ - j\left( {a + bj} \right) - b + aj}&{ - j\left( {aj + b} \right) - bj + a}
\end{array}} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = \frac{1}{2}\left[ {\begin{array}{*{20}{c}}
{2a + 2jb}&0\\
0&{2a - 2jb}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{a + jb}&0\\
0&{a - jb}
\end{array}} \right]
\end{array}\]