特徵向量是甚麽物，恁麽來？

Posted on 07/16/2013 by

本文的閱讀等級：初級
《南嶽懷讓禪師傳》記載：
祖問：「甚麽處來？」
曰：「嵩山來。」
祖曰：「甚麽物，恁麽來？」師無語，經八載忽然有悟，乃白祖曰：「某甲有個會處。」
祖曰：「作麽生？」
師曰：「説似一物即不中。」
唐代懷讓禪師為尋訪善知識跑去嵩山謁見惠安國師，惠安指點他參訪曹溪六祖。禮拜畢，六祖問：「你從何處來？」懷讓回：「我從嵩山來。」六祖又問：「你是甚麼東西？怎麼來的？」懷讓當下無言以對，經過八年參究，一天豁然開悟，便對六祖說：「我想通了。」六祖問：「怎麼樣？」懷讓回：「說是甚麼東西都不對。」

特徵向量甚麽處來？問既一般，答亦相似。翻開課本就可以找到答案，定義有兩種版本。(1) 線性變換版：令 \mathcal{V} 為一向量空間，T:\mathcal{V}\to\mathcal{V} 是一線性變換。若非零向量 \mathbf{x}\in\mathcal{V} 滿足 T(\mathbf{x})=\lambda\mathbf{x}，則 \mathbf{x} 稱為對應特徵值 \lambda 的特徵向量。(2) 矩陣版：令 A 為一 n\times n 階矩陣。若非零向量 \mathbf{x}\in\mathbb{C}^n 滿足 A\mathbf{x}=\lambda\mathbf{x}，則 \mathbf{x} 稱為對應特徵值 \lambda 的特徵向量。倘使繼續追問：特徵向量是甚麽物，恁麽來？「説似一物即不中」提點我們不要死執一法 (定義)，所以何妨「說似多物」，即便亂槍打鳥不中或許也相距不遠。


一物：向量迭代
令 A 是一 n\times n 階矩陣。給定初始非零向量 \mathbf{u}_0\in\mathbb{C}^n，差分方程 \mathbf{u}_{k+1}=A\mathbf{u}_k 的解為 \mathbf{u}_k=A^k\mathbf{u}_0，k=1,2,\ldots。飯裡有砂，泥中有刺。若不細心追究，我們很難察覺表面事物底下隱藏的道理。見下例，
\displaystyle A=\begin{bmatrix} 1.2&0.2\\ 0.8&1.8 \end{bmatrix},~~~\mathbf{u}_0=\left[\!\!\begin{array}{r} 1\\ -0.5 \end{array}\!\!\right]。
逐次迭代可得向量序列：
\displaystyle \begin{array}{ccccccccccc} k&\vline&0&1&2&3&4&5&6&7&8\\ \hline &\vline&\\ \mathbf{u}_k&\vline &\left[\!\!\begin{array}{r} 1\\ -0.5 \end{array}\!\!\right]&\left[\!\!\begin{array}{r} 1.1\\ -0.1 \end{array}\!\!\right]&\left[\!\!\begin{array}{c} 1.3\\ 0.7 \end{array}\!\!\right]&\left[\!\!\begin{array}{c} 1.7\\ 2.3 \end{array}\!\!\right]&\left[\!\!\begin{array}{c} 2.5\\ 5.5 \end{array}\!\!\right]&\left[\!\!\begin{array}{r} 4.1\\ 11.9 \end{array}\!\!\right]&\left[\!\!\begin{array}{r} 7.3\\ 24.7 \end{array}\!\!\right]&\left[\!\!\begin{array}{c} 13.7\\ 50.3 \end{array}\!\!\right]&\left[\!\!\begin{array}{r} 26.5\\ 101.5 \end{array}\!\!\right] \end{array}
下圖顯示 \mathbf{u}_0,\mathbf{u}_1,\ldots,\mathbf{u}_4，其他向量因長度過長，故僅以直線表示向量指向。觀察發現向量序列 \{\mathbf{u}_k\} 的指向逐漸逼近 \mathbf{x}=\begin{bmatrix} 1\\ 4 \end{bmatrix} (圖中黑色直線)。代入數值計算可得
\displaystyle A\mathbf{x}=\begin{bmatrix} 1.2&0.2\\ 0.8&1.8 \end{bmatrix}\begin{bmatrix} 1\\ 4 \end{bmatrix}=\begin{bmatrix} 2\\ 8 \end{bmatrix}=\lambda\mathbf{x}，
其中 \lambda=2。換句話說，當 k\to\infty，向量序列 \{\mathbf{u}_k\} 收斂至對應特徵值 \lambda 的特徵向量 \mathbf{x} 所擴張的子空間。
Iterates of a vector
向量迭代

