Courant-Fischer 定理的應用

本文的閱讀等級:高級

Courant-Fischer 定理是“Hermitian 矩陣特徵值的變化界定”一文的主要結果,此定理說明了如何利用最小-最大原則或最大-最小原則推得 Hermitian 矩陣的特徵值,所以也稱作最小-最大 (min-max) 定理。本文介紹 Courant-Fischer 定理的兩個應用:Weyl 定理與Cauchy 交錯特徵值定理。為方便參照,首先回顧 Courant-Fischer 定理。

 
Courant-Fischer 定理

A 為一 n\times n 階 Hermitian 矩陣,A 的特徵值按遞減方式排序 \lambda_1\ge\cdots\ge\lambda_n,設 \mathcal{W}_k\mathbb{C}^n 中的子空間,\mathrm{dim}\mathcal{W}_k=k\lambda_k 可由下式得到

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

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

 
我們討論的第一個應用是關於二 Hermitian 矩陣和 A+B 其特徵值的界定問題。下面以符號 \lambda_i(A) 表示 n\times n 階 Hermitian 矩陣 A 按遞減排序的第 i 個特徵值。

 
Weyl 定理

ABn\times n 階 Hermitian 矩陣,對於 k=1,\ldots,n,有

\lambda_k(A)+\lambda_1(B)\ge\lambda_k(A+B)\ge\lambda_k(A)+\lambda_n(B)

證明於下。對於任意 \mathbf{x}\neq\mathbf{0},從 Rayleigh 定理可知

\lambda_{1}(B)\ge\frac{\mathbf{x}^{\ast}B\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}\ge\lambda_{n}(B)

根據 Courant-Fischer 定理的最小-最大原則,對於 k=1,\ldots,n

\begin{aligned} \displaystyle\lambda_{k}(A+B)&=\min_{\mathcal{W}_{k-1}}\max_{\mathbf{x}\perp\mathcal{W}_{k-1}\atop{\mathbf{x}\neq\mathbf{0}}}\frac{\mathbf{x}^{\ast}(A+B)\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}\\  &=\min_{\mathcal{W}_{k-1}}\max_{\mathbf{x}\perp\mathcal{W}_{k-1}\atop{\mathbf{x}\neq\mathbf{0}}}\left(\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}+\frac{\mathbf{x}^{\ast}B\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}\right)\\  &\le\min_{\mathcal{W}_{k-1}}\max_{\mathbf{x}\perp\mathcal{W}_{k-1}\atop{\mathbf{x}\neq\mathbf{0}}}\left(\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}+\lambda_1(B)\right)\\ &=\lambda_k(A)+\lambda_1(B)\end{aligned}

使用 Courant-Fischer 定理的最大-最小原則,以類似論證方式也可以得到下界:

\begin{aligned}\displaystyle \lambda_{k}(A+B)&=\max_{\mathcal{W}_{n-k}}\min_{\mathbf{x}\perp\mathcal{W}_{n-k}\atop{\mathbf{x}\neq\mathbf{0}}}\frac{\mathbf{x}^{\ast}(A+B)\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}\\  &=\max_{\mathcal{W}_{n-k}}\min_{\mathbf{x}\perp\mathcal{W}_{n-k}\atop{\mathbf{x}\neq\mathbf{0}}}\left(\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}+\frac{\mathbf{x}^{\ast}B\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}\right)\\  &\ge\max_{\mathcal{W}_{n-k}}\min_{\mathbf{x}\perp\mathcal{W}_{n-k}\atop{\mathbf{x}\neq\mathbf{0}}}\left(\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}+\lambda_n(B)\right)\\ &=\lambda_k(A)+\lambda_n(B)\end{aligned}

 
Weyl 定理的一個立即應用是 Hermitian 矩陣的特徵值擾動 (eigenvalue perturbation) 問題。對於一 n\times n 階矩陣 A,我們稱最大特徵值之絕對值為譜半徑 (spectral radius),記為

\rho(A)=\max\{\vert\lambda_1(A)\vert,\ldots,\vert\lambda_n(A)\vert\}

AB 皆為 n\times n 階 Hermitian,由 Weyl 定理可得

\lambda_1(B)\ge\lambda_k(A+B)-\lambda_k(A)\ge\lambda_{n}(B)

