行列冪から学ぶグラフ理論

対象読者は

行列の累乗を計算するのが煩わしいと感じている方々です。グラフ理論的観点から解決させます。線形代数履修したけど、結局行列って何に使うねんの人も歓迎です。

やりたいこと

・行列の累乗をグラフに帰着させることで暗算できるように
・逆にグラフのある値が欲しい時に、行列の累乗に問題を帰着させる

素朴な計算方法

以下のような行列を考えます

A = 
\begin{pmatrix}
1 & 1 & 1  \\
0 & 1 & 1 \\
0 & 1 & 1
\end{pmatrix}

早速ですが、この行列の3乗を計算してみてください。

愚直にやると以下のように求められます。

\begin{eqnarray}
A^3 &=& 
\begin{pmatrix}
1 & 1 & 1  \\
0 & 1 & 1 \\
0 & 1 & 1
\end{pmatrix} ・\begin{pmatrix}
1 & 1 & 1  \\
0 & 1 & 1 \\
0 & 1 & 1
\end{pmatrix}・\begin{pmatrix}
1 & 1 & 1  \\
0 & 1 & 1 \\
0 & 1 & 1
\end{pmatrix}\\
&=&\begin{pmatrix}
1\times1+1\times0+1\times0 & 1\times1+1\times1+1\times1 & ..  \\
0\times0+1\times0+1\times0 & .. &  \\
.. &  & 
\end{pmatrix}・\begin{pmatrix}
1 & 1 & 1  \\
0 & 1 & 1 \\
0 & 1 & 1
\end{pmatrix}\\
&=&
\begin{pmatrix}
1 & 3 & 3  \\
0 & 2 & 2 \\
0 & 2 & 2
\end{pmatrix}・\begin{pmatrix}
1 & 1 & 1  \\
0 & 1 & 1 \\
0 & 1 & 1
\end{pmatrix}\\&=&\begin{pmatrix}
1\times 1+3\times0+3\times0 & 1\times1+3\times1+3\times1 & ..  \\
0\times0+2\times0+2\times0 & .. &  \\
.. &  & 
\end{pmatrix}\\&=&\begin{pmatrix}
1 & 7 & 7  \\
0 & 4 & 4 \\
0 & 4 & 4
\end{pmatrix}
\end{eqnarray}

「んーここは1であっちは0だからつまりここは0で..次にここは..」

遅いです。グラフを考えます。

グラフとは

あー、$y=x$とかそういうやつね。（←違います)

