Hermitian 矩陣特徵值的變化界定

本文的閱讀等級:高級

在“二次型與正定矩陣”一文,我們曾經介紹對稱矩陣的特徵值與特徵向量於最佳化問題的用途,本文延續該文的討論並進一步將實對稱矩陣推廣至 Hermitian 矩陣 (請參閱背景文章“特殊矩陣 (9):Hermitian 矩陣”)。令 A 為一 n\times n 階 Hermitian 矩陣。對於任一 \mathbf{x}\in\mathbb{C}^n,二次型 \mathbf{x}^{\ast}A\mathbf{x} 必為實數。考慮這兩個實數集合:

\displaystyle  \Phi=\left\{\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}~\vline~\mathbf{x}\neq\mathbf{0}\right\}

\displaystyle  \Psi=\left\{\mathbf{x}^{\ast}A\mathbf{x}~\vline~\Vert\mathbf{x}\Vert=1\right\}

很明顯,\Psi\subseteq\Phi。另一方面,對於任意 \mathbf{x}\neq\mathbf{0},令 \mathbf{y}=\frac{\mathbf{x}}{\Vert\mathbf{x}\Vert},則 \Vert\mathbf{y}\Vert=1 而且

\displaystyle\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\Vert\mathbf{x}\Vert^2}=\left(\frac{\mathbf{x}}{\Vert\mathbf{x}\Vert}\right)^{\ast}A\left(\frac{\mathbf{x}}{\Vert\mathbf{x}\Vert}\right)=\mathbf{y}^{\ast}A\mathbf{y}

推論集合 \Phi 中的任何元素也都屬於 \Psi,所以 \Phi=\Psi。集合 \Phi 中的表示式 \frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}} 稱為 Rayleigh 商 (quotient),它與特徵方程式 A\mathbf{x}=\lambda\mathbf{x} 有著密切的關係。因為 Hermitian 矩陣的特徵值皆為實數,我們可以假設 \lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n,下面這個定理描述了 Rayleigh 商的範圍。

 
Rayleigh 定理

A 為一 n\times n 階 Hermitian 矩陣,

\displaystyle\max_{\mathbf{x}\neq\mathbf{0}}\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}=\lambda_1

\displaystyle\min_{\mathbf{x}\neq\mathbf{0}}\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}=\lambda_n

也就是說 Rayleigh 商的上界與下界分別等於 A 的最大特徵值與最小特徵值。

 
Rayleigh 定理的證明借重 Hermitian 矩陣的一個重要性質。Hermitian 矩陣是可么正對角化的 (unitarily diagonalizable),亦即存在一么正矩陣 UU^{-1}=U^{\ast},使得 A=U\Lambda U^{\ast},其中 \Lambda=\mathrm{diag}(\lambda_1,\ldots,\lambda_n)U=\begin{bmatrix}\mathbf{u}_1&\cdots\mathbf{u}_n\end{bmatrix} 的行向量 \mathbf{u}_i 為對應 \lambda_i 的特徵向量。令 \mathbf{z}=[z_i]=U^{\ast}\mathbf{x},也就有

\begin{aligned}\displaystyle  \frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}&=\frac{\mathbf{x}^{\ast}U\Lambda U^{\ast}\mathbf{x}}{\mathbf{z}^{\ast}UU^{\ast}\mathbf{z}}=\frac{\mathbf{z}^{\ast}\Lambda\mathbf{z}}{\mathbf{z}^{\ast}\mathbf{z}}\\  &=\frac{\lambda_1\vert z_1\vert^2+\cdots+\lambda_n\vert z_n\vert^2}{\vert z_1\vert^2+\cdots+\vert z_n\vert^2}\\  &\le\frac{\lambda_1(\vert z_1\vert^2+\cdots+\vert z_n\vert^2)}{\vert z_1\vert^2+\cdots+\vert z_n\vert^2}=\lambda_1\end{aligned}

取反向不等式則得到

\begin{aligned}\displaystyle  \frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}&=\frac{\lambda_1\vert z_1\vert^2+\cdots+\lambda_n\vert z_n\vert^2}{\vert z_1\vert^2+\cdots+\vert z_n\vert^2}\\  &\ge\frac{\lambda_n(\vert z_1\vert^2+\cdots+\vert z_n\vert^2)}{\vert z_1\vert^2+\cdots+\vert z_n\vert^2}=\lambda_n\end{aligned}

