特殊矩陣 (18)：正矩陣

本文的閱讀等級：高級

令 $A=[a_{ij}]$ 為一 $m\times n$ 階實矩陣。若每一 $a_{ij}>0$ ，我們稱 $A$ 是正矩陣 (positive matrix)，記為 $A>0$ 。(注意，在其他文章我用 $A\succ 0$ 表示 $A$ 是正定矩陣。) 若每一 $a_{ij}\ge 0$ ，則 $A$ 稱為非負矩陣 (nonnegative matrix)，記為 $A\ge 0$ 。推廣至更一般的情況， $A>B$ 代表每一 $a_{ij}>b_{ij}$ ， $A\ge B$ 代表每一 $a_{ij}\ge b_{ij}$ 。因為 $m$ 維實向量可視為 $m\times 1$ 階矩陣，故同樣有正向量和非負向量的概念。相反關係 $<$ 和 $\le$ 也按類似方式定義。正矩陣和非負矩陣出現於許多應用問題中，例如，馬可夫過程 (見“馬可夫過程”) 和圖論模型的鄰接矩陣 (見“Google 搜尋引擎使用的矩陣運算”，“線性代數在圖論的應用 (一)：鄰接矩陣”)。本文介紹 $n\times n$ 階正矩陣的特徵值和特徵向量性質，這些結果統稱為 Perron 定理^[1]。

Oskar Perron (1880–1975) From http://upload.wikimedia.org/wikipedia/commons/0/0b/Oskar_Perron.jpg

正矩陣的特徵分析與一般矩陣的主要差異在於大量運用不等性質。開始討論之前，我們說明幾個稍後將會使用的不等式。令 $A$ 為一 $n\times n$ 階矩陣， $\mathbf{x},\mathbf{y}\in\mathbb{R}^n$ 。為簡化符號，我們定義 $\vert A\vert\equiv[\vert a_{ij}\vert]$ 和 $\vert\mathbf{x}\vert\equiv[\vert x_i\vert]$ ，其中 $\vert\cdot\vert$ 是絕對值運算。請特別注意，本文中 $\vert A\vert$ 並不表示行列式。

(1) 若 $A>0$ ， $\mathbf{x}\ge\mathbf{0}$ ，且 $\mathbf{x}\neq\mathbf{0}$ ，直接計算可證明 $A\mathbf{x}>\mathbf{0}$ 。

(2) 若 $A\ge 0$ ， $A\neq 0$ ，且 $\mathbf{x}>\mathbf{y}>\mathbf{0}$ ，則 $A\mathbf{x}>A\mathbf{y}$ ；類似地，若 $A\ge 0$ 且 $\mathbf{x}\ge\mathbf{y}\ge\mathbf{0}$ ，則 $A\mathbf{x}\ge A\mathbf{y}$ 。

(3) 利用三角不等式，可得 $\vert A\mathbf{x}\vert\le\vert A\vert ~\vert\mathbf{x}\vert$ 。寫出 $A$ 的行向量表達式 $A=\begin{bmatrix} \mathbf{a}_1&\cdots&\mathbf{a}_n \end{bmatrix}$ ，推演過程如下：

$\begin{aligned} \vert A\mathbf{x}\vert&=\left|x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n\right|\\ &\le \vert x_1\mathbf{a}_1\vert+\cdots+\vert x_n\mathbf{a}_n\vert\\ &=\vert x_1\vert~\vert\mathbf{a}_1\vert+\cdots+\vert x_n\vert~\vert\mathbf{a}_n\vert\\ &=\vert A\vert~\vert\mathbf{x}\vert. \end{aligned}$

令 $\sigma(A)$ 是 $A$ 的所有相異特徵值所成的集合，稱為矩陣譜 (spectrum)，並令 $\rho(A)$ 是 $A$ 的最大絕對特徵值，稱為譜半徑 (spectral radius)，即 $\rho(A)=\max_{\lambda\in\sigma(A)}\vert\lambda\vert$ 。

性質一：正矩陣 $A$ 的譜半徑 $\rho(A)>0$ 是一特徵值，且對應 $\rho(A)$ 的特徵向量是一正向量。

若 $A>0$ ，先證明 $\rho(A)>0$ 。假設 $\rho(A)=0$ ，則 $\sigma(A)=\{0\}$ ， $A$ 的所有特徵值皆為 $0$ ，等於宣告 $A$ 是一冪零 (nilpotent) 矩陣。但是，每一 $a_{ij}>0$ ，因此不可能存在一正整數 $k$ 使得 $A^k=0$ (見“特殊矩陣 (1)：冪零矩陣”)，證明假設是錯誤的，故 $\rho(A)>0$ 。若 $A\mathbf{x}=\lambda\mathbf{x}$ ， $\vert\lambda\vert=\rho(A)$ ，且 $\mathbf{x}\neq\mathbf{0}$ ，利用不等性質 (3)，

