特殊矩陣 (21):非負矩陣

本文的閱讀等級:高級

A=[a_{ij}] 為一個 m\times n 階實矩陣。若每一 a_{ij}>0,我們稱 A 是正矩陣 (positive matrix),記為 A>0。若每一 a_{ij}\ge 0,則 A 稱為非負矩陣 (nonnegative matrix),記為 A\ge 0。推廣至更一般的情況,A>B 表示每一 a_{ij}>b_{ij}A\ge B 表示每一 a_{ij}\ge b_{ij}。因為 n 維實向量可視為 n\times 1 階實矩陣,故同樣有正向量和非負向量的概念。相反關係 <\le 也按類似方式定義。令 \sigma(A)A 的所有相異特徵值所形成的集合,稱為矩陣譜 (spectrum),並令 \rho(A)A 的最大絕對特徵值,稱為譜半徑 (spectral radius),即 \rho(A)=\max_{\lambda\in\sigma(A)}\vert\lambda\vert。若 A 是一個 n\times n 階正矩陣,Perron 定理包含下列特徵值和特徵向量性質 (見“特殊矩陣 (18):正矩陣”):

  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} 0&1\\ 0&0 \end{bmatrix} 有相重特徵值 0\rho(A)=0,對應的特徵向量為 \begin{bmatrix} 1\\ 0 \end{bmatrix},性質 (1),(2),(3) 不成立;B=\begin{bmatrix} 0&1\\ 1&0 \end{bmatrix} 有特徵值 1, -1\rho(B)=1,對應的特徵向量分別為 \begin{bmatrix} 1\\ 1 \end{bmatrix}\left[\!\!\begin{array}{r} -1\\ 1 \end{array}\!\!\right],性質 (4) 不成立;C=\begin{bmatrix} 0&1\\ 0&1 \end{bmatrix} 有特徵值 1,0\rho(C)=1,對應的特徵向量分別為 \begin{bmatrix} 1\\ 1 \end{bmatrix}\begin{bmatrix} 1\\ 0 \end{bmatrix},性質 (5) 不成立。

 
本文包含兩個主題。第一,在不引進任何條件的情況下,將應用於正矩陣的 Perron 定理推廣至非負矩陣。除了性質 (6) 維持不變,性質 (1) 和 (3) 依然可通過操作極限的方式延伸至非負矩陣,但 > 必須替換為 \ge 。第二,加入適當的限制至非負矩陣使得 Perron 定理得以盡可能原封不動地保留,這個結果稱為 Perron-Frobenius 定理。

 
性質一:非負矩陣 A 的譜半徑 \rho(A)\ge 0 是一個特徵值,且存在一對應 \rho(A) 的非負特徵向量,即 \mathbf{x}\ge \mathbf{0}\mathbf{x}\neq\mathbf{0}

n\times n 階矩陣 A\ge 0。令 A(\epsilon)=A+\epsilon J,其中 J 的所有元為 1。對於任一 \epsilon>0A(\epsilon)>0。令 \mathbf{x}(\epsilon)>\mathbf{0}A(\epsilon) 的 Perron 向量使得 A(\epsilon)\mathbf{x}(\epsilon)=\rho(A(\epsilon))\mathbf{x}(\epsilon)\Vert\mathbf{x}(\epsilon)\Vert_1=1 (正矩陣性質 (3))。因為 \mathbf{x}(\epsilon) 限定於有界緊集 \{\mathbf{y}\in\mathbb{C}^n\vert\Vert\mathbf{y}\Vert_1=1\},故存在一單調遞減數列 \epsilon_1\ge\epsilon_2\ge\cdots\lim_{k\to\infty}\epsilon_k=0 使得 \lim_{k\to\infty}\mathbf{x}(\epsilon_k) 存在,設為 \mathbf{x}。再由 \Vert\mathbf{x}\Vert_1=\lim_{k\to\infty}\sum_{i=1}^nx_i(\epsilon_k)=1,可知 \mathbf{x}\ge\mathbf{0}\mathbf{x}\neq\mathbf{0}。接下來我們要證明 A\mathbf{x}=\rho(A)\mathbf{x}。使用此性質 (見“譜半徑與矩陣範數”,例一):

\displaystyle B\ge C\ge 0~~\Rightarrow~~\rho(B)\ge\rho(C)

因為 A(\epsilon_1)>A(\epsilon_2)>\cdots>A\ge 0,可得 \rho(A(\epsilon_1))\ge\rho(A(\epsilon_2))\ge\cdots\ge\rho(A),也就是說,\{\rho(A(\epsilon_k))\}_1^\infty 是一個單調遞減非負數列。根據單調收斂定理,\lim_{k\to\infty}\rho(A(\epsilon_k)) 存在,設為 \rho,且 \rho\ge\rho(A)。然而,