\mathbf{x}=\mathbf{u}_1,我們得到 \mathbf{z}=U^{\ast}\mathbf{u}_1=(1,0,\ldots,0)^T,故 \frac{\mathbf{z}^{\ast}\Lambda\mathbf{z}}{\mathbf{z}^{\ast}\mathbf{z}}=\lambda_1;當 \mathbf{x}=\mathbf{u}_n,可得 \mathbf{z}=U^{\ast}\mathbf{u}_n=(0,\ldots,0,1)^T,故 \frac{\mathbf{z}^{\ast}\Lambda\mathbf{z}}{\mathbf{z}^{\ast}\mathbf{z}}=\lambda_{n}。Rayleigh 商的最大值與最小值分別發生於對應 \lambda_1\lambda_n 的特徵向量 \mathbf{u}_1\mathbf{u}_n

 
Rayleigh 定理的幾何意義是如果限制 \mathbf{x} 為單位向量,\lambda_1\lambda_n 給出二次型 \mathbf{x}^{\ast}A\mathbf{x} 的最大值與最小值。考慮 \mathbf{e}_i=(0,\ldots,0,1,0,\ldots,0)^T,其第 i 個元素為 1,則 \mathbf{e}_i^{\ast}A\mathbf{e}_i=a_{ii}。Rayleigh 定理有這個必然結果:Hermitian 矩陣 A=[a_{ij}] 的任意主對角元也落在 \lambda_1\lambda_n 之間,即 \lambda_n\le a_{ii}\le\lambda_1。利用此性質可約略估計 Hermitian 矩陣最大特徵值的下界和最小特徵值的上界,例如,

A=\begin{bmatrix}    1&2&3\\    2&5&4\\    3&4&9    \end{bmatrix}

不需經過計算也可推知 A 的最大特徵值不小於 9,最小特徵值不大於 1

 
Rayleigh 定理提供了一個界定 Hermitian 矩陣最大和最小特徵值的方法,但要如何利用極小化或極大化原則求出其餘的特徵值 \lambda_2,\ldots,\lambda_{n-1}?倘若我們僅考慮與 \mathbf{u}_1 正交的子空間中的向量 \mathbf{x}\mathbf{x}\perp\mathbf{u}_1,則 \mathbf{z}=U^{\ast}\mathbf{x}=\begin{bmatrix}\mathbf{u}_1&\mathbf{u}_2&\cdots&\mathbf{u}_n\end{bmatrix}^{\ast}\mathbf{x}=(0,z_2,\ldots,z_n)^T,檢視以向量 \mathbf{z} 表示的 Rayleigh 商:

\begin{aligned}  \displaystyle\frac{\mathbf{z}^{\ast}\Lambda\mathbf{z}}{\mathbf{z}^{\ast}\mathbf{z}}&=\frac{\lambda_2\vert z_2\vert^2+\cdots+\lambda_n\vert z_n\vert^2}{\vert z_2\vert^2+\cdots+\vert z_n\vert^2}\\  &\le\frac{\lambda_2(\vert z_2\vert^2+\cdots+\vert z_n\vert^2)}{\vert z_2\vert^2+\cdots+\vert z_n\vert^2}=\lambda_2\end{aligned}

也就有

\displaystyle\max_{\mathbf{x}\neq\mathbf{0},~\mathbf{x}\perp\mathbf{u}_1}\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}=\lambda_2

 
上述作法的缺點是必須先知道特徵向量 \mathbf{u}_1,如要略過計算特徵向量不妨考慮 \mathbb{C}^n 中的任意向量 \mathbf{w},我們仍然在與 \mathbf{w} 正交的子空間中尋找 Rayleigh 商的極值,由 \mathbf{x}\perp\mathbf{w} 可知

0=\mathbf{x}^{\ast}\mathbf{w}=(U\mathbf{z})^{\ast}\mathbf{w}=\mathbf{z}^{\ast}U^{\ast}\mathbf{w}

\mathbf{z}\perp U^{\ast}\mathbf{w}。令 \mathcal{V}=\{\mathbf{z}\in\mathbb{C}^n\vert\mathbf{z}\perp U^\ast\mathbf{w}\}\mathcal{V}'=\{\mathbf{z}\in\mathbb{C}^n\vert\mathbf{z}\perp U^\ast\mathbf{w},z_3=\cdots=z_n=0\}。明顯地,\mathcal{V}'\subset\mathcal{V}。所以,