$\rho(A)\vert\mathbf{x}\vert=\vert\lambda\vert~\vert\mathbf{x}\vert=\vert\lambda\mathbf{x}\vert=\vert A\mathbf{x}\vert\le\vert A\vert~\vert\mathbf{x}\vert=A\vert\mathbf{x}\vert$ ，

故 $\mathbf{y}=A\vert\mathbf{x}\vert-\rho(A)\vert\mathbf{x}\vert\ge 0$ 。我們的目標是要證明等號成立。假設 $\mathbf{y}\neq\mathbf{0}$ ，利用不等性質 (1)，可知 $A\mathbf{y}>0$ 且 $A\vert\mathbf{x}\vert>0$ 。因此，存在 $\epsilon>0$ 使得 $A\mathbf{y}>\epsilon \rho(A)A\vert\mathbf{x}\vert$ ，或寫成

$\displaystyle \frac{A}{\rho(A)(1+\epsilon)}A\vert\mathbf{x}\vert>A\vert\mathbf{x}\vert$ 。

為簡化符號，令 $B=\rho(A)^{-1}(1+\epsilon)^{-1}A$ 且 $\mathbf{z}=A\vert\mathbf{x}\vert$ ，則有 $B\mathbf{z}>\mathbf{z}>0$ 。因為 $B>0$ ，利用不等性質 (2)，依序可得

$B^2\mathbf{z}>B\mathbf{z}>\mathbf{z},~~B^3\mathbf{z}>B^2\mathbf{z}>B\mathbf{z}>\mathbf{z},\ldots$

亦即 $B^k\mathbf{z}>\mathbf{z}$ ， $k=1,2,\ldots$ 。另一方面，

$\displaystyle \rho(B)=\frac{1}{1+\epsilon}<1$ ，

這意味 $\lim_{k\to\infty}B^k=0$ (見“譜半徑與矩陣範數”)。當 $k$ 趨於無窮大時， $\mathbf{0}>\mathbf{z}$ ，但這與事實 $\mathbf{z}>\mathbf{0}$ 相矛盾，也就是說，最初的假設 $\mathbf{y}\neq\mathbf{0}$ 並不成立，故得 $\rho(A)\vert\mathbf{x}\vert=A\vert\mathbf{x}\vert$ 。根據譜半徑定義，必存在一特徵值 $\lambda$ 使得 $\vert\lambda\vert=\rho(A)$ ，故證明 $\rho(A)$ 是 $A$ 的特徵值，對應的特徵向量是正向量，即 $\vert\mathbf{x}\vert=\rho(A)^{-1}A\vert\mathbf{x}\vert>\mathbf{0}$ 。

性質二：除了 $\rho(A)$ ，正矩陣 $A$ 不存在其他特徵值 $\lambda$ 使得 $\vert\lambda\vert=\rho(A)$ 。

換一個說法，對於每一特徵值 $\lambda\neq\rho(A)$ ， $\vert\lambda\vert0$ ， $A\mathbf{x}=\lambda\mathbf{x}$ ， $\vert\lambda\vert=\rho(A)$ ，且 $\mathbf{x}\neq\mathbf{0}$ ，由性質一可知 $A\vert\mathbf{x}\vert=\rho(A)\vert\mathbf{x}\vert$ ， $\vert\mathbf{x}\vert>\mathbf{0}$ 。另外， $\vert A\mathbf{x}\vert=\vert\lambda\mathbf{x}\vert=\vert\lambda\vert~\vert\mathbf{x}\vert=\rho(A)\vert\mathbf{x}\vert$ 。合併以上結果，使用三角不等式，可得

$\displaystyle \begin{aligned} \rho(A)\vert x_k\vert&=\vert\lambda\vert~\vert x_k\vert=\vert\lambda x_k\vert=\left|\sum_{j=1}^n{a}_{kj}x_j\right|\\ &\le\sum_{j=1}^n\vert{a}_{kj}\vert~\vert x_j\vert =\sum_{j=1}^n{a}_{kj}\vert x_j\vert=\rho(A)\vert x_k\vert.\end{aligned}$

