Perron–Frobeniusの定理

行列の積の定義から
$$ (T^k)_{ij}=\sum_{i_1,\dots,i_{k-1}}t_{ii_1}t_{i_1i_2}\cdots t_{i_{k-1}j} $$
であり、各項は $0$ 以上である。よって $(T^k)_{ij}>0$ は、すべての因子が正となる列 $i,i_1,\dots,i_{k-1},j$、すなわち長さ $k$ の有向歩道があることと同値である。
後半：既約なら強連結であることは前半から明らかである。逆に強連結で $n\ge2$ なら、$i\ne j$ については前半から $(T^k)_{ij}>0$ となる $k$ がある。$i$ から別の頂点 $j$ へ行き、$j$ から $i$ へ戻る有向歩道をつなげば $i$ から $i$ への有向歩道が得られるので、$(T^k)_{ii}>0$ となる $k\ge1$ もある。$\square$

$I$ と $T$ は可換なので $(I+T)^{n-1}=\sum_{k=0}^{n-1}\binom{n-1}{k}T^k$ であり、各項は $0$ 以上である。対角成分は $k=0$ の項から $1$ 以上である。$i\neq j$ とすると、既約性と lem-pf-walks により $i$ から $j$ への有向歩道がある。そのうち最短のものは同じ頂点を 2 度通らない（通れば間を省いてより短くできる）ので、長さ $k$ は $n-1$ 以下で、$(T^k)_{ij}>0$ である。よって $(I+T)^{n-1}$ の $(i,j)$ 成分は正である。
後半：第 $i$ 行が零ベクトルなら、どの $k\ge1$ でも $(T^k)_{ij}=\sum_lt_{il}(T^{k-1})_{lj}=0$ となり、既約性に反する。$\square$

段 1（$P$ で $\gamma$ は増える）．$x\in B$ とする。$P>0$ なので $Px>0$ である。$\gamma(x)x\le Tx$ の両辺に $P\ge0$ を掛けると $\gamma(x)Px\le PTx=T(Px)$ なので $\gamma(Px)\ge\gamma(x)$ である。さらに $Tx\ne\gamma(x)x$ なら、$w:=Tx-\gamma(x)x\in B$ で $Pw>0$、すなわち $T(Px)-\gamma(x)Px>0$ であり、$Px>0$ で割ると $(T(Px))_i/(Px)_i>\gamma(x)$ がすべての $i$ で成り立つ。有限個の $i$ の最小値をとって $\gamma(Px)>\gamma(x)$ である。
段 2（最大値の存在）．$C:=\{x\ge0\mid x_1+\dots+x_n=1\}$ はコンパクトなので、その連続像 $P[C]$ もコンパクトで、段 1 により $P[C]$ の元はすべて正のベクトルである。正のベクトルの上では $\gamma(y)=\min_i(Ty)_i/y_i$ は連続関数の最小値なので連続であり、$\gamma$ は $P[C]$ の上で最大値をとる。その点を $x_0=Pz_0$（$z_0\in C$）とし、$r_0:=\gamma(x_0)$ とおく。任意の $x\in B$ について、$s:=x_1+\dots+x_n>0$ とすると $x/s\in C$ なので、段 1 により $\gamma(x)=\gamma(x/s)\le\gamma(P(x/s))\le r_0$ である。よって $r_0=\max_B\gamma$ である。
段 3（最大点は固有ベクトル）．$Tx_0\ne r_0x_0$ とすると、段 1 により $\gamma(Px_0)>r_0$ となり、$Px_0\in B$ なので段 2 に反する。よって $Tx_0=r_0x_0$ で、$x_0=Pz_0>0$ である。lem-pf-positive-power により $T$ の各行は零でないので $(Tx_0)_i>0$ であり、$r_0>0$ である。
段 4（$r_0$ は最大の絶対値）．$\lambda$ を $T$ の固有値、$x\in\mathbb C^n$ をその固有ベクトルとする。三角不等式により $|\lambda||x_i|=|\sum_jt_{ij}x_j|\le\sum_jt_{ij}|x_j|$、すなわち $|\lambda||x|\le T|x|$ であり、$|x|\in B$ なので $|\lambda|\le\gamma(|x|)\le r_0$ である。$r_0$ 自身が固有値なので $r_0=\rho(T)=r$ である。これで 1 が示された。
段 5（$Tz\ge rz$ なら固有ベクトル）．$z\in B$、$Tz\ge rz$ とする。$\gamma(z)\ge r$ と段 2 から $\gamma(z)=r$ である。$Tz\ne rz$ なら段 1 により $\gamma(Pz)>r$ となって段 2 に反するので、$Tz=rz$ である。このとき $(I+T)z=(1+r)z$ から $Pz=(1+r)^{n-1}z$ で、$Pz>0$ なので $z>0$ である。$\square$