\begin{aligned}\displaystyle \max_{\mathbf{x}\neq\mathbf{0},~\mathbf{x}\perp\mathbf{w}}\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}&=\max_{\mathbf{z}\neq\mathbf{0},~\mathbf{z}\perp U^{\ast}\mathbf{w}}\frac{\mathbf{z}^{\ast}\Lambda\mathbf{z}}{\mathbf{z}^{\ast}\mathbf{z}}=\max_{\mathbf{z}\neq\mathbf{0},~\mathbf{z}\in\mathcal{V}}\frac{\mathbf{z}^{\ast}\Lambda\mathbf{z}}{\mathbf{z}^{\ast}\mathbf{z}}\\  &\ge\max_{\mathbf{z}\neq\mathbf{0},~\mathbf{z}\in\mathcal{V}'}\frac{\mathbf{z}^{\ast}\Lambda\mathbf{z}}{\mathbf{z}^{\ast}\mathbf{z}}=\max_{\mathbf{z}\neq\mathbf{0},~\mathbf{z}\in \mathcal{V}'}\frac{\lambda_1\vert z_1\vert^2+\lambda_2\vert z_2\vert^2}{\vert z_1\vert^2+\vert z_2\vert^2}\ge\lambda_2\end{aligned}

前面的不等式成立的原因是在 \mathcal{V}^{\prime}\setminus\{\mathbf{0}\} 所得到的最大值必不大於在 \mathcal{V}\setminus\{\mathbf{0}\} 中找到的最大值;後面的不等式則源於 \lambda_1\ge\lambda_2。因為 \mathbf{w} 是任意固定向量,對於所有可能的 \mathbf{w} 獲得的極小值也必定大於 \lambda_2,亦即

\displaystyle\min_{\mathbf{w}}\max_{\mathbf{x}\neq\mathbf{0},~\mathbf{x}\perp\mathbf{w}}\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}\ge\lambda_2

此不等式的等號於 \mathbf{w}=\mathbf{u}_1 時成立,所以有

\displaystyle \min_{\mathbf{w}}\max_{\mathbf{x}\neq\mathbf{0},~\mathbf{x}\perp\mathbf{w}}\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}=\lambda_2

設想在任意的 n-1 維子空間,亦即與 \mathbf{w} 正交的子空間中尋找 Rayleigh 商的最大值。這個子空間未必包含任何特徵向量,但我們確知其中必定有某個子空間不包含對應最大特徵值 \lambda_1 的特徵向量 \mathbf{u}_1,而從該子空間所找到的最大 Rayleigh 商正是在所有 n-1 維子空間所能找到的極小值!如果將 max 和 min 交換位置,利用對稱原理不難得知

\displaystyle \max_{\mathbf{w}}\min_{\mathbf{x}\neq\mathbf{0},~\mathbf{x}\perp\mathbf{w}}\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}=\lambda_{n-1}

 
繼續討論之前,請先看下面這個取自2010年成大研究所的入學試題 (此題由網友 sevensix 提供張貼於 http://img707.yfrog.com/i/math2a.jpg/):

\displaystyle \max_{\mathbf{w}}\min_{\mathbf{x}^{T}\mathbf{w}=0}\frac{\mathbf{x}^TA\mathbf{x}}{\mathbf{x}^T\mathbf{x}}

其中

A=\left[\!\!\begin{array}{rrcr}    5&0&1&-2\\    0&5&2&-1\\    1&2&5&0\\    -2&-1&0&5    \end{array}\!\!\right]

A 的特徵值依遞減方式排序,\lambda_1\ge\lambda_2\ge\lambda_3\ge\lambda_4,此題答案即為 \lambda_3,剩下的工作是解出 A 的特徵值。運用一些技巧可以避開求解四階特徵多項式的根,考慮

B=A-5I=\left[\!\!\begin{array}{rrcr}    0&0&1&-2\\    0&0&2&-1\\    1&2&0&0\\    -2&-1&0&0    \end{array}\!\!\right]

\lambda_i(A)\lambda_i(B) 代表 AB 的特徵值,很明顯 \lambda_i(A)=\lambda_i(B)+5。觀察 B 的型態可設 B=\begin{bmatrix}    0&C\\    C^T&0    \end{bmatrix},令 \begin{bmatrix}    \mathbf{x}\\    \mathbf{y}    \end{bmatrix} 為特徵向量,則 B 的特徵方程式為

\begin{bmatrix}    0&C\\    C^T&0    \end{bmatrix}\begin{bmatrix}    \mathbf{x}\\    \mathbf{y}    \end{bmatrix}=\lambda\begin{bmatrix}    \mathbf{x}\\    \mathbf{y}    \end{bmatrix}

展開得到 C\mathbf{y}=\lambda\mathbf{x}C^{T}\mathbf{x}=\lambda\mathbf{y},第二式左乘 C,再使用第一式,就有

CC^{T}\mathbf{x}=\lambda C\mathbf{y}=\lambda^2\mathbf{x}

代入數值計算 CC^{T}=\begin{bmatrix}    5&4\\    4&5    \end{bmatrix},解出 CC^T 的特徵值 \lambda^291,故 \lambda_i(B)=3,1,-1,-3 (因為 B 的特徵值和為零),所以 \lambda_i(A)=8,6,4,2,原題答案為 4

 
回到我們的問題,順著極小化─極大化 (或極大化─極小化) 原則可以繼續往前推論出更一般性結果,稱為 Courant-Fischer 定理。先準備必要的符號,令 \mathcal{W}_{k}\mathbb{C}^n 中的子空間,設 \mathcal{W}_{k} 的基底為 \{\mathbf{w}_1,\ldots,\mathbf{w}_k\},故 \mathrm{dim}\mathcal{W}_{k}=k

 
Courant-Fischer 定理

A 為一 n\times n 階 Hermitian 矩陣,

\displaystyle  \min_{\mathcal{W}_{k-1}}\max_{\mathbf{x}\neq\mathbf{0},~\mathbf{x}\perp\mathcal{W}_{k-1}}\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}=\lambda_k