上面不等式兩端相等，這說明在複數平面上 $a_{kj}x_j$ ， $j=1,\ldots,n$ ，位在由原點射出的同一直線上。換句話說，它們有相同的角度，設為 $\theta$ ，則 $e^{-i\theta}a_{kj}x_j>0$ ， $j=1,\ldots,n$ ，其中 $i=\sqrt{-1}$ 。因為所有 $a_{kj}>0$ ，可知 $\mathbf{v}=e^{-i\theta}\mathbf{x}>\mathbf{0}$ 。上式左乘 $A$ ，就有 $A\mathbf{v}=e^{-i\theta}A\mathbf{x}=e^{-i\theta}\lambda\mathbf{x}=\lambda\mathbf{v}$ 。因為 $A>0$ 且 $\mathbf{v}=\vert\mathbf{v}\vert$ ，

$A\mathbf{v}=\vert A\mathbf{v}\vert=\vert\lambda\mathbf{v}\vert=\vert\lambda\vert~\vert\mathbf{v}\vert=\rho(A)\mathbf{v}$ ，

即知 $\lambda=\rho(A)$ ，故證得所求。

接下來我們討論正矩陣的特徵值 $\rho(A)$ 的指標 (index)、代數重數和幾何重數。所謂特徵值 $\lambda$ 的指標是指對應 $\lambda$ 的最大基本 Jordan 分塊階數 (見“Jordan 形式大解讀 (上)”)。

性質三：正矩陣 $A$ 的特徵值 $\rho(A)$ 的指標等於 $1$ 。

假設正矩陣 $A$ 的特徵值 $\rho(A)$ 指標是 $m>1$ 。令 $B=[b_{ij}]=\rho(A)^{-1}A$ ，則 $B>0$ ， $\rho(B)=1$ 是 $B$ 的特徵值且指標為 $m$ 。證明包含兩個步驟：當 $k\to\infty$ ，由 $m>1$ 可推得 $\Vert B^k\Vert_{\infty}\to\infty$ ，其中 $\infty$ -矩陣範數定義為 (見“矩陣範數”)

$\displaystyle \Vert B\Vert_{\infty}=\max_{1\le i\le n}\sum_{j=1}^n\vert b_{ij}\vert$ ；

使用反證法。考慮 $B$ 的 Jordan 形式 $B=MJM^{-1}$ ，其中 Jordan 矩陣 $J$ 的冪矩陣包含最大基本 Jordan 分塊的冪矩陣：

$\displaystyle J_{\ast}^k(\lambda)=\begin{bmatrix} \lambda^k&\binom{k}{1}\lambda^{k-1}&\binom{k}{2}\lambda^{k-2}&\cdots&\binom{k}{m-1}\lambda^{k-m+1}\\ &\lambda^k&\binom{k}{1}\lambda^{k-1}&\ddots&\vdots\\ &&\ddots&\ddots&\binom{k}{2}\lambda^{k-2}\\[0.5em] &&&\lambda^k&\binom{k}{1}\lambda^{k-1}\\ &&&&\lambda^k \end{bmatrix}$ 。

若 $\lambda=\rho(B)=1$ 且 $J_{\ast}^k(1)$ 是 $m\times m$ 階， $m>1$ ，則 $\lim_{k\to\infty}\Vert J_{\ast}^k(1)\Vert_{\infty}=\infty$ ，也就有 $\lim_{k\to\infty}\Vert J^k\Vert_{\infty}=\infty$ 。因為

$\Vert J^k\Vert_{\infty}=\Vert M^{-1}B^kM\Vert_{\infty}\le\Vert M^{-1}\Vert_{\infty}\Vert B^k\Vert_\infty\Vert M\Vert_\infty$ ，

立得

$\displaystyle \Vert B^k\Vert_\infty\ge\frac{\Vert J^k\Vert_\infty}{\Vert M^{-1}\Vert_\infty\Vert M\Vert_\infty}=\infty$ 。

令 $B^k=\left[b_{ij}^{(k)}\right]$ ，並設 $p$ 使得 $\Vert B^k\Vert_\infty=\sum_{j=1}^nb_{pj}^{(k)}$ 。因為 $B^k>0$ ，利用性質一，存在 $\mathbf{v}>0$ 使得 $B^k\mathbf{v}=\mathbf{v}$ 。所以，當 $k\to\infty$ ，

$\displaystyle \Vert\mathbf{v}\Vert_\infty\ge v_p=\sum_{j=1}^nb_{kj}^{(k)}v_j\ge\left(\sum_{j=1}^nb_{pj}^{(k)}\right)\min_{1\le i\le n}v_i=\Vert B^k\Vert_\infty\min_{1\le i\le n}v_i\to\infty$ 。