\displaystyle\begin{aligned} A\mathbf{x}&=\lim_{k\to\infty}A(\epsilon_k)\mathbf{x}(\epsilon_k)=\lim_{k\to\infty}\rho(A(\epsilon_k))\mathbf{x}(\epsilon_k)\\ &=\lim_{k\to\infty}\rho(A(\epsilon_k))\lim_{k\to\infty}\mathbf{x}(\epsilon_k)=\rho\mathbf{x} \end{aligned}

\mathbf{x}\neq\mathbf{0} 表明 \rhoA 的一個特徵值,故 \rho\le\rho(A)。合併以上結果,推得 \rho=\rho(A),證畢。

 
Collatz-Wielandt 公式 (正矩陣性質 (6)),即正矩陣的譜半徑界定公式,對於非負矩陣仍然成立,但兩者的證明方法不同。

 
性質二:若 A\ge 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}

我們沿用性質一證明的記號。令 \mathbf{y}(\epsilon_k)>\mathbf{0}k=1,2,\ldots,為 A(\epsilon_k) 的左 Perron 向量使得 \mathbf{y}(\epsilon_k)^TA(\epsilon_k)=\rho(A(\epsilon_k))\mathbf{y}(\epsilon_k)^T。設 \mathbf{x}\in S,不難驗證 \mathbf{y}(\epsilon_k)^T\mathbf{x}>0,且 0\le\Psi(\mathbf{x})x_j\le(A\mathbf{x})_j\le(A(\epsilon_k)\mathbf{x})_j1\le j\le n,即有

\displaystyle \mathbf{0}\le\Psi(\mathbf{x})\mathbf{x}\le A\mathbf{x}\le A(\epsilon_k)\mathbf{x}

上式左乘 \mathbf{y}(\epsilon_k)^T

\displaystyle \mathbf{0}\le\Psi(\mathbf{x})\mathbf{y}(\epsilon_k)^T\mathbf{x}\le \mathbf{y}(\epsilon_k)^TA\mathbf{x}\le \mathbf{y}(\epsilon_k)^TA(\epsilon_k)\mathbf{x}=\rho(A(\epsilon_k))\mathbf{y}(\epsilon_k)^T\mathbf{x}

可知 \Psi(\mathbf{x})\le\rho(A(\epsilon_k)),故 \Psi(\mathbf{x})\le\lim_{k\to\infty}\rho(A(\epsilon_k))=\rho\le\rho(A)。根據性質一,如果我們令 \mathbf{x}A 的一個非負特徵向量對應特徵值 \rho(A),則 \Psi(\mathbf{x})=\rho(A),因此證明所求。

 
在不加入限制條件的情況下,一 n\times n 階矩陣 A\ge 0 僅滿足 Perron 定理的少部分性質:

  1. 譜半徑 \rho(A)\ge 0A 的一特徵值,稱為 Perron 根;
  2. 存在一 \mathbf{x}\ge\mathbf{0}\mathbf{x}\neq\mathbf{0},使得 A\mathbf{x}=\rho(A)\mathbf{x}\Vert\mathbf{x}\Vert_1=1,即 \sum_{i=1}^nx_i=1
  3. 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}

對於 A\ge 0\rho(A) 仍稱為 Perron 根 (縱使特徵值 \rho(A) 的代數重數未必等於 1)。因為 \rho(A) 的幾何重數可能大於 1,即對應 \rho(A) 的特徵向量不唯一決定,一般非負矩陣不存在「Perron 向量」。例如,I=\begin{bmatrix} 1&0\\ 0&1 \end{bmatrix} 有相重特徵值 1\rho(I)=1,任一非零向量皆為特徵向量。

 
進入第二主題,我們的目標是在非負矩陣中加入某些條件使得 Perron 定理的其他性質能夠成立。考慮 Perron 性質 (2),對於任一正矩陣 A\rho(A) 的代數重數等於 1。見下例,

\displaystyle A=\begin{bmatrix} 1&0\\ 1&1 \end{bmatrix},~~~A'=\begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}

矩陣 A 有相重特徵值 1A' 有相異特徵值 (1\pm\sqrt{5})/2。德國數學家弗羅貝尼烏斯 (Ferdinand Georg Frobenius) 發現這兩個非負矩陣的特徵值性質之所以不同,原因在於零元所在的位置。他界定出兩矩陣的差異在於 A 是可約矩陣 (reducible matrix),而 A' 是不可約矩陣 (irreducible matrix)。如果存在一排列矩陣 (permutation matrix) P 使得

\displaystyle   P^TAP=\begin{bmatrix}  B&C\\   0&D   \end{bmatrix}

