8.5.7 定理：原始的非負行列に対する指数の上限
定理 8.5.7．\( A \in M_n \) が非負かつ原始的な行列であり、\( \Gamma(A) \) における最短閉路の長さが \( s \) であるとする。このとき、
\gamma(A) \le n + s(n - 2)
すなわち、
A^{n + s(n - 2)} \gt 0
証明
\( A \) が既約であるため、\( \Gamma(A) \) のすべての節点はある閉路に含まれている。また、最短閉路の長さは高々 \( n \) である。最短閉路の異なる節点を \( P_1, P_2, \ldots, P_s \) としてよい。ここで、次の等式に注目する：
n + s(n - 2) = n - s + s(n - 1)
これより、
A^{n - s + s(n - 1)} = A^{n - s}(A^s)^{n - 1}
とおく。ここで、次のように分割する：
A^{n - s} =
\begin{bmatrix}
X_{11} & X_{12} \\
X_{21} & X_{22}
\end{bmatrix}
ただし \( X_{11} \in M_s \)、\( X_{22} \in M_{n-s} \) である。節点 \( P_1, \ldots, P_s \) は \( \Gamma(A) \) において閉路を構成しているため、任意の正の整数 \( m \) と \( i \in \{1, \ldots, s\} \) に対して、長さ \( m \) の有向路が \( P_i \) から \( P_j \)（\( j \in \{1, \ldots, s\} \)）に存在する。特に \( m = n - s \) とすると、\( X_{11} \) の各行には少なくとも1つの正の要素が存在する。
一方、\( i \in \{s + 1, \ldots, n\} \) に対して、節点 \( P_i \)（閉路外）から閉路内のある節点への有向路が存在し、その長さは \( r \le n - s \) である。もし \( r \lt n - s \) ならば、閉路をさらに \( n - s - r \) ステップ進むことで、長さちょうど \( n - s \) の有向路を構成できる。したがって、\( X_{21} \) の各行にも少なくとも1つの非零要素が存在する。
次に、次のように分割する：
(A^s)^{n - 1} =
\begin{bmatrix}
Y_{11} & Y_{12} \\
Y_{21} & Y_{22}
\end{bmatrix}
ただし \( Y_{11} \in M_s \)、\( Y_{22} \in M_{n-s} \) である。節点 \( P_1, \ldots, P_s \) は \( \Gamma(A) \) において閉路を構成しているため、\( \Gamma(A^s) \) の各節点 \( P_1, \ldots, P_s \) に自己ループが存在する。
また \( A \) は原始行列であるため、\( A^s \) も原始であり、したがって既約である。ゆえに任意の \( i, j \in \{1, \ldots, n\} \) に対して、長さ高々 \( n - 1 \) の有向路が \( \Gamma(A^s) \) において \( P_i \) から \( P_j \) へ存在する。さらに \( P_i \) 上の自己ループを十分な回数たどることで、ちょうど長さ \( n - 1 \) の有向路を構成できる。したがって、\( Y_{11} \gt 0 \) かつ \( Y_{12} \gt 0 \) である。
以上を踏まえて、次を計算する：
A^{n - s}(A^s)^{n - 1}
=
\begin{bmatrix}
X_{11} & X_{12} \\
X_{21} & X_{22}
\end{bmatrix}
\begin{bmatrix}
Y_{11} & Y_{12} \\
Y_{21} & Y_{22}
\end{bmatrix}
\ge
\begin{bmatrix}
X_{11}Y_{11} & X_{11}Y_{12} \\
X_{21}Y_{11} & X_{21}Y_{12}
\end{bmatrix}
式 (8.1.14) を用いれば、\( A^{n - s}(A^s)^{n - 1} \gt 0 \) であることがわかる。∎
定理 (8.5.7) の結果として、H. ヴィーラント（H. Wielandt）による著名な結果が得られる。これは原始性指数の鋭い上界を与えるものである。
行列解析の総本山
コメント