それもグラフですが、これから考えるのは離散グラフです。離散グラフは頂点と呼ばれる点(node)と、それらを結びつける辺(edge）からなる数学的な構造体です。例を挙げます。

• 町1, 町2, 町3があります。町1からは町2, 町3に行くことができます(逆向きはいけません)。また、町2と町3はお互いに行き来できます。さらに同じ街であれば自由に散歩できます。

これを離散グラフを使って書き表すと以下のように表せます。

試しに色々、計算してみましょう。町1からちょうど3回の移動を考えます。
例えば1→2→3→2であったり、1→1→2→3という移動ができますね。
終点はそれぞれ2, 3です。(注:自分への移動も含みます)

• では町2に始まって町3で終わるような長さが3の経路は何通りあるでしょうか？

これはグラフを見ると4通りですね。(2→2→2→3, 2→3→2→3,2→3→3→3,2→2→3→3)

ではさらに、始点と終点を全て考慮した3×3=9パターンを考えます。
んーと、言葉で書くとめんどくさいですよね。ここである簡単な関数を定義します。

$f(i, j, k):$町$i$から町$j$にk回の移動で行く経路の総数

• 先ほど計算したのは$i=2,j=3,k=3$の場合ですね。つまり$f(2,3,3)=4$です。

今考えているのはk=3の場合のみなので一旦kはここでは省きます。

以降計算省略のポイントです

• グラフを見ると町2と町3は対称的な関係です。つまり以下が成立します。
  • $f(1, 3)=f(1, 2)$
  • $f(2, 1)=f(3, 1)$
  • $f(2,2) = f(2, 3)=f(3, 3)=f(3,2)$
• さらに町2から町1へは交通手段がないので$f(2,1)$は明らかに0です。
  • これをグラフ理論の言葉では頂点1,2が強連結でないと言います。

つまり計算する必要があるのはなんとf(2,2),f(1,2)の2つのみです。

f(2,2),f(1,2)についてグラフを見ながら数えて、以上の結果をまとめるとこうなります。

f(2, 1) = f(3, 1) = 0\\
f(1, 1) = 1\\
f(2, 2) = f(2, 3) = f(3, 2) = f(3, 3) = 4\\
f(1, 2) = f(1, 3) = 7

少し見にくいですね。始点を行,終点を列にとった行列に対応させてみましょうか。

\begin{pmatrix}
f(1,1) & f(1, 2) & f(1, 3)  \\
f(2, 1) & f(2, 2) & f(2, 3) \\
f(3, 1) & f(3, 2) & f(3, 3)
\end{pmatrix} = \begin{pmatrix}
1 & 7 & 7  \\
0 & 4 & 4 \\
0 & 4 & 4
\end{pmatrix}

綺麗にまとまりました。

グラフによる解釈

上の結果を、先ほど計算した行列Aの3乗と比べてみましょう。

..どうやら一致していますね。実はこれは偶然ではなく必然です。
簡単に帰納法で証明できます。やってみます。(一般のn乗の場合を考えます。)

行列サイズを|V|としておきます。これは頂点数を|V|と表すことに起因します。

• n = 1の時は明らかですね。

  • Aの各成分$a_{ij}$が辺の有無、つまり$f(i, j, 1)$に一致しています。

• n=kの場合に成り立つと仮定すると仮定します。

  • つまり$A^k$の$ij$成分は$f(i, j, k)$である、ということです。

  • n=k+1の場合に示したいのは$A^k+1$の$ij$成分が$f(i, j, k+1)$に一致することです。

    • グラフの性質から$f(i, j, k+1)$を$f(i, j, k)$で表すことができないか試みます。

頂点iから頂点jへk+1回の移動で移動する経路の総数は、頂点iから各頂点mに向かってちょうどk回の移動を行い、さらに各頂点mから頂点jへ1回の移動を行う経路の総数の総数に同値です。

よって式にすると以下が成り立ちます。終点の直前の頂点で場合分けするイメージです。

f(i, j, k+1) = \sum_{m=1}^{|V|}f(i, m, k)・f(m, j, 1)\,\,\,\,\,\dots(\ast)

これを用いてn=k+1の場合に成り立っているかを確認すればいいですね。

A^{k+1} = A^kA\\

ここで$A^{k+1}$のi 行j 列目の成分を考えると正方行列の積の定義から$A^k$のi行と$A$のj列との内積に等しいことがわかります。n=kの時に成り立つことは仮定していることに注意すると、

\begin{eqnarray}
a^{k+1}_{ij} &=& <\vec{a}^k_{i}, ^t\vec{a}_j>\\
&=& f(i, 1, k)・f(1, j, 1)+...+f(i, |V|, k)・f(|V|, j, 1)\\
&=&\sum_{m=1}^{|V|}f(i, m, k)・f(m, j, 1)\\
&=&f(i, j, k+1) \,\,\,\,\,\,\dots(\ast)
\end{eqnarray} 

さらに拡張(成分が0,1以外だとどうか)

成分0、１からなる行列の累乗の値がグラフの経路数に帰着出来ることが示せました。

では一般にはどうでしょうか。実はその場合もほとんど変わりません。

具体的には先ほど辺の有無でグラフを構築していたところに追加で、
辺に対して行列の対応する成分と同じだけの重みを与えてやれば解決です。

• 行列Aの各$a_{ij}$成分に対し、頂点$i$から$j$へ重み$a_{ij}$の辺を貼るグラフを考える
  • 先ほどの$0,1$行列の場合だと重み$1$の辺を貼るグラフとも言い換えられます。

その場合は先ほど定義した関数を以下のように変えてやります。

$\tilde{f}(i, j, k)$: $i$から$j$へ$k$回の辺移動を繰り返すことでいける経路の辺の重み積の総和

上記を用いると一般の場合には以下が成立します。

A^k=
\begin{pmatrix}
a_{11} & \cdots & a_{1j} & \cdots & a_{1n} \\
\vdots & \ddots &  &  &  \\
a_{i1} &  & a_{ij} &  & \vdots \\
\vdots &  &  &  &  \\
a_{n1} &  & .. &  &
\end{pmatrix}^k
=
\begin{pmatrix}
\tilde{f}(1,1,k) & \cdots & \tilde{f}(1,j,k) & \cdots & \tilde{f}(1,n,k) \\
\vdots & \ddots &  &  &  \\
\tilde{f}(i, 1, k) &  & \tilde{f}(i,j,k) &  & \vdots \\
\vdots &  &  &  &  \\
\tilde{f}(n,1,k) &  & \cdots &  & 
\end{pmatrix}

計算例

問1

• 以下のn次正方行列のm乗を求めてみてください。左上方向の対角に1が並ぶ行列です。

A=
\begin{pmatrix}
 &  &  &  & 1 \\
 &  &  & 1 &  \\
 &  & .. &  &  \\
 & 1 &  &  &  \\
1 &  &  &  &  
\end{pmatrix}

(本来なら頭の中で)この行列をグラフ化します。重みは1なので省きます。

考察します。

• 頂点$i$から1回の移動で頂点$n-i+1$に行きます。それ以外の経路はありません
• 頂点$i$から2回の移動で頂点$i$自身に戻ります。それ以外の経路はありません
• 頂点$i$から3回の移動で頂点$n-i+1$に行きます。それ以外の経路はありません
• ...(以降繰り返し)

クリックで答え

A^k  = \left\{
\begin{array}{ll}
A & (k: odd)\\
E & (k: even)
\end{array}
\right.

• このように各連結成分ごとに考えられるので簡潔です。

問2

・以下のn次正方行列のm乗を求めよ。(高圧的)

A=
\begin{pmatrix}
0 & \lambda &  &  &  \\
 & 0 & \lambda &  &  \\
 &  & \ddots & \ddots &  \\
 &  &  & 0 & \lambda \\
 &  &  &  & 0 
\end{pmatrix}

グラフを書きます。が、今回は成分が0,1ではないので重みをつけて考えます。

考察します

• 巡回することはないです。
  • グラフ理論的には有向非巡回グラフ(DAG)と言います。
• 始点$i$,長さ$k$の経路を考えると、重み$\lambda^k$,終点$i+k$の1本のみです。
• 長さが$n$以上の経路は存在しません。

クリックで答え

A = \begin{pmatrix}
0 & \lambda &  &  &  \\
 & 0 & \lambda &  &  \\
 &  & \ddots & \ddots &  \\
 &  &  & 0 & \lambda \\
 &  &  &  & 0 
\end{pmatrix},A^2=
\begin{pmatrix}
0 & 0 &\lambda^2   &  &  \\
 &  & & \ddots  &  \\
 &  & \ddots &  & \lambda^2 \\
 &  &  &  & 0 \\
 &  &  &  & 0 
\end{pmatrix}\\
A^{n-1}=
\begin{pmatrix}
0 & \cdots &  \cdots & 0 & \lambda^{n-1} \\
 &  & &  \ddots & 0 \\
 &  & \ddots &  & \vdots \\
 &  &  &  & \vdots \\
 &  &  &  & 0 
\end{pmatrix},A^n=O,A^{n+1}=O..

• グラフ化した時にDAGであれば、Aは冪零行列だということも明らかです
  • 具体的には(最長パスの長さ + 1) で必ず冪零です。

おまけ (雑です)

行列の積を考える際、足し算と掛け算が内部では行われます。

• $A^2$の$a^2_{ij}$成分を例に取ると以下です

a^2_{ij}=a_{i1}\times a_{1j} + a_{i2}\times a_{2j} +\cdots+a_{in}\times a_{nj}

• ここで$\times$,$+$の代わりに、それぞれ$+, min$に変えてみましょう。さらに加法の単位元が0であったところを$min$の単位元である $\infty$に取り替えます。

  • $min$はその中で最小値を取る演算です。$min(2, 4, 1, \infty) = 1$です。
    • (この演算の置き換えを大雑把にトロピカル半環と言ったりします)

• 以下のような形に変わります

a^2_{ij}=min(a_{i1} + a_{1j}, a_{i2} + a_{2j}, \cdots , a_{in} + a_{nj})

これの何が嬉しいかというと、このように行列の積を定義することにより

行列の$k$乗の$ij$成分は始点$i$,終点$j$,長さ$k$の全経路の重み積の総和に等しい。

であったのが、

行列の$k$乗の$ij$成分は始点$i$,終点$j$,長さ$k$の全経路の中で重みが最小の経路に等しい。
(そのような経路が存在しないなら$\infty$)

に代わりグラフの最短経路問題に帰着出来るという点です。

実際には「長さk以下の全経路の中で、」とした方が便利であるため、
元の行列にコスト0の自己ループを付け加えた場合で考えることが多いです。

また、これは実はワーシャルフロイド法というアルゴリズムに一致しています。
おまけ議論はトロピカル代数(Min-Plus代数)と呼ばれる分野の話で、以下に詳しいです。

動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜

ワーシャルフロイド法(全点間最短経路アルゴリズム)

終わりに

願望)
何か間違いなどあれば教えてください..

予定)
グラフの問題を行列の冪乗に帰着させる部分も書きたかったのでまた追加します。