佩弗定理與馬可夫矩陣的特徵值結構
佩弗定理與馬可夫矩陣的特徵值結構
佩弗定理（Perron–Frobenius theorem）是由兩位德國數學家 Oskar Perron 及 Georg Frobenius 分別於 1907 及 1912 年獨立提出，它對每一項元素都非負的矩陣的特徵值、特徵向量有一系列的描述。以下我們挑幾個較常見的性質介紹，完整的敘述及證明可以參考 Spectra of Graph 一書。
首先，接下來我們要考慮的矩陣每一項都非負，我們簡稱其為 非負矩陣。另一方面，如果一個方陣 \(M\) 可以找到一個排列矩陣 \(P\) 使得
中的 \(A\) 和 \(B\) 都是方陣，則 \(M\) 被稱為 可分解的（reducible），反之則被稱為 不可分解的（irreducible）。如果矩陣可分解，則 \(\spec(M) = \spec(A)\cup\spec(B)\)，所以只是想知道特徵值的話，我們可以專注在更小塊的矩陣上就好。大家可以試試看
分別是可分解和不可分解的。先前提到的賦權有向圖為判斷一個馬可夫矩陣是否可分解提供很有效的工具。當 \(\Gamma\) 為一馬可夫矩陣 \(M\) 的賦權有向圖時，則以下兩敘述等價：
- \(M\) 不可分解。
- \(\Gamma\) 為強連通圖。
這裡一個有向圖為 強連通（strongly connected） 指的是圖上任兩點 \(u\) 和 \(v\) 都有一條有向路徑從 \(u\) 走到 \(v\)、也有一條一條有向路徑從 \(v\) 走到 \(u\)。
佩弗定理
令 \(M\) 為一非負方陣，則 \(M\) 有以下性質：
- 有一個實數特徵值 \(\rho\)，且其它特徵值 \(\lambda\) 都滿足 \(\lvert\lambda\rvert \leq \rho\)。
- 若 \(M\) 不可分解，則特徵值 \(\rho\) 對應到的特徵向量有一個是各項全正的。
- 如果一特徵向量是各項全正的，則它對應到的特徵值必為 \(\rho\)。
- 若 \(M\) 不可分解，則 \(\rho\) 的代數重數及幾何重數都是 \(1\)。
由於 \(\rho\) 大過其它特徵值（可能是複數）的長度，所以 \(\rho\) 被稱為 \(M\) 的 譜半徑（spectral radius）。要注意到的是一般實數矩陣不一定會有實數特徵值，佩弗定理令人佩服的地方在於它只需要知道 \(M\) 是非負方陣就好，就可以得到一系列性質。
一個馬可夫矩陣 \(M\) 顯然是非負的。我們知道 \(M\bone = 1\cdot\bone\)，所以 \(\bone\) 是一個各向全正的特徵向量，也因此 \(1\) 是 \(M\) 的譜半徑。由於 \(M\trans\) 也是非負矩陣且 \(\spec(M\trans) = \spec(M)\)，因此 \(1\) 也是 \(M\trans\) 的譜半徑，如此一來我們知道 \(M\trans\) 有一個各項全正的特徵向量 \(\pi\) 對應到特徵值 \(1\)，所以 \(\pi\trans M = \pi\trans\) 且 \(\pi\trans\) 是 \(M\) 的穩定態。總結來說，佩弗定理告訴我們任何馬可夫矩陣都會有至少一個穩定態，而當 \(M\) 不可分解時，這樣的穩定態是唯一的。
想想以下問題：
- 強連通和矩陣可否分解有什麼關係？
- 把 \(M_1\) 對應的賦權有向圖畫出來，如果兩點之間彼此有路徑往返則將兩點歸為一類，算算會得到幾類。並說明如何用這些類來幫 \(M_1\) 分解。
- 把 \(M_2\) 對應的賦權有向圖畫出來，說明它是強連通的。
- 譜半徑和其它特徵值在複數平面上的圖像為何？
- 計算
\[ M = \begin{bmatrix} 0.2 & 0.8 & 0 \\ 0.4 & 0.2 & 0.4 \\ 0 & 0.8 & 0.2 \\ \end{bmatrix} \]
的所有特徵值，並將其畫在複數平面上，最後以原點為圓心、譜半徑為半徑畫一個圓。
- 計算
\[ M = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ \end{bmatrix} \]
的所有特徵值，並將其畫在複數平面上，最後以原點為圓心、譜半徑為半徑畫一個圓。
- 計算