\displaystyle  \max_{\mathcal{W}_{n-k}}\min_{\mathbf{x}\neq\mathbf{0},~\mathbf{x}\perp\mathcal{W}_{n-k}}\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}=\lambda_k

 
第一式稱為 \lambda_k 的極小化─極大化原則,第二式則稱為 \lambda_k 的極大化─極小化原則。下面只證明極小化─極大化原則,極大化─極小化原則的證明方式雷同。令 U^{\ast}\mathcal{W}_{k} 表示由基底\{U^{\ast}\mathbf{w}_1,\ldots,U^{\ast}\mathbf{w}_{k}\} 擴張而成的子空間。我們將證明以 \mathbf{z} 表達的 Rayleigh 商滿足

\displaystyle\lambda_k=\min_{\mathcal{W}_{k-1}}\max_{\mathbf{z}\neq\mathbf{0},~\mathbf{z}\perp U^{\ast}\mathcal{W}_{k-1}}\frac{\mathbf{z}^{\ast}\Lambda\mathbf{z}}{\mathbf{z}^{\ast}\mathbf{z}}

仿照前述當 k=2 的推論證明方式,可得

\displaystyle  \max_{\mathbf{z}\neq\mathbf{0},~\mathbf{z}\perp U^{\ast}\mathcal{W}_{k-1}}\frac{\mathbf{z}^{\ast}\Lambda\mathbf{z}}{\mathbf{z}^{\ast}\mathbf{z}}\ge\max_{\mathbf{z}\neq\mathbf{0},~\mathbf{z}\perp U^{\ast}\mathcal{W}_{k-1}}\frac{\lambda_1\vert z_1\vert^2+\cdots+\lambda_k\vert z_k\vert^2}{\vert z_1\vert^2+\cdots+\vert z_k\vert^2}\ge\lambda_k

也就是說,對於任意 \mathcal{W}_{k-1} 都有

\displaystyle\max_{\mathbf{x}\neq\mathbf{0},~\mathbf{x}\perp\mathcal{W}_{k-1}}\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}\ge\lambda_k

\mathbf{w}_i=\mathbf{u}_{i}i=1,\ldots,k-1\mathcal{W}_{k-1} 的正交補餘 \mathcal{W}_{k-1}^{\perp} 不包含特徵向量 \mathbf{u}_1,\ldots,\mathbf{u}_{k-1},故 \lambda_k 是我們所能找到最大的特徵值,這時上面不等式的等號成立,因此證得

\displaystyle\min_{\mathcal{W}_{k-1}}\mathrm{max}_{\mathbf{x}\neq\mathbf{0},~\mathbf{x}\perp\mathcal{W}_{k-1}}\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}=\lambda_k

 
Courant-Fischer 定理的價值在於──即便不知道 Hermitian 矩陣的特徵向量──我們能從極小化─極大化原則,也就是透過變化界定 (variational characterization) 來決定 Hermitian 矩陣的特徵值。Courant-Fischer 定理的應用將於另文詳細介紹。

延伸閱讀:
This entry was posted in 線性代數專欄, 二次型 and tagged , , , , . Bookmark the permalink.

