記法
$$
\norm\big{x}\coloneqq \max_i x^i
$$
正行列に対するPerron-Frobeniusの定理
全ての成分が正の正方行列\(\hspace{0.2em}A\hspace{0.2em}\)について、正の固有値\(\hspace{0.2em}\alpha\hspace{0.2em}\)が存在して
- \(A\hspace{0.2em}\)の固有値\(\hspace{0.2em}\beta\hspace{0.2em}\)で\(\hspace{0.2em}\alpha\hspace{0.2em}\)と異なるものは\(\hspace{0.2em}\abs{\beta}<\alpha\hspace{0.2em}\)を満たす。
- 固有値\(\hspace{0.2em}\alpha\hspace{0.2em}\)は縮退せず、固有ベクトルの成分はすべて正。
- \(\alpha\hspace{0.2em}\)以外の固有値に属する固有ベクトルは正ではない成分を持つ。
補題1
\(u_{n+1}=\dfrac{Au_n}{\norm{Au_n}},\quad \norm{u_n}=1\hspace{0.2em}\)なる正ベクトルの列\(\hspace{0.2em}\{u_n\}_{n=0}^\infty\hspace{0.2em}\)が存在する。
証明
\(\hspace{0.2em}u_0=[1,\dots,1]^\mathrm{T}\hspace{0.2em}\)とすると\(\hspace{0.2em}\norm{u_0}=1\hspace{0.2em}\)で正ベクトル。また、\(A\hspace{0.2em}\)が正行列であることから\(\hspace{0.2em}Au_n\hspace{0.2em}\)も正ベクトルであり、\(\norm{u_{n+1}}=\norm\Big{Au_n/\norm{Au_n}}=1\hspace{0.2em}\)より、求めたい\(\hspace{0.2em}\{u_n\}_n\hspace{0.2em}\)の列が得られた。
補題2
\(f(x)\coloneqq \min_j (A^j{}_k x^k/x^j)\hspace{0.2em}\)とすると、\(\alpha\coloneqq \lim_{n\to\infty}f(u_n)\hspace{0.2em}\)が存在して\(\hspace{0.2em}\alpha>0\hspace{0.2em}\)となる。