本記事の内容
本記事は行列の既約性、可約性、有向グラフの強連結性について解説する記事です。
本記事を読むにあたり、隣接行列、有向グラフについて知っている必要があるため、以下の記事も合わせてご覧ください。
今回、次回、次々回で言いたいこと
今回と次回で言いたいことは次の2つです。
定理0-1.
与えられた\(n\)次の正方行列\(A=\left( a_{ij}\right)\)が可約であれば、添字の番号を並べ替えることにより、次の行列に変形することが出来る。 $$ \begin{pmatrix} A_1&\ast&\ast&\cdots&\ast\\ O&A_2&\ast&\cdots&\ast\\ \vdots&\ddots&\ddots&\ddots&\ast\\ O&\cdots&O&A_{s-1}&\ast\\ O&O&\cdots&O&A_s\\ \end{pmatrix} $$ ただし、\(A_i\)は既約な正方行列である。これは次々回証明します。
定理0-2.
有向グラフが強連結であることと、有向グラフの隣接行列が既約であることは同値である。今回はこの十分性を証明します。
行列の既約と可約
まず、行列の既約と可約について解説します。
行列の添字の並び替え
\(n\)次正方行列\(A=\left( a_{ij}\right)\)に対して、添字の並び替えというのは、要するに置換のことです。
置換とは何だったかと言うと、以下でした。
置換
\(n\in\mathbb{N}\)とする。\(n\)個の文字\(1,2,\dots,n\)からなる集合を $$ M_n=\{1,2,\dots,n\} $$ とする。写像\(\sigma:M_n\to M_n\)が全単射であるとき、\(\sigma\)を\(M_n\)の置換という。置換\(\sigma\)による対応が $$ 1\mapsto i_1,\ 2\mapsto i_2,\dots,n\mapsto i_n $$ であるとする、すなわち、 $$ \sigma(1)=i_1,\ \sigma(2)=i_2,\dots,\ \sigma(n)=i_n $$ とする。このとき\(\sigma\)を $$ \sigma= \begin{pmatrix} 1&2&\cdots&n \\ i_1&i_2&\cdots&i_n\\ \end{pmatrix} $$ と書く。
詳しくは、【線型代数学の基礎シリーズ】行列式編 その1を御覧ください。
より具体的に言えば、\(n\)次正方行列\(A=\left( a_{ij}\right)\)において、添字の並び替えというのは\(\{1,2,\dots,n\}\)を\(\{k_1,k_2,\dots,k_n\}\)と並び替える置換のことです。
つまり、\(n\)次正方行列\(A=\left( a_{ij}\right)\)に対して、\((i,j)\)成分が\(a_{k_ik_j}\)となるような、添字の並び替えにより得られる行列を、置換\(\left( k_1,k_2,\dots,k_n\right)\)により得られる行列といいます。
ちなみに、置換は
$$
\left(
\begin{array}{c}
1&2&\cdots&n\\
k_1&k_2&\cdots&k_n\\
\end{array}
\right)
$$
と書かれますが、これは、省略して\(\left(k_1,k_2,\dots,k_n \right)\)と書かれるのでした。
例1. 行列
$$
A=
\begin{pmatrix}
a_{11}&a_{12}&a_{13}\\
a_{21}&a_{22}&a_{23}\\
a_{31}&a_{32}&a_{33}\\
\end{pmatrix}
$$
において、\((1,2,3)\)を\((3,1,2)\)に並び替えた行列は
$$
A=
\begin{pmatrix}
a_{33}&a_{31}&a_{32}\\
a_{13}&a_{11}&a_{12}\\
a_{23}&a_{21}&a_{22}\\
\end{pmatrix}
$$
です。
隣接行列における添字の並び替え
行列における添字の並び替えは、単純に成分を並び替えるということですが、その行列が隣接行列だった場合、どういう意味を持つのか、ということを述べます。
述べると言っても誠に単純な話で、
ということです。
前回の記事で「隣接行列とは何か？」について解説しました。
その時、「このように名前(番号)を付けます。」というように、さも当然のように、それしか番号の付け方が無いかのように説明してしまいましたが、実はそんな事はありません。
要するに、グラフの頂点に番号をつけるときは恣意的なため、隣接行列は1つとは限りません。
しかし、成分を並び替えることでどの隣接行列も同じ形に変形することが出来ます。
ちょっと踏み込んだ言い方をすれば、隣接行列の番号の並び替えは同形なグラフを求めている、という言い方もできます。
行列の可約と既約
行列が可約だ、というのは
を言います。
“っぽい”というのは抽象的ですが、イメージとしてはそんなもんです。
これを厳密に書くと以下です。
可約、既約
\(n\)次正方行列\(A=\left(a_{ij} \right)\)が可約(reducible)とは、添字の並び替えにより $$ \begin{pmatrix} A_{11}&A_{12}\\ O&A_{22}\\ \end{pmatrix} $$ と表現出来るときをいう。ただし、\(A_{11}\)および\(A_{22}\)は正方行列である。行列\(A\)が可約でないとき既約(irreducible)であるという。例2. \(\displaystyle A=\begin{pmatrix}1&0\\1&1\\ \end{pmatrix}\)は\((1,2)\)を\((2,1)\)に入れ替えることで\(\displaystyle\begin{pmatrix}1&1\\0&1\\ \end{pmatrix}\)となるため、\(A\)は可約です。
例3. \(\displaystyle A=\begin{pmatrix}0&1\\1&1\\ \end{pmatrix}\)は\((1,2)\)を\((2,1)\)に入れ替えても\(\displaystyle\begin{pmatrix}1&1\\1&0\\ \end{pmatrix}\)となるため既約です。
強連結と正方行列の既約性
ここではグラフが強連結であることと、正方行列の既約性のグラフ理論的判定法について解説します。
強連結
強連結というのは、一言でいうと
です。
無向グラフのときは、各辺に往復の2方向があるため、「頂点の間に辺が存在する」という状態なだけで、「頂点同士が繋がっている」と言えました。
しかし、有向グラフの場合はそうもいきません。
なぜなら、各辺に対して1つの方向が決まっているからです。
強連結は、各辺に1つの方向が定まっているにも関わらず、どの頂点からもどの頂点へと辺をたどって行き着くことができる状態を指します。
すなわち、以下です。
強連結
有向グラフ\(X^o=(V,E^o)\)が強連結(strongly connected)であるとは、任意の2つの頂点\(x,y\in V\)に対して、\(o(c)=x\)かつ\(t(c)=y\)となるような路\(c\)が存在するときをいう。 すなわち、どんな2頂点に対しても、一方から他方への有向辺の向きに合わせてたどっていくことが出来るときをいう。強連結であれば連結ですが、逆は成り立ちません。
強連結と隣接行列の関係
強連結性と隣接行列の関係を表す事実を証明します。
定理5.
可約な\(n\)次正方行列\(A\)に対する有向グラフ\(X^o\)は強連結ではない。対偶を取れば、有向グラフ\(X^o\)が強連結であれば、\(X^o\)の隣接行列\(A\)は既約である。定理5.の証明
\(A\)は可約なので、添字を並び替えることで
$$
\begin{pmatrix}
A_{11}&A_{12}\\
O&A_{22}\\
\end{pmatrix}
$$
と変形できたとします。
ただし、\(A_{11}\)と\(A_{22}\)はそれぞれ\(n_1\)次、\(n_2\)次正方行列とします(\(n_1+n_2=n\))。
\(\left\{1,2,\dots,n\right\}\)を\(S=\left\{1,2,\dots,n_1\right\}\)と\(T=\left\{n_1+1,n_1+2,\dots,n_1+n_2=n\right\}\)の2つに分けます。
このとき、\(T\)の要素を始点、\(S\)の要素を始点とする有向辺は存在しません。
実際、もし仮に存在したとすると、\(a_{ij}\neq0\)となるような\(i\in T\)と\(j\in S\)が存在することになります。
しかしながら、上記の図の右側の行列の図を見ればわかるように、\((i,j)\)成分の位置には\(0\)歯科存在しないので、矛盾です。
故に、\(T\)から\(S\)に向かうような有向辺が存在しないので、グラフは強連結ではありません。
定理5.の証明終わり
皆様のコメントを下さい！
今回は数学者に関するジョークを紹介します。
エンジニアと化学者と数学者が古いモーテル(自動車で旅行をする人を想定して設置された、セルフサービスを基本とするホテルのこと)の隣接した客室に宿泊していました。
さいしょにエンジニアのコーヒーメーカーから出火しました。
かれは煙たさから飛び起き、コーヒーメーカーのプラグを抜いて機会を窓の外に捨て、そのまま眠りにつきました。
その夜、しばらくしてから、化学者が流行り煙たさから飛び起き、煙草の吸殻入れが燃えているのを見つけました。
彼は独り言で「ふむふむ。どうやって火を消そうかな。燃料の温度を引火点より下げるか、燃えているものを酸素から引き離す、あるいはその両方を行えばいいけど、それは水を書けることで達成できるね。」といい、灰皿を拾ってシャワー室に置いて蛇口をひねり、火が消えた後に眠りにつきました。
数学者は勿論、これらの火事を窓から眺めていました。
だから、しばらくした後に彼のパイプの胚芽ベッドシーツに火を付けた際にも微塵も動じず「解決法は既に存在する。」としてそのまま眠りについたそうな。
これは、解を具体的に明示しないで、その存在のみを問題にする数学者の手法を皮肉っています。
「まあ、たしかに化学者やらと比べるとそうだね。」という印象でした。
このようなジョークを知っている方は是非コメントで教えて下さい！
結
今回は、行列の既約性と有向グラフの強連結がそれぞれ何かを解説しました。
それぞれ
- 行列の既約性：添字の並び替えをしても、正方行列を使って上三角行列のようなブロック分けが出来ないときにその行列は既約という。
- 強連結：有向グラフにおける連結。
です。
次回は強連結成分について解説します。
乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければ全てお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ３日以内にお答えします。
もし直ちに回答が欲しければその旨もコメントでお知らせください。直ちに対応いたします。
この記事の内容をより詳しく知りたい方は以下の書籍を御覧ください！
コメントをする
行列の可約と規約をちょうど調べていたのでとても助かりました。大変感謝しております。
Noz様
コメントありがとうございます！
こちらこそご覧頂き誠にありがとうございます。
大変励みになります！
例2と例3は一見同じ行列を考えているように見えます。何が違うのでしょうか。
名無し様
コメントありがとうございます。
>例2と例3は一見同じ行列を考えているように見えます。何が違うのでしょうか。
とのお問い合わせですが、
の間違いでした。
ご指摘ありがとうございました。