11 則回應給 Hermitian 矩陣特徵值的變化界定

  1. foremap 說:

    ………..對齁
    害我玩了很久
    原來直接扣掉5I就可以輕鬆求eigenvalue了
    我覺得 當個研究生 很容易讓頭腦僵化 真的 = =

  2. ccjou 說:

    二十出頭的年輕人怎麼說自己頭腦僵化呢?誰說找特徵值一定要透過解特徵多項式的根…大概又是我們當老師的這些人說的…

    我才頭腦僵化,常常忘東忘西,昨天又差一點找不到鑰匙。

  3. Watt Lin 說:

    我有一位教授,退休成為榮譽教授,現在九十多歲,頭腦還很靈活。
    他去年還來為我們作一兩場特別演講,這回PowerPoint檔由別人幫他作。
    但我記得七年前,老教授是親自打字完成PowerPoint的slides。

    幾個月前遇到教授,談起民國七十七年,我在大學一年級時期,曾經與他談過的一些話,他也記得。

    頭腦愈用會愈靈活!
    願大家都保持靈活的思考!

    我雖然40多歲才自學線性代數,買老師的DVD來看,也是學得津津有味。感覺最近頭腦好像愈來愈好,可能是來自線性代數的啟發。

  4. ccjou 說:

    Blaise Pascal 說:人是會思考的蘆葦。這句話既富哲思又具美感,全文如下:
    Man is but a reed, the most feeble thing in nature, but he is a thinking reed. The entire universe need not arm itself to crush him. A vapor, a drop of water suffices to kill him. But, if the universe were to crush him, man would still be more noble than that which killed him, because he knows that he dies and the advantage which the universe has over him, the universe knows nothing of this.
    All our dignity then, consists in thought. By it we must elevate ourselves, and not by space and time which we cannot fill. Let us endeavour then, to think well; this is the principle of morality.

  5. Watt Lin 說:

    看到 Pascal ,我眼睛為之一亮,這是數學家、哲學家,也是一種程式語言的名稱。
    民國74年我高中一年級暑假,學習Pascal程式語言,大概也是我第一次「遇到」矩陣乘法。當年我能夠寫出矩陣乘法的程式(書本習題),但沒思考它有深層的意涵。
    高三數學課本有矩陣列運算,老師曾經演算課本沒提到的二維方陣eigen value,印象中好像也有A的n次方拆成 S (Lumbda ^ n) (Inv(S)) 這種快速算法。當年只會跟著抄筆記,不瞭解意思。

    大學時期沒接觸相關課程,竟然等到40多歲才學習思考矩陣乘法代表的意義。
    好像太慢了!但好像也還來得及,或許過幾年,線性代數的觀念會在我的生活、工作發揮效用,這也說不定。

    最後要說:很高興我又看到 Pascal 了!
    雖然我的職業不是寫程式,也只曾經寫過少量程式碼,
    但是Pascal程式語言曾經伴隨我頭腦作思考,很多年之久。

  6. 說:

    請問老師可否說說 “前面的不等式成立的原因是在子空間 \mathcal{V}^{\prime}\subset\mathcal{V} 得到的最大值必不大於在 \mathcal{V} 中找到的最大值" 中, 子空間 \mathcal{V}^{\prime}\mathcal{V} 分別是指什麼嗎? 因為仍然看不明白不等式跟 \lambda_1, \lambda_2z_1, z_2 的關係. 謝謝

  7. yetengqi 說:

    There is a typo in the formula $\frac{x^*Ax}{x^*x} = \frac{x^*U\Lambda U^*x}{z^*UU^*z}$

  8. Lin 說:

    仔細推導了下,感覺子空間V和V’的選取很有技巧性啊!
    我是這樣理解的:V = N(w’U),表示向量w’U的零空間;設矩陣B=[w’U;e3′;e4′;…;en’],那麼V’=N(B)。
    因此V’在V裡面。
    最重要的是,這中設計方法能保證B是一個(n-1)xn的矩陣,dim N(B)>0。必然存在一個非零的向量z屬於N(B)。
    根據這個思路,就好理解後面的Courant-Fischer 定理了。

    另一個感覺是上文中的min max問題和max min問題很像是在求解一個worst case optimization problem。例如,最小化函數f(x)=x’Ax/(x’x),如果限制x與某個向量w正交,max min f(x)相當於求“最差”情況下,f(x)的最小值。而最差情況就是lambda_n對應的特徵向量u_n作為w,在此情況下,最優解只能是x=u_(n-1),f(x)=lambda_(n-1)。

    之前對Courant-Fischer 定理有一種“似懂非懂”的感覺,今天好想明白了。。。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s