上面的迭代過程提供了一個計算特徵向量 \mathbf{x} 以及對應特徵值 \lambda 的算法。為了控制 \mathbf{u}_k 的長度，我們在迭代步驟引入歸一性：對於 k=0,1,2,\ldots，
\displaystyle\begin{aligned} \mathbf{u}_{k+1}&=\frac{A\mathbf{u}_k}{\Vert A\mathbf{u}_k\Vert}\\ \lambda_{k+1}&=\mathbf{u}_{k+1}^TA\mathbf{u}_{k+1}.\end{aligned}
這個算法稱為 Power 迭代法，數列 \{\lambda_{k}\} 收斂至 A 的絕對值最大的特徵值，而 \{\mathbf{u}_k\} 收斂至對應的單位長特徵向量 (證明見“Power 迭代法”)。

說也奇怪，每次談到迭代總會讓我想起趙州禪師與弟子文遠「比誰卑賤」的故事，亮點是贏的人 (也就是比較卑賤的人) 輸果子：
師與文遠論義。曰：「鬥劣不鬥勝。」勝者輸果子。
遠曰：「請和尚立義。」
師曰：「我是一頭驢。」
遠曰：「我是驢胃。」
師曰：「我是驢糞。」
遠曰：「我是糞中蟲。」
師曰：「你在彼中作甚麼。」
遠曰：「我在彼中過夏。」
師曰：「把將果子來。」
如果「我是一頭驢」代表初始向量 \mathbf{u}_{0}，每鬥一回迭代一次，\mathbf{u}_{k+1}=A\mathbf{u}_k 表示「卑賤度」提升一層，最終「我是糞中蟲」不就是 (嚴格說，逼近) 特徵向量 \mathbf{x}？

二物：約束最佳化
下文抄錄自“二次型與正定矩陣”：
特徵值和特徵向量是線性代數裡分析矩陣結構與線性變換最重要的概念，二次型的最大化 (或最小化) 問題是特徵值和特徵向量的一個典型應用。設 A 是實對稱矩陣，考慮此問題：
\displaystyle \max_{\Vert\mathbf{x}\Vert=1}\mathbf{x}^TA\mathbf{x}。
求解這個約束最佳化 (constrained optimization) 問題的傳統方法是引入 Lagrangian 函數：
\displaystyle L(\mathbf{x},\lambda)\equiv\mathbf{x}^TA\mathbf{x}-\lambda(\mathbf{x}^T\mathbf{x}-1)。
產生極值的必要條件是 L 對 \mathbf{x} 的各元的一次偏導數都等於零，亦即 \mathbf{x} 是 L 的一個駐點 (見“最佳化理論與正定矩陣”)。因為 A^T=A，請讀者自行計算驗證
\displaystyle \mathbf{0}=\nabla_{\mathbf{x}}L=2(A\mathbf{x}-\lambda\mathbf{x})。
單位長向量 \mathbf{x} 要使\mathbf{x}^TA\mathbf{x} 最大化的必要條件即為特徵方程 A\mathbf{x}=\lambda\mathbf{x}，將此式代入二次型可得
\displaystyle \mathbf{x}^TA\mathbf{x}=\mathbf{x}^T(\lambda\mathbf{x})=\lambda\Vert\mathbf{x}\Vert^2=\lambda。
由於實對稱矩陣的特徵值必為實數，使二次型最大化的向量 \mathbf{x} 正是對應最大特徵值的特徵向量。

