邊界特徵值與馬可夫矩陣的極限

邊界特徵值與馬可夫矩陣的極限

佩弗定理說明了非負矩陣的特徵值都在譜半徑畫出來的圖內，而實際上完整的佩弗定理對圓周邊界上的特徵值也有清楚的刻畫。在敘述這個部份的定理之前，我們先來看一類特殊結構矩陣的性質。

性質（循環區塊矩陣）

令 \(A\) 為一方陣且有以下結構

\[ A = \begin{bmatrix} O_{n_1} & B_1 & ~ & ~ \\ ~ & O_{n_2} & \ddots & ~ \\ ~ & ~ & \ddots & B_{p-1} \\ B_p & ~ & ~ & O_{n_p} \end{bmatrix}. \]

若 \((\bx_1, \bx_2, \ldots, \bx_p)\trans\) 為 \(A\) 的特徵向量且其特徵值為 \(\lambda\)，則 \((\bx_1, \zeta\bx_2, \ldots, \zeta^{p-1}\bx_p)\trans\) 也會是 \(A\) 的特徵向量，其所對應的特徵值為 \(\zeta\lambda\)，其中 \(\zeta = e^{\frac{2k\pi}{p}i}\) 且 \(k = 0, 1, \ldots, p-1\)。

關於這個性質一個簡單的例子，可以令

\[ A = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}. \]

由於全一向量 \(\bone\) 是 \(A\) 的特徵向量且特徵值為 \(1\)，所以 \((1,\omega, \omega^2)\trans\) 和 \((1, \omega^2, \omega^4)\trans\) 也都是 \(A\) 的特徵向量且特徵值分別為 \(\omega\) 和 \(\omega^2\)，其中 \(\omega = e^{\frac{2\pi}{3}i}\)。由於三個特徵值都不同，所以這樣就找到了這個矩陣的一組特徵基底。

回到馬可夫矩陣，如果一個馬可夫矩陣 \(M\) 可以寫為是週期為 \(p\) 的循環區塊矩陣，則我們知道其譜半徑 \(\rho\) 及 \(\zeta\rho, \ldots, \zeta^{p-1}\rho\) 都是圓周上的邊界特徵值，其中 \(\zeta = e^{\frac{2\pi}{p}i}\)。我們將最大可能的 \(p\) 定義為一個矩陣 \(M\) 的 週期（period），則佩弗定理還告訴我們上述找到的 \(p\) 個特徵值，就是圓周上所有的特徵值了。

佩弗定理

若 \(M\) 為一非負不可分解的矩陣、且其週期為 \(p\)，則譜半徑 \(\rho\) 畫出來的圓周上恰有 \(p\) 個，也就是 \(\rho, \zeta\rho, \ldots, \zeta^{p-1}\rho\)，其中 \(\zeta = e^{\frac{2\pi}{p}i}\)。

附帶一提，在判斷一個矩陣的週期時，其對應的賦權有向圖 \(\Gamma\) 再次扮演一個重要的角色。在 \(\Gamma\) 上我們可以考慮所有的有向圈，如果它們長度的最大公因數是 \(p\)，則我們知道從任一點出發要走回自己的步數一定是 \(p\) 的倍數，這樣就可以把圖的點分為 \(p\) 個等價類：如果 \(u\) 到 \(v\) 的步數為 \(p\) 的倍數，則這兩點歸為同一類。如此一來第一類走一步會到第二類、依此類推，而第 \(p\) 類再走一步則會回到第一類。反應在矩陣上就是該矩陣可以寫為週期為 \(p\) 的循環區塊矩陣，因此一個矩陣的週期剛好就是 \(\Gamma\) 所有有向圈長度的最大公因數。

對馬可夫矩陣來說，邊界特徵值特別重要，因為特徵值的長度為 \(1\)，而其它內部特徵值在乘了很多次以後都會趨近於 \(0\)。直覺來說，一個馬可夫矩陣 \(M\) 乘了很多次以後，留下來的只剩圓周上的特徵值。實際上，如果 \(M\) 的週期為 \(p\) 且 \(p > 1\)，則 \(\be_1\trans M^t\) 的非零項會在區塊上循環，導致 \(M^t\) 在 \(t\) 趨近到無窮大時不收斂，這裡 \(\be_1 = (1,0,\ldots,0)\trans\)。反之，當一個不可分解的 \(M\) 的週期為 \(1\) 時，則任意初始態在多次迭代以後都會趨近到其唯一的穩定態 \(\pi\trans\)。也就是對於所有初始態 \(\bx_0\) 都有

\[ \lim_{t\to\infty} \bx_0\trans M^t = \pi\trans. \]

取 \(\bx_0\) 為 \(\mathbb{R}^n\) 標準基底 \(\{\be_1,\ldots,\be_n\}\) 中的各向量則可以得到 \(M^t\) 的極限各列均為 \(\pi\)，因此

\[ \lim_{t\to\infty} M^t = \bone\pi\trans. \]

想想以下問題：

1. 已知
   \[ A = \begin{bmatrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ \end{bmatrix} \]

   有一特徵向量為 \((2,1,1,1,1)\trans\)。求 \(\spec(A)\)。

2. 令
   \[ M = \begin{bmatrix} 0 & 0.5 & 0 & 0.5 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}. \]

   求 \(M\) 的週期。

3. 計算各種馬可夫矩陣 \(M\) 的極限 \(\lim_{t\to\infty}M^t\)，或說明該極限不收斂。
   1. 可分解：\(M = \begin{bmatrix} 0 & 1 \\ 0 & 1 \end{bmatrix}\)。
   2. 不可分解，週期 \(p > 1\)：\(M = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\)。
   3. 不可分解，週期 \(p = 1\)：\(M = \begin{bmatrix} 0.2 & 0.8 \\ 0.8 & 0.2 \end{bmatrix}\)。