\lambda_1(B)\ge\cdots\ge\lambda_n(B),因此 \rho(B)=\mathrm{max}\{\vert\lambda_1(B)\vert,\vert\lambda_n(B)\vert\}。對於 k=1,\ldots,n,就有

\vert\lambda_k(A+B)-\lambda_k(A)\vert\le\rho(B)

上式的意義為 Hermitian 矩陣 A 是完全受約束的,在另一個 Hermitian 矩陣 B 的擾動下,A 的特徵值改變量必不大於 B 的譜半徑 \rho(B)

 
Courant-Fischer 定理的第二個應用稱為共邊 (bordered) 矩陣的 Cauchy 交錯特徵值 (interlaced eigenvalues) 定理。設 A 為一 n\times n 階 Hermitian 矩陣,\mathbf{b}\in\mathbb{C}^nc\in\mathbb{R}。令 (n+1)\times (n+1) 階共邊 Hermitian 矩陣 B

B=\begin{bmatrix}  A&\mathbf{b}\\  \mathbf{b}^{\ast}&c  \end{bmatrix}

矩陣 A 即為 B 的左上 n\times n 階主子陣。

 
Cauchy 交錯特徵值定理

An\times n 階 Hermitian 矩陣,B(n+1)\times(n+1) 階共邊 Hermitian 矩陣,特徵值分別表示為 \lambda_i(A)\lambda_i(B),並按遞減方式排序 \lambda_1(A)\ge\cdots\ge\lambda_n(A)\lambda_1(B)\ge\cdots\ge\lambda_{n}(B)\ge\lambda_{n+1}(B),則

\lambda_1(B)\ge\lambda_1(A)\ge\lambda_2(B)\ge\lambda_2(A)\ge\cdots\ge\lambda_{n}(B)\ge\lambda_{n}(A)\ge\lambda_{n+1}(B)

對於每個 1\le k\le n,我們將證明 \lambda_k(B)\ge\lambda_k(A)\ge\lambda_{k+1}(B)。令 \mathcal{W}_{k}\mathbb{C}^{n} 中的 k 維子空間,\mathcal{W}^{\prime}_{k}\mathbb{C}^{n+1} 中的 k 維子空間。設 \mathbf{y}=\begin{bmatrix}  \mathbf{x}\\  \xi  \end{bmatrix},其中 \mathbf{x}\in\mathbb{C}^n\xi\in\mathbb{C}。Courant-Fischer 定理的最小-最大原則給出

\displaystyle\lambda_{k}(B)=\min_{\mathcal{W}^{\prime}_{k-1}}\max_{\mathbf{y}\perp\mathcal{W}^{\prime}_{k-1}\atop{\mathbf{y}\neq\mathbf{0}}}\frac{\mathbf{y}^{\ast}B\mathbf{y}}{\mathbf{y}^{\ast}\mathbf{y}}

如果限制 \xi=0,縮減 \mathbf{y} 的搜尋空間將使極大值減小,所以

\begin{aligned} \displaystyle\lambda_{k}(B)&\ge\min_{\mathcal{W}^{\prime}_{k-1}}\max_{\mathbf{y}\perp\mathcal{W}^{\prime}_{k-1}\atop{\mathbf{y}\neq\mathbf{0},~\xi=0}}\frac{\mathbf{y}^{\ast}B\mathbf{y}}{\mathbf{y}^{\ast}\mathbf{y}}\\  &=\min_{\mathcal{W}_{k-1}}\max_{\mathbf{x}\perp\mathcal{W}_{k-1}\atop{\mathbf{x}\neq\mathbf{0}}}\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}=\lambda_k(A)\end{aligned}

再由 Courant-Fischer 定理的最大-最小原則,

\displaystyle\lambda_{k+1}(B)=\max_{\mathcal{W}^{\prime}_{(n+1)-(k+1)}}\min_{\mathbf{y}\perp\mathcal{W}^{\prime}_{(n+1)-(k+1)}\atop{\mathbf{y}\neq\mathbf{0}}}\frac{\mathbf{y}^{\ast}B\mathbf{y}}{\mathbf{y}^{\ast}\mathbf{y}}

同樣限制 \xi=0,縮減 \mathbf{y} 的搜尋空間將使極小值變大,故

