凱梅尼常數的矩陣跡公式

整理一下目前有的所有性質。當 \(M\) 是一個不可分解的馬可夫矩陣、且 \(\pi\trans = (p_1, \ldots, p_n)\) 為其穩定態時，我們有：

  1. \(H\) 的對角線項均為 \(0\)。
  2. \(\check{H} = H + \Pi^{-1}\)，其中 \(\Pi\) 是以 \(\pi\trans\) 為對角線各項的對角矩陣。
  3. \(MH + J = \check{H} = H + \Pi^{-1}\)。
  4. \(H\pi = \hat{K}\bone\)。

然而我們目前唯一可以求出 \(\hat{K}\) 的辦法就是先求出 \(H\)，在這邊我們介紹一個更直接的計算方式。

我們同樣將第 \(3\) 點改寫為

\[ (I - M)H = J - \Pi^{-1}. \]

它之所以難解的原因在於 \(I - M\) 並不可逆，所以文獻中曾經使用群反矩陣（group inverse）或是廣義反矩陣（Moore–Penrose pseudoinverse）來處理它，但這裡我們想辦法將 \(I - M\) 先調整成一個可逆矩陣，也就是想辦法把 \(M\) 之中 \(1\) 這個特徵值處理掉。

令 \(U = \vspan\{\bone\}\) 且 \(W = \vspan\{\pi\}^\perp\)。由於 \(\dim(W) = n-1\) 且 \(\bone\notin W\)，我們知道 \(U\oplus W = \mathbb{R}^n\)，這裡 \(\oplus\) 是值和的意思，表示任何向量 \(\by\in\mathbb{R}^n\) 都可以唯一表示成 \(\by = \bu + \bw\)，其中 \(\bu\in U\) 且 \(\bw\in W\)。注意到的是 \(U\) 和 \(W\) 都是 \(M\) 的不變子空間，所以我們可以找到一個矩陣 \(Q\) 使得

\[ Q^{-1}MQ = \begin{bmatrix} 1 & \bzero\trans \\ \bzero & M' \end{bmatrix}, \]

這裡 \(Q\) 的第一行可以取 \(\bone\)，而第二行以後分別放入 \(W\) 的一組基底。注意到 \(Q^{-1}\) 的第一列是 \(M\) 的左特徵向量，對應到特徵值 \(1\)，而且它和 \(Q\) 的第一行內積是 \(1\)，所以 \(Q^{-1}\) 的第一列一定是 \(\pi\trans\)。也就是說，我們知道

\[ Q\begin{bmatrix} 0 & \bzero\trans \\ \bzero & M' \end{bmatrix}Q^{-1} = M - \bone\pi\trans \]

並沒有 \(1\) 這個特徵值（因為佩弗定理告訴我們 \(1\) 的重數只有一次）。

利用這個特性我們可以回頭解先前的等式，首先將兩側都加上 \(\bone\pi\trans H\)：

\[ (I - M + \bone\pi\trans)H = J - \Pi^{-1} + \bone\pi\trans H. \]

由於 \(I - M + \bone\pi\trans\) 可逆，令 \(Z = (I - M + \bone\pi\trans)^{-1}\)。兩側同時左乘 \(Z\) 可得

\[ H = Z(J - \Pi^{-1}) + Z\bone\pi\trans H = J - Z\Pi^{-1} + \bone\pi\trans H, \]

其中第二個等式是因為 \((I - M + \bone\pi\trans)\bone = \bone\) 且 \(Z\bone = \bone\)。這告訴我們 \(H\) 是由 \(J - Z\Pi^{-1}\) 每行加上某個 \(\bone\) 的倍數得來。由於 \(H\) 的對角線項均為 \(0\)，我們可以令 \(\bd\) 為 \(J - Z\Pi^{-1}\) 對角線項所成的向量，如此我們可以得到

\[ H = J - Z\Pi^{-1} - \bone\bd\trans. \]

如果令 \(z_{i,j}\) 為 \(Z\) 的各項，則

\[ h_{i,j} = 1 - \frac{z_{i,j}}{p_j} - (1 - \frac{z_{j,j}}{p_j}) = \frac{z_{j,j} - z_{i,j}}{p_j}. \]

最後，直接計算可得

\[ \hat{K} = \sum_{j = 1}^n h_{i,j}p_j = \sum_{j = 1}^n (z_{j,j} - z_{i,j}) = \tr(Z) - 1, \]

這裡第二個等式是因為 \(Z\bone = \bone\) 告訴我們 \(Z\) 的每列和均為 \(1\)，而這個計算再次告訴我們這個數值與 \(i\) 的選取無關。由於 \(Z\) 的特徵值為 \(\{1\} \cup \{1 - \lambda: \lambda\in \spec(M),\ \lambda\neq 1\}\)，我們也可以得到

\[ \hat{K} = \tr(Z) - 1 = \sum_{\substack{\lambda\in\spec(M) \\ \lambda\neq 1}}\frac{1}{1 - \lambda}. \]

以下補充一些類似的公式：

  1. 令 \(A = I - M\) 而 \(A^\sharp\) 為其群反矩陣，則
    \[ H = A^\sharp (J - \Pi^{-1}) - \bone\bd\trans = -A^\sharp\Pi^{-1} + JA^\sharp_d \Pi^{-1}, \]

    其中 \(\bd\) 為 \(A^\sharp (J - \Pi^{-1})\) 的對角線項所成的向量，而 \(A^\sharp_d\) 為 \(A^\sharp\) 的對角項項所成的對角矩陣。

  2. 令 \(A = I - M\) 而 \(A^\dagger\) 為其廣義反矩陣，則
    \[ H = A^\dagger (J - \Pi^{-1}) - \bone\bd\trans, \]

    其中 \(\bd\) 為 \(A^\dagger (J - \Pi^{-1})\)。

實際上透過 \(Z\) 的手法來解方程式本質上和 \(A^\sharp\) 的概念一樣，只是躲過群反矩陣的操作。反之，\(A^\dagger\) 的公式並沒有帶來太大的好處，而且 \(A^\dagger\) 的特徵值和 \(A\) 的特徵值沒有直接的關係。有另一個辦法是先將 \(M\) 標準化為 \(\Pi M\Pi^{-1}\)，並對其使用廣義反矩陣的操作，但這部份就留到未來聊到拉普拉斯矩陣時再談了。

想想以下問題：

  1. 驗證 \(U\) 和 \(W\) 都是 \(M\) 的不變子空間。
  2. 想想 \(Q^{-1}ZQ\) 是什麼？
  3. 說明 \(A^\sharp = Q\begin{bmatrix} 0 & \bzero\trans \\ \bzero & (I - M')^{-1} \end{bmatrix}\) 滿足 \(AA^\sharp A = A\)、\(A^\sharp AA^\sharp = A^\sharp\)、及 \(AA^\sharp = A^\sharp A\)。實際上這也是群反矩陣的定義。