但這與 $\mathbf{v}$ 是一常數向量相矛盾，故 $m>1$ 不為真，證得 $\rho(B)=1$ 的指標等於 $1$ ，同義於 $\rho(A)$ 的指標為 $1$ 。

性質四：正矩陣 $A$ 的特徵值 $\rho(A)$ 的代數重數 (和幾何重數) 等於 $1$ 。

性質四等價於正矩陣 $B=\rho(A)^{-1}A$ 的特徵值 $\rho(B)=1$ 的代數重數 (和幾何重數) 等於 $1$ 。為方便說明，我們仍用矩陣 $B$ 來證明。根據性質三，若 $B>0$ ， $\rho(B)=1$ 的指標等於 $1$ ，可知代數重數等於幾何重數，因此我們僅需要證明特徵值 $1$ 的代數重數為 $1$ 即可 (縱使不使用性質三，代數重數等於 $1$ 即可推論幾何重數等於 $1$ )。使用反證法，假設 $B$ 的特徵值 $1$ 的代數重數是 $\beta>1$ ，可知 $B$ 有 $\beta$ 個線性獨立特徵向量對應特徵值 $1$ 。令 $A\mathbf{x}=\mathbf{x}$ ， $A\mathbf{y}=\mathbf{y}$ ，且對於任一 $c\in\mathbb{C}$ ， $\mathbf{x}\neq c\mathbf{y}$ 。設 $y_i\neq 0$ ，令 $\mathbf{v}=\mathbf{x}-(x_i/y_i)\mathbf{y}$ ，則 $B\mathbf{v}=B\mathbf{x}-(x_i/y_i)A\mathbf{y}=\mathbf{x}-(x_i/y_i)\mathbf{y}=\mathbf{v}$ 。利用性質一，可得 $B\vert \mathbf{v}\vert=\vert\mathbf{v}\vert>0$ ，但這與事實 $v_i=x_i-(x_i/y_i)y_i=0$ 相矛盾，可見最初假設 $\beta>1$ 並不成立，故得證。

性質四指出 $\dim N(A-\rho(A)I)=1$ ，對應特徵值 $\rho(A)$ ，僅存在唯一的特徵向量 $\mathbf{x}\in N(A-\rho(A)I)$ 使得 $\sum_{i=1}^nx_i=1$ 。對於 $A>0$ ，我們稱此「正規化」的特徵向量 $\mathbf{x}$ 為 Perron 向量，對應的特徵值 $\rho(A)$ 則稱為 Perron 根。正矩陣 $A$ 可推得 $A^T>0$ ，且 $\rho(A)=\rho(A^T)$ (因為 $A$ 和 $A^T$ 有相同的特徵值集合)， $A^T$ 也存在唯一的 Perron 向量 $\mathbf{y}>0$ 使得 $A^T\mathbf{y}=\rho(A)\mathbf{y}$ ，取轉置可得 $\mathbf{y}^TA=\rho(A)\mathbf{y}^T$ ，故 $\mathbf{y}$ 亦稱為 $A>0$ 的左 Perron 向量。

性質五：除了對應特徵值 $\rho(A)$ 的正特徵向量，正矩陣 $A$ 不存在其他非負特徵向量。

這個性質也可以這麼說：對應 $A>0$ 的特徵值 $\lambda\neq\rho(A)$ 的特徵向量必不是非負向量。令 $\mathbf{y}>0$ 是 $A>0$ 的左 Perron 向量， $\mathbf{y}^TA=\rho(A)\mathbf{y}^T$ 。若 $A\mathbf{x}=\lambda\mathbf{x}$ ， $\mathbf{x}\ge\mathbf{0}$ ，由不等性質 (1)， $\mathbf{y}^T\mathbf{x}>0$ ，而且

$\rho(A)\mathbf{y}^T\mathbf{x}=\mathbf{y}^TA\mathbf{x}=\lambda\mathbf{y}^T\mathbf{x}$ ，

故知 $\rho(A)=\lambda$ ，因此證得所求。

下面性質給出正矩陣 $A$ 的譜半徑 $\rho(A)$ 界定公式，稱為 Collatz-Wielandt 公式^[2]。

性質六：若 $A>0$ ，則 $\rho(A)=\max_{\mathbf{x}\in S}\Psi(\mathbf{x})$ ，其中 $S=\{\mathbf{x}\vert\mathbf{x}\ge\mathbf{0},~\mathbf{x}\neq\mathbf{0}\}$ 且

$\displaystyle \Psi(\mathbf{x})=\min_{1\le i\le n\atop x_i\neq 0}\frac{(A\mathbf{x})_i}{x_i}$ 。