段 6（固有空間は 1 次元）．$x\in\mathbb R^n$ を $Tx=rx$ をみたす $0$ でないベクトルとする。必要なら $-x$ に替えて、$x$ は正の成分をもつとしてよい。$c:=\min_{i:\,x_i>0}x_{0,i}/x_i>0$（$x_{0,i}$ は $x_0$ の第 $i$ 成分）とおき、$y:=x_0-cx$ とする。$x_i>0$ の成分では $c$ の定め方から $y_i\ge0$、$x_i\le0$ の成分では $y_i\ge x_{0,i}>0$ であり、最小値をとる $i$ では $y_i=0$ である。$Ty=ry$ なので、$y\ne0$ なら $y\in B$、$Ty\ge ry$ となり、段 5 により $y>0$ となって $y_i=0$ に反する。よって $y=0$、すなわち $x=x_0/c$ である。複素ベクトル $x=u+\sqrt{-1}\,v$（$u,v$ 実）が $Tx=rx$ をみたせば、$T$ と $r$ は実なので $Tu=ru$、$Tv=rv$ であり、$u,v$ はともに $x_0$ の実数倍である。よって固有空間は $x_0$ で張られる。
段 7（左固有ベクトルと 3・4）．転置 $T^{\mathsf T}$ も非負で、$(T^{\mathsf T})^k=(T^k)^{\mathsf T}$ なので既約である。固有多項式は $T$ と同じなのでスペクトル半径も $r$ である。段 1〜5 を $T^{\mathsf T}$ に当てはめると、$T^{\mathsf T}y_0=ry_0$、すなわち $y_0^{\mathsf T}T=ry_0^{\mathsf T}$ となる $y_0>0$ が得られる。これが 4 である。次に $x\in B$、$Tx=\lambda x$ とすると
$$ r\,y_0^{\mathsf T}x=y_0^{\mathsf T}Tx=\lambda\,y_0^{\mathsf T}x $$
であり、$y_0>0$、$x\in B$ から $y_0^{\mathsf T}x>0$ なので $\lambda=r$ である。prf-pf-existence の段 5 により $x>0$ で、3 が示された。
段 8（単根であること）．$N:=T-rI$ とし、固有値 $r$ の代数的重複度を $m$ とする。$m\ge2$ と仮定する。Jordan標準形 の記事の補題「広義固有空間への分解」により、広義固有空間 $\ker N^m$（複素ベクトル空間として）は $m$ 次元で、段 6 により $\ker N$ は 1 次元なので、$\ker N\subsetneq\ker N^m$ である。もし $\ker N^2=\ker N$ なら、$v\in\ker N^{k+1}$（$k\ge1$）について $N^{k-1}v\in\ker N^2=\ker N$ から $v\in\ker N^k$ となり、帰納的に $\ker N^m=\ker N$ となって矛盾する。よって $w\in\ker N^2\setminus\ker N$ がある。$Nw\ne0$、$N(Nw)=0$ なので段 6 により $Nw=cx_0$（$c\ne0$）である。左から $y_0^{\mathsf T}$ を掛けると、$y_0^{\mathsf T}N=y_0^{\mathsf T}T-ry_0^{\mathsf T}=0$ なので
$$ 0=y_0^{\mathsf T}Nw=c\,y_0^{\mathsf T}x_0 $$
となるが、$y_0>0$、$x_0>0$ から右辺は $0$ でない。これは矛盾なので $m=1$ であり、2 が示された。
段 9（最大最小の特徴づけ）．最初の等号は段 2・3 そのものである（$\gamma(x)$ が内側の最小値で、最大値は $x_0$ でとる）。$x>0$ について $\delta(x):=\max_i(Tx)_i/x_i$ とおくと $Tx\le\delta(x)x$ であり、左から $y_0^{\mathsf T}\ge0$ を掛けて $r\,y_0^{\mathsf T}x=y_0^{\mathsf T}Tx\le\delta(x)\,y_0^{\mathsf T}x$、よって $r\le\delta(x)$ である。$\delta(x_0)=r$ なので、2 つ目の等号も成り立つ。$\square$

原始行列は既約なので thm-pf-main が使える。$T^k>0$ とし、$Tx=\lambda x$、$x\ne0$、$|\lambda|=r$ とする。prf-pf-existence の段 4 と同じく $|\lambda||x|\le T|x|$、すなわち $T|x|\ge r|x|$ なので、同じ証明の段 5 により $T|x|=r|x|$ かつ $|x|>0$ である。よって $T^k|x|=r^k|x|$ であり、一方 $T^kx=\lambda^kx$ から
$$ \Bigl|\sum_j(T^k)_{ij}x_j\Bigr|=|\lambda|^k|x_i|=r^k|x_i|=\sum_j(T^k)_{ij}|x_j| $$
がすべての $i$ で成り立つ。複素数の三角不等式で等号が成り立ち、係数 $(T^k)_{ij}$ はすべて正なので、$x_1,\dots,x_n$（どれも $0$ でない）の偏角はすべて等しい。つまり $x=e^{\sqrt{-1}\theta}|x|$ と書ける。すると $\lambda x=Tx=e^{\sqrt{-1}\theta}T|x|=e^{\sqrt{-1}\theta}r|x|=rx$ で、$\lambda=r$ である。$\square$

$r=\rho(T)$ とし、$Ss=\mu s$、$s\ne0$ とする。$|\mu||s|=|Ss|\le|S||s|\le T|s|$ なので $|\mu|\le\gamma(|s|)\le r$ である（prf-pf-existence の段 2）。$0\le S\le T$ かつ $|\mu|=r$ なら $T|s|\ge r|s|$ となり、同じ証明の段 5 により $T|s|=r|s|$ かつ $|s|>0$ である。すると $r|s|=|\mu||s|\le S|s|\le T|s|=r|s|$ から $(T-S)|s|=0$ であり、$T-S\ge0$ と $|s|>0$ から $T-S=0$ である。$\square$