8.5.6 定理：原始行列の冪が正行列となる上限
\( A \in M_n \) が非負行列であるとする。もし \( A \) が原始行列であるならば、ある正の整数 \( k \le (n - 1)n^n \) が存在して、次が成り立つ。
A^k \gt 0
証明
\( A \) が既約であるため、\( A \) の有向グラフ \( \Gamma(A) \) において、ノード \( P_1 \) から自身に戻る経路が存在する。その最短経路の長さを \( k_1 \) とすれば、\( k_1 \le n \) である。
このとき、行列 \( A^{k_1} \) の (1,1) 成分は正であり、また \( A^{k_1} \) の任意の冪も同様に (1,1) 成分が正である。\( A \) の原始性および (8.5.5) から、\( A^{k_1} \) は既約である。
したがって、\( \Gamma(A^{k_1}) \) のノード \( P_2 \) から自身に戻る経路が存在する。その最短経路の長さを \( k_2 \le n \) とすると、行列 \( (A^{k_1})^{k_2} = A^{k_1k_2} \) の (1,1) および (2,2) 成分はともに正である。
この手順を主対角線上のすべての要素に対して繰り返すと、行列 \( A^{k_1k_2 \cdots k_n} \)（各 \( k_i \le n \)）が得られる。この行列は既約であり、かつ主対角成分がすべて正である。
補題 8.5.4 より、次が成り立つ。
(A^{k_1k_2\cdots k_n})^{n-1} \gt 0
最後に、次の不等式が成り立つことに注意する。
k_1 k_2 \cdots k_n (n - 1) \le n^n (n - 1)
したがって、ある \( k \le (n - 1)n^n \) に対して \( A^k \gt 0 \) が成り立つ。
ここで、\( A \in M_n \) が非負かつ原始的なとき、\( A^k \gt 0 \) となる最小の \( k \) を \( A \) の原始指数（index of primitivity）といい、\( \gamma(A) \) で表す。
このとき、次が成り立つ。
\gamma(A) \le n^n (n - 1)
また、もし \( A \) の主対角成分がすべて正であるならば、さらに強い条件として \( \gamma(A) \le n - 1 \) が成立する。
次の定理では、上の上限よりもはるかに小さい上界を与える。特に、もし \( A \) の主対角に正の成分が1つだけ存在する場合、その上界は先ほどの値のちょうど2倍になる。また、\( \Gamma(A) \) に長さ \( s \) の閉路が少なくとも1つ存在し、これより短い閉路が存在しない場合、その最短閉路の長さを \( s \) という。
行列解析の総本山
コメント