\begin{aligned} \lambda_{k+1}(B)&\le\displaystyle\max_{\mathcal{W}^{\prime}_{n-k}}\min_{\mathbf{y}\perp\mathcal{W}^{\prime}_{n-k}\atop{\mathbf{y}\neq\mathbf{0},~\xi=0}}\frac{\mathbf{y}^{\ast}B\mathbf{y}}{\mathbf{y}^{\ast}\mathbf{y}}\\  &=\max_{\mathcal{W}_{n-k}}\min_{\mathbf{x}\perp\mathcal{W}_{n-k}\atop{\mathbf{x}\neq\mathbf{0}}}\frac{\mathbf{x}^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}=\lambda_k(A)\end{aligned}

 
設想我們在 n\times n 階 Hermitian 方陣加入一列和一行於最末列和最末行,交錯特徵值定理說明了 (n+1)\times(n+1) 階共邊矩陣與原矩陣的特徵值關係,但我們也可以視之為刪除 (n+1)\times(n+1) 階 Hermitian 方陣的最末列和最末行之後的矩陣特徵值關係。既然如此,沒有理由堅持非得刪除最末列和最末行不可,事實上,交錯特徵值定理適用於刪除任何列指標和行指標 i 的情況,證明與前述過程相同,只需將向量 \mathbf{y} 取代為 \mathbf{y}=(x_1,\ldots,x_{i-1},\xi,x_i,\ldots,x_n) 即可,\xi 為第 i 個元素。下面以一個例子說明交錯特徵值定理,考慮對稱矩陣

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

同時將 A_4 的列指標 3 和行指標 3 刪除可得到三階主子陣,如下:

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

矩陣 A_3 的特徵值依序為 \lambda_1(A_3)=5+\sqrt{5}\lambda_2(A_3)=5\lambda_3(A_3)=5-\sqrt{5}A_4 的特徵值為 \lambda_1(A_4)=8\lambda_2(A_4)=6\lambda_3(A_4)=4\lambda_4(A_4)=2,檢查確認二矩陣的特徵值滿足交錯關係:

8\ge 5+\sqrt{5}\ge 6\ge 5\ge 4\ge 5-\sqrt{5}\ge 2

 
如果刪除 n\times n 階 Hermitian 矩陣 An-r 個相同列指標與行指標,結果為一個 r\times r 階主子陣,記作 A_r。(主子陣的例子請見“正定矩陣的性質與判別方法”。) 重複運用上述交錯特徵值定理可界定主子陣 A_r 的特徵值範圍為

\lambda_k(A)\ge\lambda_k(A_r)\ge\lambda_{k+n-r}(A)

此式稱為包含原則 (inclusion principle)。上例中,將 A_3 的列指標 2 和行指標 2 刪除得到二階矩陣:

A_2=\left[\!\!\begin{array}{rr}  5&-2\\  -2&5  \end{array}\!\!\right]

其特徵值為 \lambda_1(A_2)=7\lambda_2(A_2)=3。應用交錯特徵值定理於 A_2A_3,就有

\lambda_1(A_3)\ge\lambda_1(A_2)\ge\lambda_2(A_3)\ge\lambda_2(A_2)\ge\lambda_3(A_3)

再應用交錯特徵值定理於 A_3A_4

\lambda_1(A_4)\ge\lambda_1(A_3)\ge\lambda_2(A_4)\ge\lambda_2(A_3)\ge\lambda_3(A_4)\ge\lambda_3(A_3)\ge\lambda_4(A_4)

合併上面兩個式子便可比較 A_2A_4 的特徵值大小。針對 \lambda_1(A_2),有不等關係

\lambda_1(A_4)\ge\lambda_1(A_3)\ge\lambda_1(A_2)\ge\lambda_2(A_3)\ge\lambda_3(A_4)

也就有 \lambda_1(A_4)\ge\lambda_1(A_2)\ge\lambda_3(A_4);針對 \lambda_2(A_2),則有

\lambda_2(A_4)\ge\lambda_2(A_3)\ge\lambda_2(A_2)\ge\lambda_3(A_3)\ge\lambda_4(A_4)

因此可得 \lambda_2(A_4)\ge\lambda_2(A_2)\ge\lambda_4(A_4)

Advertisements
本篇發表於 線性代數專欄, 二次型 並標籤為 , , , , , , 。將永久鏈結加入書籤。

發表迴響

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

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s