8.5.9 定理（Holladay–Varga の結果）：非負既約行列の原始性と対角要素の影響
次の定理は、非負かつ既約な行列の中で、主対角要素に正の成分がいくつか含まれる場合に、その行列が原始行列となるための指数（index of primitivity）の上限を与えるものである。
定理 8.5.9
\( A \in M_n \) を非負かつ既約な行列とし、その主対角要素のうち \( d \) 個が正であるとする。ただし \( 1 \le d \le n \) とする。このとき次が成り立つ。
A^{2n - d - 1} \gt 0
すなわち、原始指数は次を満たす。
\gamma(A) \le 2n - d - 1
証明
仮定より、\( A \) は原始行列であり、その有向グラフ \( \Gamma(A) \) には長さ 1 の閉路（自己ループ）が \( d \) 個存在するものとする。これらのループをもつノードを \( P_1, P_2, \dots, P_d \) とする。
次を考える。
A^{2n - d - 1} = A^{n - d} \, A^{n - 1}
ここで、
A^{n - d} =
\begin{bmatrix}
X_{11} & X_{12} \\
X_{21} & X_{22}
\end{bmatrix},
\quad
A^{n - 1} =
\begin{bmatrix}
Y_{11} & Y_{12} \\
Y_{21} & Y_{22}
\end{bmatrix}
とブロック分割する。ただし、\( X_{11}, Y_{11} \in M_d \)、\( X_{22}, Y_{22} \in M_{n-d} \) である。
定理 (8.5.7) の証明と同様にして、ブロック \( X_{11} \) と \( X_{21} \) の各行には少なくとも1つの非零成分が含まれること、また \( Y_{11} \) と \( Y_{12} \) は正であることが示される。したがって積 \( A^{n - d} A^{n - 1} \) は正である。ゆえに定理が示された。
演習
次の行列を考える。
A =
\begin{bmatrix}
0 & 1 \\
1 & 1
\end{bmatrix}
(1) \( A \) が原始行列であることを示せ。
(2) その固有値を求めよ。
(3) 式 (8.5.7) および (8.5.9) により与えられる \( \gamma(A) \) の上限を求めよ。
(4) 実際の \( \gamma(A) \) の値を求めよ。
原始性の確認手順について
非負行列が原始であることを確認するには、まずそれが既約であるかを調べ、さらにWielandtの条件 (8.5.8) を満たすかどうかを確認すればよい。
実際の応用で現れる行列は、しばしば特定の構造をもつため、対応する有向グラフが強連結であるかどうかを容易に判定できる。また、非負行列が既約であり、主対角成分の一部でも正であれば、それは必ず原始である。
しかし、主対角要素がすべて 0 の大規模な行列で特別な構造をもたない場合には、既約性や原始性を確認するために、(8.4.1) や (8.5.8) を用いる必要がある。このような場合、実用的な方法として、行列を繰り返し二乗し、得られるべき臨界指数（既約性には \( n - 1 \)、原始性には \( n^2 - 2n + 2 \)）を超えるまで計算を進めるとよい。
例えば \( n = 10 \) の場合、既約性を確認するには、次の行列を順に計算すれば十分である。
(I + A)^2, \; (I + A)^4, \; (I + A)^8, \; (I + A)^{16}
これにより、(8.4.1) を直接適用する場合に必要な8回の行列積の代わりに、4回の積で済む。同様に、原始性を確認するには次を順に計算すればよい。
A^2, \; A^4, \; A^8, \; A^{16}, \; A^{32}, \; A^{64}, \; A^{128}
これにより \( n = 10 \) の場合、81回の積の代わりに7回の行列積で原始性を確認できる。これらの考察では、(8.5.P3) の結果を暗黙的に利用している。
行列解析の総本山
コメント