確率行列と固有値

Problem

Exercise 1

\(n\) 次非負実行列 \(A = (a_{ij})\) が

\[ \sum_{j=1}^n a_{ij} = 1 \]

を満たすとき，\(A\) を確率行列と呼ぶ． このとき，以下が成立することを示せ

\[ A\pmb f = \pmb f \]

ただし，\(\pmb f = (1, \cdots 1)^T\)， つまり \(\pmb f\) はすべての成分が1であるような \(n\)項列ベクトルであるとする．

Proof

\(A\pmb f\) は \(n\) 項列ベクトルとなるので，その第 \(i\) 項成分を \(b_i\) とすると

\[ \begin{align} b_i &= \sum_{j=1}^n a_{ij}f_j\\ &= \sum_{j=1}^n a_{ij} \quad (\because f_j = 1)\\ &= 1 \end{align} \]

従って，

\[ A\pmb f = (1, \cdots, 1)^T = \pmb f \]

Exercise 2

\(A, B\) が \(n\) 次確率行列であるとき，\(AB\) も確率行列であることを示せ

Proof

\(AB = (c_{ij})\) とするとき，

\[ \begin{align} c_{ij} = \sum_{k=1}^n a_{ik}b_{kj} \end{align} \]

となります．このとき

\[ \begin{align} \sum_{j=1}^n c_{ij} &= \sum_{j=1}^n\sum_{k=1}^n a_{ik}b_{kj}\\ &= \sum_{k=1}^n\sum_{j=1}^n a_{ik}b_{kj}\\ &= \sum_{k=1}^n a_{ik}(\sum_{j=1}^n b_{kj})\\ &= \sum_{k=1}^n a_{ik} \quad (\because \sum_{j=1}^n b_{kj} = 1)\\ &= 1 \end{align} \]

従って，\(A, B\) が \(n\) 次確率行列であるとき，\(AB\) も確率行列である．

Exercise 3

\(A\) が確率行列のとき，複素数 \(\lambda\) に対して \(A\pmb x = \lambda \pmb x\) となるような列ベクトル \(\pmb x \neq \pmb 0\) が存在すれば

\[ |\lambda| \leq 1 \]

となることを示せ．

Proof

\(\pmb x\) の成分のうち絶対値が最大となるような成分を \(|x_p|\) とすると

\[ \begin{align} \lambda x_p = \sum_{i=1}^n a_{pi} x_i \end{align} \]

ここで，両辺について絶対値を取ると

\[ \begin{align} |\lambda x_p | &= |\lambda|\,|x_p|\\ \left|\sum_{i=1}^n a_{pi} x_i\right| & \leq \sum_{i=1}^n a_{pi} |x_i| \quad (\because\text{三角不等式})\\ & \leq \sum_{i=1}^n a_{pi} |x_p|\\ &= |x_p| \quad(\because \sum_{i=1}^n a_{pi} = 1) \end{align} \]

従って，

\[ |\lambda|\,|x_p| \leq |x_p| \Rightarrow |\lambda|\leq 1 \]

Appendix

Theorem 1 : 転置行列の固有値

任意の \(n\) 次正方行列 \(A\) に対して，\(A\) の固有値と \(A^T\) の固有値は等しい

Proof

\(A\) の固有値を \(\lambda\) とすると，\(\lambda\) は次の固有方程式の解と対応します．

\[ |\lambda \pmb I - A| = 0 \]

行列式は転置不変性，つまり

\[ |\lambda \pmb I - A| = |(\lambda \pmb I - A)^T| \]

という性質を持つので

\[ \begin{align} |(\lambda \pmb I - A)^T| &= |(\lambda \pmb I^T - A^T)|\\ &= |(\lambda \pmb I - A^T)|\\ &= 0 \end{align} \]

従って，\(\lambda\) は \(A^T\) の固有方程式の解となることがわかるので，\(A\) の固有値と \(A^T\) の固有値は等しいことがわかる．