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

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

性質（循環區塊矩陣）

令 AA 為一方陣且有以下結構

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

若 (x1,x2,…,xp)⊤(\bx_1, \bx_2, \ldots, \bx_p)\trans 為 AA 的特徵向量且其特徵值為 λ\lambda，則 (x1,ζx2,…,ζp−1xp)⊤(\bx_1, \zeta\bx_2, \ldots, \zeta^{p-1}\bx_p)\trans 也會是 AA 的特徵向量，其所對應的特徵值為 ζλ\zeta\lambda，其中 ζ=e2kπpi\zeta = e^{\frac{2k\pi}{p}i} 且 k=0,1,…,p−1k = 0, 1, \ldots, p-1。

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

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

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

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

佩弗定理

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

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

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

lim⁡t→∞x0⊤Mt=π⊤. \lim_{t\to\infty} \bx_0\trans M^t = \pi\trans.

取 x0\bx_0 為 Rn\mathbb{R}^n 標準基底 {e1,…,en}\{\be_1,\ldots,\be_n\} 中的各向量則可以得到 MtM^t 的極限各列均為 π\pi，因此

lim⁡t→∞Mt=1π⊤. \lim_{t\to\infty} M^t = \bone\pi\trans.

想想以下問題：

  1. 已知
    A=[0111110000100001000010000] 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)⊤(2,1,1,1,1)\trans。求 spec⁡(A)\spec(A)。

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

    求 MM 的週期。

  3. 計算各種馬可夫矩陣 MM 的極限 lim⁡t→∞Mt\lim_{t\to\infty}M^t，或說明該極限不收斂。
    1. 可分解：M=[0101]M = \begin{bmatrix} 0 & 1 \\ 0 & 1 \end{bmatrix}。
    2. 不可分解，週期 p>1p > 1：M=[0110]M = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}。
    3. 不可分解，週期 p=1p = 1：M=[0.20.80.80.2]M = \begin{bmatrix} 0.2 & 0.8 \\ 0.8 & 0.2 \end{bmatrix}。