特殊矩陣 (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]

 
正矩陣的特徵分析與一般矩陣的主要差異在於大量運用不等性質。開始討論之前,我們說明幾個稍後將會使用的不等式。令 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 0A\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}>0A\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\vert0A\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_jj=1,\ldots,n,位在由原點射出的同一直線上。換句話說,它們有相同的角度,設為 \theta,則 e^{-i\theta}a_{kj}x_j>0j=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)=1B 的特徵值且指標為 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)=1J_{\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) (因為 AA^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}>0A>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 SA\mathbf{x}=\rho(A)\mathbf{x},故得 \Psi(\mathbf{x})=\rho(A),證畢。

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

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

  1. 譜半徑 \rho(A)>0A 的一特徵值,稱為 Perron 根。
  2. \rho(A) 的代數重數 (和幾何重數) 等於 1
  3. 存在唯一 \mathbf{x}>\mathbf{0},稱為 Perron 向量,使得 A\mathbf{x}=\rho(A)\mathbf{x}\Vert\mathbf{x}\Vert_1=1,即 \sum_{i=1}^nx_i=1
  4. 對於 A 的每一特徵值 \lambda\neq\rho(A)\vert\lambda\vert<\rho(A)
  5. 對應特徵值 \lambda\neq\rho(A) 的特徵向量不為非負向量。
  6. 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):正矩陣

  1. 耿阳 說道:

    周老師,您好!非常感謝精彩的證明,看到您的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}”?

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s