[行列解析6.2.16]定理：有向経路と行列のべき乗の関係

6.2.16
行列解析の総本山

6.2.16

定理6.2.16．行列 \(A \in M_n\) と、\(\mathcal{G}(A)\) のノード \(P_i\) および \(P_j\) が与えられたとする。次の3条件は同値である。

(a) \(\mathcal{G}(A)\) において、\(P_i\) から \(P_j\) への長さ \(m\) の有向経路が存在する。

(b) \(|A|^m\) の \(i,j\) 成分が非ゼロである。

証明．帰納法により示す。\(m = 1\) の場合、主張は自明である。\(m = 2\) の場合、次を計算する。

(|A|^2)_{ij} = \sum_{k=1}^{n} |A|_{ik} |A|_{kj} = \sum_{k=1}^{n} |a_{ik}| |a_{kj}|

したがって、\((|A|^2)_{ij} \neq 0\) であることは、少なくとも1つの \(k\) に対して \(a_{ik}\) と \(a_{kj}\) が両方とも非ゼロである場合に限る。これは \(\mathcal{G}(A)\) において \(P_i\) から \(P_j\) への長さ2の経路が存在する場合に同値である。

一般の場合、\(m = q\) で主張が成立すると仮定する。このとき

(|A|^{q+1})_{ij} = \sum_{k=1}^{n} (|A|^q)_{ik} |A|_{kj} = \sum_{k=1}^{n} (|A|^q)_{ik} |a_{kj}| \neq 0

であることは、少なくとも1つの \(k\) に対して \((|A|^q)_{ik}\) と \(|a_{kj}|\) が両方非ゼロである場合に限る。これは、\(P_i\) から \(P_k\) への長さ \(q\) の経路と、\(P_k\) から \(P_j\) への長さ1の経路が存在する場合に同値であり、つまり \(P_i\) から \(P_j\) への長さ \(q+1\) の経路が存在する場合に同値である。

同じ議論は \(M(A)\) に対しても成立する。■