其中 Br\times r 階,r\ge 1D(n-r)\times(n-r) 階,我們稱 A 為可約矩陣,否則稱之為不可約矩陣。上例中,A 是可約矩陣,因為

\displaystyle   P^TAP=\begin{bmatrix} 1&1\\ 0&1 \end{bmatrix}

其中 P=\begin{bmatrix} 0&1\\ 1&0 \end{bmatrix}。除了前述非負矩陣的三個性質,上例暗示不可約非負矩陣可能擁有更多的 Perron 性質。

 
為了證明猜想為真,我們需要這個不可約矩陣性質:令 A\ge 0 為一 n\times n 階矩陣。若 A 是不可約矩陣,則 (I+A)^{n-1}>0。相反方向的陳述同樣成立 (見“特殊矩陣 (18):可約矩陣”,定理二)。除了 Perron 性質 (4) 之外,我們可以證明不可約非負矩陣 A 繼承了正矩陣 (I+A)^{n-1} 的所有性質。這個結果稱為 Perron-Frobenius 定理。

Perron-Frobenius 定理:若 A\ge 0 是一 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. 對應特徵值 \lambda\neq\rho(A) 的特徵向量不為非負向量。
  5. 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}

先前已經確知 \rho(A)A 的一個特徵值,稍後將證明 \rho(A)>0。欲證明 (2),令 B=(I+A)^{n-1}。運用矩陣函數的 Jordan 形式可推論 \lambda\in\sigma(A) 等價於 (1+\lambda)^{n-1}\in\sigma(B) (見“矩陣函數 (下)”)。因此,\lambda 之於 A 的代數重數等於 (1+\lambda)^{n-1} 之於 B 的代數重數。計算可得

\displaystyle\begin{aligned} \rho(B)&=\max_{\lambda\in\sigma(A)}\vert 1+\lambda\vert^{n-1}=\left(\max_{\lambda\in\sigma(A)}\vert 1+\lambda\vert\right)^{n-1}\\ &=\left(1+\max_{\lambda\in\sigma(A)}\vert\lambda\vert\right)^{n-1}=(1+\rho(A))^{n-1}.\end{aligned}

因為 B>0,Perron 定理說 \rho(B) 的代數重數為 1,故知 \rho(A) 的代數重數也等於 1。欲證明 (3),設 A\mathbf{x}=\rho(A)\mathbf{x},由此推得

\displaystyle\begin{aligned} B\mathbf{x}&=(I+A)^{n-1}\mathbf{x}=\sum_{k=0}^{n-1}\binom{n-1}{k}A^k\mathbf{x}\\ &=\sum_{k=0}^{n-1}\binom{n-1}{k}(\rho(A))^k\mathbf{x}=(1+\rho(A))^{n-1}\mathbf{x}=\rho(B)\mathbf{x}. \end{aligned}

根據 Perron 定理,\mathbf{x}>0B 的 Perron 向量,此陳述等價於 \mathbf{x} 是對應 A 的特徵值 \rho(A) 的一個正特徵向量,即 Perron 向量。使用相同方式可證明 (4)。因為 A\mathbf{x}=\lambda\mathbf{x} 等價於 B\mathbf{x}=(1+\lambda)^{n-1}\mathbf{x},Perron 定理表明對應 B 的特徵值 (1+\lambda)^{n-1}\neq\rho(B) 的特徵向量不為非負向量,這等價於對應 A 的特徵值 \lambda\neq\rho(A) 的特徵向量不為非負向量。最後證明 \rho(A)>0。假設 \rho(A)=0,則有 A\mathbf{x}=\mathbf{0},其中 \mathbf{x}>\mathbf{0}。但 A\ge 0\mathbf{x}>\mathbf{0} 必定有 A\mathbf{x}>\mathbf{0},即知假設不成立。

 
不可約非負矩陣的 Perron-Frobenius 定理幾乎完全複製了正矩陣的 Perron 定理,除了如 A=\begin{bmatrix} 0&1\\ 1&0 \end{bmatrix} 有特徵值 1,-1,故不滿足 Perron 定理的性質 (4):對於 A 的每一特徵值 \lambda\neq\rho(A)\vert\lambda\vert<\rho(A)。若一不可約非負矩陣滿足性質 (4),我們稱之為原始矩陣 (primitive matrix)。這個主題將留待他日詳細介紹。

This entry was posted in 特殊矩陣, 線性代數專欄 and tagged , , , , , , , . Bookmark the permalink.

4 則回應給 特殊矩陣 (21):非負矩陣

  1. 西北狼 說:

    周老师:非负矩阵是一类特殊的矩阵,因此我想其分解问题一定也很特殊。不知老师能否将这方面的内容和它的应用写博文呢?

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s