6.2.20
系6.2.20．行列 \(A \in M_n\) およびノード \(i, j \in \{1, \dots, n\}\) に対して、\(i \neq j\) ならば、\(\mathcal{G}(A)\) において \(P_i\) から \(P_j\) への経路が存在することは、\((I + |A|)^{n-1}\) の \(i,j\) 成分が非ゼロであることと同値である。
演習．前系を用いて、SC性を判定する明示的な計算テストを作成せよ。この際、\(n-2\) 回の行列乗算の代わりに、約 \(\log_2(n-1)\) 回の行列乗算で済む方法を考えよ。ヒント：\((I + |A|)^2\) や、その二乗行列を順次考慮する。
次に、SC性のもう一つの同値な特徴付けを導入する。これは \(\mathcal{G}(A)\) の強連結性が単に \(\mathcal{G}(A)\) の位相的性質であり、ノードのラベル付けとは無関係であることに基づく。ノードのラベルを置換しても、グラフは強連結であるか否かの性質は変わらない。
行列 \(A\) の第 \(i\) 行と第 \(j\) 行、および第 \(i\) 列と第 \(j\) 列を入れ替えることは、\(\mathcal{G}(A)\) におけるノード \(P_i\) と \(P_j\) のラベルを入れ替えることに相当する。逆に、\(\mathcal{G}(A)\) のノードのラベルを置き換えることは、行列 \(A\) のいくつかの行と列の入れ替えに対応する。したがって、置換相似 \(A \to P^T A P\)（有限回の行・列の入れ替えの結果）は、\(\mathcal{G}(A)\) のノードラベルの置換と同値である。
重要なのは、行列 \(A\) の行と列のいくつかを置換して、次の定義で示す特殊なブロック形式に変換できるかどうかである。
行列解析の総本山
コメント