三物：微分方程
下文抄錄自“從不變子空間切入特徵值問題”：
對首次接觸特徵分析的學者來說，A\mathbf{x}=\lambda\mathbf{x} 像是從天上掉下來的禮物。表面上，人人面露喜悅之情欣然接受；私底下，個個心中不免納悶：「這個神奇的式子究竟是怎麼冒出來的？」教書多年，我當然清楚學生的疑惑，參考了各家說法之後，決定採用一個省時省力的問題導入方式。每回開始講解特徵分析前，我會先介紹一階常微分方程
\displaystyle \frac{du}{dt}=au(t)，
並說明解為 u(t)=xe^{at}，其中 x 是一純量。緊接著延伸至高階微分方程，寫出對應的矩陣表達式：
\displaystyle \frac{d\mathbf{u}}{dt}=A\mathbf{u}(t)。
從一階微分方程的解，我們猜想解向量的形式為 \mathbf{u}(t)=e^{\lambda t}\mathbf{x}，將它代回微分方程式，可得
\displaystyle \lambda e^{\lambda t}\mathbf{x}=e^{\lambda t}A\mathbf{x}。
等號兩邊消去 e^{\lambda t} 就得到特徵方程 A\mathbf{x}=\lambda\mathbf{x}。

四物：對角化
令 A 和 B 為 n\times n 階矩陣。若存在可逆矩陣 S 使得 B=S^{-1}AS，我們稱 B 相似於 A，並稱 S 是 A 與 B 之間的相似變換矩陣。根據上述定義，二相似矩陣有何功能性的關係？已知 S=\begin{bmatrix} \mathbf{x}_1&\cdots&\mathbf{x}_n \end{bmatrix} 是 n\times n 階可逆矩陣，\{\mathbf{x}_1,\ldots,\mathbf{x}_n\} 是線性獨立集，故可為 \mathbb{C}^n 的一組基底，記為 \boldsymbol{\beta}=\{\mathbf{x}_1,\ldots,\mathbf{x}_n\}。令 [\mathbf{x}]_{\boldsymbol{\beta}}=S^{-1}\mathbf{x} 代表向量 \mathbf{x} 參考基底 \boldsymbol{\beta} 的座標向量。考慮以矩陣 A 表示的線性變換 T(\mathbf{x})=A\mathbf{x}，同樣令 [T(\mathbf{x})]_{\boldsymbol{\beta}}=S^{-1}(A\mathbf{x}) 代表 T(\mathbf{x}) 參考 \boldsymbol{\beta} 的座標向量。將 \mathbf{x}=S[\mathbf{x}]_{\boldsymbol{\beta}} 代入上式，可得
\displaystyle [T(\mathbf{x})]_{\boldsymbol{\beta}}=S^{-1}AS[\mathbf{x}]_{\boldsymbol{\beta}}。
若 A 是線性變換 T 參考標準基底的表示矩陣，則 B=S^{-1}AS 為 T 參考基底 \boldsymbol{\beta} 的線性變換表示矩陣。

相似變換保留許多重要的矩陣性質，如特徵多項式、特徵值、行列式、跡數、矩陣秩以及 Jordan 形式 (見“相似變換下的不變性質”)。因為這個緣故，我們希望 B=S^{-1}AS 的形式越簡單越好。主對角矩陣是最簡化的矩陣型態，記作 D=\hbox{diag}(\lambda_1,\ldots,\lambda_n)=S^{-1}AS，稱為對角化。將相似變換改寫成 AS=SD，如下：
\displaystyle A\begin{bmatrix} \mathbf{x}_1&\cdots&\mathbf{x}_n \end{bmatrix}=\begin{bmatrix} \mathbf{x}_1&\cdots&\mathbf{x}_n \end{bmatrix}\begin{bmatrix} \lambda_1&&\\ &\ddots&\\ &&\lambda_n \end{bmatrix}。
乘開比較等號兩邊，可得特徵方程 \displaystyle A\mathbf{x}_i=\lambda_i\mathbf{x}_i，i=1,\ldots,n。

特徵向量是甚麽物，恁麽來？上述所有理由都能自圓其說。但如果讀者還是不滿意這些說法，請看「趙州小便」的故事：
問：「急切處，請師道。」
師云：「尿是小事，須是老僧自去始得。」
信徒問趙州禪師：「怎麼參禪才能悟道呢？」趙州起身道：「我要去小便了。」接著又說：「尿尿這種小事，還是要老僧自己去才行。」意思是說，如何參禪悟道是你自己的事，怎麼來問我呢？