若 $A>0$ 且 $\mathbf{z}\in S$ ，根據函數 $\Psi$ 的定義，顯然有 $A\mathbf{z}\ge \Psi(\mathbf{z})\mathbf{z}\ge \mathbf{0}$ 。令 $\mathbf{x}$ 和 $\mathbf{y}$ 分別是對應 $\rho(A)$ 的 Perron 向量和左 Perron 向量。利用不等性質 (1)，可得 $\mathbf{y}^T\mathbf{z}>0$ ，再使用不等性質 (2)，

$\Psi(\mathbf{z})\mathbf{y}^T\mathbf{z}\le\mathbf{y}^TA\mathbf{z}=\rho(A)\mathbf{y}^T\mathbf{z}$ ，

推知 $\Psi(\mathbf{z})\le\rho(A)$ 。因為 $\mathbf{x}\in S$ 且 $A\mathbf{x}=\rho(A)\mathbf{x}$ ，故得 $\Psi(\mathbf{x})=\rho(A)$ ，證畢。

本文得到的所有正矩陣特徵值和特徵向量性質統稱為 Perron 定理。

Perron 定理：若 $A$ 是一 $n\times n$ 階正矩陣，以下性質成立：

譜半徑 $\rho(A)>0$ 是 $A$ 的一特徵值，稱為 Perron 根。
$\rho(A)$ 的代數重數 (和幾何重數) 等於 $1$ 。
存在唯一 $\mathbf{x}>\mathbf{0}$ ，稱為 Perron 向量，使得 $A\mathbf{x}=\rho(A)\mathbf{x}$ 且 $\Vert\mathbf{x}\Vert_1=1$ ，即 $\sum_{i=1}^nx_i=1$ 。
對於 $A$ 的每一特徵值 $\lambda\neq\rho(A)$ ， $\vert\lambda\vert<\rho(A)$ 。
對應特徵值 $\lambda\neq\rho(A)$ 的特徵向量不為非負向量。
令 $S=\{\mathbf{x}\vert\mathbf{x}\ge\mathbf{0},~\mathbf{x}\neq\mathbf{0}\}$ 。Collatz-Wielandt 公式給出

$\displaystyle \rho(A)=\max_{\mathbf{x}\in S}\min_{1\le i\le n\atop x_i\neq 0}\frac{(A\mathbf{x})_i}{x_i}$ 。

最後我們舉一個例子展示 Perron 定理：

$A=\begin{bmatrix} 9&1&2\\ 3&7&2\\ 3&1&8 \end{bmatrix}$

有特徵值 $12, 6, 6$ ，對應的特徵向量為 $(1,1,1)^T, (-1,3,0)^T, (-1,0,3)^T$ 。Perron 根，即譜半徑，是 $12$ ；Perron 根 $12$ 的代數重數等於 $1$ ；Perron 向量為 $(1/3,1/3,1/3)^T$ ；除了 Perron 根，其他特徵值 $6, 6$ 的絕對值小於 $12$ ；對應特徵值 $6$ 的特徵向量 $(-1,3,0)^T, (-2,0,3)^T$ 不為非負向量。

參考來源：
[1] Roger A. Horn and Charles R. Johnson, Matrix Analysis, 1985, pp 490-501.
[2] Carl Meyer, Matrix Analysis and Applied Linear Algebra, 2004, pp 663-667.

2 Responses to 特殊矩陣 (18)：正矩陣

耿阳 says:

06/25/2017 at 10:43 am

周老師，您好！非常感謝精彩的證明，看到您的blog仿佛发现了新天地，以后我会常来瞻仰您的佳作。
另外，关于这篇文章，有幾個我感觉存在问题的地方还想和您确认一下。
1. 性質二證明第一列(row)，“\vert\lambda\vert 0” 是多餘的？
2. 性質三證明導數第三列式子中，左起第三項求和中“b_{kj}^{(k)}v_j”應該是“b_{pj}^{(k)}v_j”？
3. 性質四證明第五列中，“A\mathbf{x}=\mathbf{x},A\mathbf{y}=\mathbf{y}”應該是“B\mathbf{x}=\mathbf{x},B\mathbf{y}=\mathbf{y}”？
4.性質四證明第七列中，“B\mathbf{x}-(x_i/y_i)A\mathbf{y}”應該是“B\mathbf{x}-(x_i/y_i)B\mathbf{y}”？

- ccjou says:
  
  06/26/2017 at 3:17 pm
  
  本文部分排版似乎有問題，等有空時再重勘修訂。

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