8.5.3 原始行列と閉路長の最大公約数による特徴づけ
定理 8.5.3
\( A \in M_n \) を既約かつ非負の行列とし、その有向グラフを \( \mathcal{G}(A) \) とする。ノードを \( P_1, P_2, \ldots, P_n \) とし、各ノード \( P_i \) に対して、ノード \( P_i \) から出発し、同じノード \( P_i \) に戻るすべての有向経路の長さの集合を
L_i = \{ k^{(i)}_1, k^{(i)}_2, \ldots \}
とする。ここで、\( g_i \) を集合 \( L_i \) に含まれるすべての経路長の最大公約数とする。このとき、次が成り立つ。
A \text{ は原始行列である} \quad \Longleftrightarrow \quad g_1 = g_2 = \cdots = g_n = 1
証明
\( A \) の既約性から、どの \( L_i \) も空集合ではない。すなわち、任意の \( i \) と \( j \ne i \) に対して、\( \mathcal{G}(A) \) には \( P_i \) から \( P_j \) への経路と \( P_j \) から \( P_i \) への経路が存在する。
もし \( A \) が原始行列であれば、定理 (8.5.2) により \( m \ge 1 \) が存在して \( A^m \gt 0 \) が成り立つ。したがって、すべての \( k \ge m \) に対して \( A^k \gt 0 \) である。このとき、任意の整数 \( p \ge 1 \) に対して \( m + p \in L_i \) が成り立つので、すべての \( i = 1, \ldots, n \) について \( g_i = 1 \) となる。
逆に、\( A = [a_{ij}] \) が原始でないとし、最大絶対値をもつ固有値がちょうど \( k \gt 1 \) 個あると仮定する。系 (8.4.8) により、\( m \) が \( k \) の整数倍でないとき、\( A^m \) の主対角要素はすべて 0 である。したがって、そのような \( m \) では、いかなるノードについても自分自身に戻る有向経路が存在しない。ゆえに
L_i \subset \{ k, 2k, 3k, \ldots \}
が成り立ち、したがって各 \( i = 1, \ldots, n \) に対して \( g_i \ge k \gt 1 \) となる。
ロマノフスキーの定理
ロマノフスキーの定理によると、もし \( A \in M_n \) が既約かつ非負であるならば、
g_1 = g_2 = \cdots = g_n = k
が成り立ち、この \( k \) は \( A \) の最大絶対値をもつ固有値の個数に等しい。
この結果は、特に、主対角成分がすべて正である既約非負行列は原始行列であることを示している点で有用である。
行列解析の総本山
コメント