こんにちは！半沢です！
今回の記事ではグラフ理論における行列木定理(matrix-tree theorem)について解説します。
ケイリーの公式を系として導くことができる，かなり強力な定理です。
その美しさを味わってみましょう。
行列木定理
行列木定理(matrix-tree theorem)
\(G\,\)を連結単純グラフとする。
このとき\(\,G\,\)の全域木の総数は\(\,G\,\)のラプラシアン\(\,L\,\)の任意の余因子に等しい。
かなり美しい定理です。キルヒホッフの定理(Kirchhoff’s theorem)とも呼ばれます。
ラプラシアンの固有値で主張を表すこともできます。それについては補足で主張と証明を書いてあります。
この定理の系として次のケイリーの公式が得られます。
ケイリーの公式(Cayley’s formula)
\(n\,\)点からなる異なるラベル付き木は\(\,n^{n-2}\,\)個ある。
ケイリーの公式を行列木定理から証明しましょう。
\(n\,\)点からなる異なるラベル付き木は，\(\,n\,\)点からなる完全グラフの全域木として考えられます。
\(n\,\)点からなる完全グラフのラプラシアンは以下のような\(\,n\,\)次正方行列となります。
\[\underbrace{\begin{pmatrix} n-1 & -1 & \cdots & -1\\ -1 & n-1 & \cdots & -1\\ \vdots & \vdots & \ddots & \vdots\\ -1 & -1 & \cdots & n-1 \end{pmatrix}}_{n列}\]
よってその余因子の一つである，第\(\,(1,1)\,\)余因子
\[\underbrace{\begin{vmatrix} n-1 & -1 & \cdots & -1\\ -1 & n-1 & \cdots & -1\\ \vdots & \vdots & \ddots & \vdots\\ -1 & -1 & \cdots & n-1 \end{vmatrix}}_{n-1列}\]
が\(\,n^{n-2}\,\)になることを示せば良いです。
上の余因子は第\(\,1\,\)列以外の列ベクトルを，第\(\,1\,\)列ベクトルに全て足し合わせると，
\[\begin{vmatrix} 1 & -1 & \cdots & -1\\ 1 & n-1 & \cdots & -1\\ \vdots & \vdots & \ddots & \vdots\\ 1 & -1 & \cdots & n-1 \end{vmatrix}\]
となります。
そこで今度は第\(\,1\,\)ベクトルをその他の列ベクトルに足し合わせると，
\[\underbrace{\begin{vmatrix} 1 & 0 & \cdots & 0\\ 1 & n & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 1 & 0 & \cdots & n \end{vmatrix}}_{n-1列}\]
となり，こちらの行列式は明らかに\(\,n^{n-2}\,\)なので，ケイリーの公式は示されました。
余談ですが，ケイリーの公式は，私の知る限りでも，(今回の証明も含めて)6通りの証明があります。
記事として改めて書く予定ですので，楽しみにしておいてください。
証明
補題
まずは線形代数学の補題から示していきましょう。
補題
\(n\,\)次正方行列\(\,A\,\)について，行・列ベクトルの和がそれぞれ\(\,\bm{0}\,\)となるとき，
\(A\,\)の第\(\,(i,j)\,\)余因子\(\,C_{ij}\,\)は\(\,(i,j)\,\)に依らない。
ラプラシアンがこの補題の前提を満たすことに着目しましょう。
それでは証明です。
条件\(\,(\,\mathrm{i}\,)\,\)から，\(\,A\,\)の列(行)ベクトルは線形従属なので，\(\,\det A=0\,\)です。
よって\(\,\operatorname{rank}A\leq n-1\,\)です。
\(\operatorname{rank}A\lt n-1\,\)のとき，\(\,\operatorname{rank}\,\)は\(\,0\,\)でない小行列式の最大次数[1]を表すので，\(\,\forall i,j,\,\,C_{ij}=0\,\)となり，\(\,(\mathrm{ii})\,\)は成り立ちます。
故に後は\(\,\operatorname{rank}A=n-1\,\)のときを考えましょう。
このとき\(\,\dim(\operatorname{Ker}A)=\dim(\operatorname{Ker}A^{\top})=n-\dim(\operatorname{Im}A)=1\,\)です。
ここで条件\(\,(\,\mathrm{i}\,)\,\)は\(\,A\bm{1}=0,\,\,A^{\top}\bm{1}=0\,\)と表せます(\(\,\bm{1}\,\)は全成分が\(\,1\,\)の\(\,n\,\)項列ベクトルです)。
よって\(\,\bm{1}\in \operatorname{Ker}A,\operatorname{Im}A^{\top}\,\)で，\(\,\operatorname{Ker}A=\operatorname{Ker}{A}^{\top}=\langle\bm{1}\rangle\,\)となります。
また\(\,A\,\)の余因子行列\(\,\tilde{A}\,\)の性質から，\(\,A\tilde{A}=(\det A) I=O\,\)です。
これは\(\,\tilde{A}\,\)の列ベクトルが\(\,\operatorname{Ker}A\,\)に属することを意味しますね。
故に\(\,\operatorname{Ker}A=\langle\bm{1}\rangle\,\)から，ある定列ベクトル\(\,\bm{c}\,\)を用いて，\(\,\tilde{A}=\bm{1}\bm{c}^{\top}\,\)と表せます。
同様に\(\,A^{\top}\tilde{A}^{\top}=O\,\)も成り立ち，\(\,\tilde{A}\,\)の行ベクトル(の転置)は\(\,\operatorname{Ker}A^{\top}\,\)に属することを意味します。
\(\tilde{A}=\bm{1}\bm{c}^{\top}\,\)よりその行ベクトルとは\(\,\bm{c}\,\)のことで，\(\,\bm{c}=c\bm{1}\,\,(c\in \mathbb{K})\,\)と表せます。
以上より\(\,\tilde{A}=c\bm{1}\bm{1}^{\top}\,\)を表せることが分かり，これより明らかに\(\,(\mathrm{ii})\,\)が分かります。\(\quad\square\)
余談ですが，この補題の逆は成り立ちません。例えば行列\(\,\begin{pmatrix}1&0\\0&0\end{pmatrix}\,\)を考えてみてください。
締めくくり
グラフのラプラシアンは補題を満たすので，その第\(\,(i,j)\,\)余因子は\(\,(i,j)\,\)に依りません。
よって目的の定理を示すには次の主張を示せば十分です。
連結単純グラフ\(\,G\,\)のラベル付き全域木の総数は，
そのグラフのラプラシアン\(\,L\,\)の主余因子に等しい。
証明上の注意として，グラフ\(\,G=G(V,E)\,\)について，そのラプラシアン\(\,L\,\)は\(\,|V|\times|V|\,\)の行列なので，その行・列の指定を点により指定します。
つまり「第\(\,i\,\)行」という呼び方ではなく，\(\,v\in V\,\)を用いて「第\(\,v\,\)行」と指定するということです。
また\(\,G\,\)の接続行列も\(\,|V|\times |E|\,\)の行列なので，同様に列の指定を辺により指定することにします。
それでは証明です。
コーシー・ビネの公式(参考:“高校数学の美しい物語”さんによる解説)を使います。
ラプラシアン\(\,L\,\)は向き付けた接続行列\(\,B\,\)により\(\,L=BB^{\top}\,\)と表されます。
よってラプラシアンの第\(\,v\,\)行，第\(\,v\,\)列(\(\,v\,\)は適当な点)を除いた行列を\(\,L_v\,\)，接続行列の第\(\,v\,\)行を除いた行列を\(\,B_v\,\)とおくと，\(\,L_v=B_vB_v^{\top}\)となります。
グラフ\(\,G\,\)は連結なので，\(\,|E|\geq |V|-1\,\)を満たしています。
よって先ほどの等式にコーシー・ビネの公式を用いることができ，
\[C_v=\sum_{N\in S} \det N\cdot\det N^{\top}=\sum_{N\in S} (\det N)^2 \]
となります。
ただし\(\,C_v\,\)は\(\,L\,\)の第\(\,v\,\)主余因子で，集合\(\,S\,\)は行列\(\,B_v\,\)の\(\,|V|-1\,\)次小行列の集合です。
元の\(\,B_v\,\)は\(\,(|V|-1)\times |E|\,\)の行列だったので，\(\,B_i\,\)の\(\,|V|-1\,\)次小行列\(\,N\,\)の選び方は，グラフ\(\,G\,\)において辺を\(\,|V|-1\,\)本持つ部分グラフ\(\,G_N\,\)を選ぶことに対応します。
この対応をもとで次の式が成り立つことが証明の重要な点です。
\[|\det N|=\begin{cases}+1 && G_Nが全域木となる. \\ \phantom{+}0&& G_Nが全域木でない. \end{cases}\]
つまり\(\,|\det N|\,\)は\(\,G\,\)の全域木のカウントを行ってくれるということです。
よって先ほどの式を示せば証明は完了です。
まず\(\,G_N\,\)が全域木でないときを考えましょう。
\(G_N\,\)は点が\(\,|V|\,\)個で，辺が\(\,|V|-1\,\)個であることに注目しましょう。
そのため\(\,G_N\,\)は非連結グラフです(そうでないと点と辺の個数から\(\,G_N\,\)は全域木になることが言えます)。
よって少なくとも連結成分が\(\,2\,\)個存在するので，点\(\,v\,\)を含まない連結成分内の点に対応する\(\,N\,\)の行ベクトルを考えます。
この行ベクトルを足し合わせると(グラフの向き付けにより)\(\,\bm{0}\,\)となるので，\(\,N\,\)の行ベクトルには線形従属な組み合わせが含まれることが分かります。
故にこのとき\(\,\det N=0\,\)となります。
今度は\(\,G_N\,\)が全域木をなす場合を考えましょう。
まず木の性質から\(\,G_N\,\)には少なくとも二つ次数\(\,1\,\)の点が存在するので，その中で\(\,v\,\)とは一致しない適当な点\(\,v_1\,\)と\(\,v_1\,\)に接続している辺\(\,e_1\,\)を取ってきます。
そして\(\,G_N\,\)から\(\,v_1,e_1\,\)を削除したグラフを考えると，それも木なので，その新たな木で再び次数\(\,1\,\)の点\(\,v_2\,\)と\(\,v_2\,\)に接続している辺\(\,e_2\,\)を取ってきます。
これを繰り返し，\(\,G\,\)の点の列\(\,v_1,\ldots,v_{|V|-1}\,\)，辺の列\(\,e_1,\ldots,e_{|V|-1}\,\)が取れます。
この取り方から\(\,i\lt j\,\)なら\(\,v_i\not\in e_j\,\)となります。
そのため\(\,N\,\)の行・列を\(\,v_1,\ldots,v_{|V|-1}\,\)や\(\,e_1,\ldots,e_{|V|-1}\,\)の順序に従って並び替えると，
\[\begin{pmatrix}\pm1 & & & \\ \ast & \pm1 & &\text{\huge{0}} \\ \vdots & & \ddots \\ \ast & \ast & \dots & \pm1 \end{pmatrix}\]
のような対角成分が\(\,\pm1\,\)の下三角行列になります。
行・列の並び替え行列式の値は不変なので，上の行列の行列式の値は\(\,\det N\,\)です。
よって\(\,|\det N|=1\,\)となることが分かるので，証明完了です。\(\quad\square\)
まとめ
今回の記事では行列木定理(matrix-tree theorem)を解説いたしました。
\(\det N\,\)が全域木のカウントを行ってくれる点が面白かったですね。
アイキャッチ画像の\(\,\displaystyle\frac{1}{|V|}\prod_{i=1}^{|V|-1}\lambda_i\,\)という，ここまで登場していない謎の数式は，行列木定理のラプラシアンの固有値による表式です。
補足で解説しているので，興味のある方は読んでみてください。
もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#サイエンティクスでつぶやいていただけると，できる限り対応します。
ここまで読んでいただき，ありがとうございました。
補足
補足では行列木定理のラプラシアンの固有値による以下の表式を，これまでの表式から導出します。
行列木定理
\(G(V,E)\,\)を単純グラフとし，そのラプラシアン\(\,L\,\)の固有値のうち，\(\,0\,\)を一つだけ除いたものを\(\,\lambda_1,\ldots,\lambda_{|V|-1}\,\)とおく。
このとき\(\,G\,\)の全域木の総数は，\(\,\displaystyle\frac{1}{|V|}\prod_{i=1}^{|V|-1}\lambda_i\,\)と表される。
それでは証明です。
まずラプラシアンの固有多項式の\(\,|xI-L|\,\)の\(\,1\,\)次の係数は，ラプラシアン\(\,L\,\)の第\(\,v\,\)主因子を\(\,C_v\,\)とおくと，
\[(-1)^{|V|-1}\sum_{v\in V}C_v\]
と表されることを示します。
以下，証明のために行列\(\,A\,\)の第\(\,(i,j)\,\)成分を\(\,A_{ij}\,\)を表す表記法を用います。
固有多項式
\[|xI-L|=\sum_{\sigma\in \mathfrak{S}_{V}}\operatorname{sgn}(\sigma) \Biggl(\sum_{v\in V}(xI-L)_{v,\sigma(v)}\Biggr)\]
より，\(\,|xI-L|\,\)に\(\,x\,\)は対角項のみしか現れないので，全て展開したときに\(\,1\,\)次の係数となる部分は，どこか一つの対角成分の\(\,x\,\)を使っていることになります。
仮にそれが第\(\,v\,\)対角成分だったとすると，\(\,1\,\)次の係数となるためには，後は第\(\,v\,\)行・第\(\,v\,\)列以外の定数\(\,-L_{ij}\,\)を選ぶ必要があります。
このとき，この選び方に対応する置換\(\,\sigma\,\)は，\(\,\sigma(v)=v\,\)という固定点を持つので，\(\,V\setminus\{v\}\,\)上の置換に対応します(この対応で置換の符号も不変)。
よって第\(\,v\,\)成分で\(\,x\,\)を使ったときの，\(\,1\,\)次の係数となる部分は\(\,(-1)^{|V|-1}C_v\,\)となります。
後はこれを足し合わせることで，ラプラシアンの固有多項式の\(\,1\,\)次の係数は\(\,\displaystyle(-1)^{|V|-1}\sum_{v\in V}C_v\,\)となることが分かります。
さらに補題から，主余因子は\(\,v\,\)に依らないので，\(\,C\coloneqq C_v\,\)とおくと，\(\,1\,\)次の係数は
\[|V|(-1)^{|V|-1}C\]
と表せることが分かります。
ここで別角度から固有多項式の\(\,1\,\)次の係数を求めましょう。
補題の証明からも分かるように，\(\,L\bm{1}=0\,\)でラプラシアンは固有値\(\,0\,\)を持ちます。
そのため\(\,0\,\)を一つだけ除いたラプラシアンの固有値を\(\,\lambda_1,\ldots,\lambda_{|V|-1}\,\)とおくと，
固有方程式は\(\,x\displaystyle\prod_{i=1}^{|V|-1}(x-\lambda_i)\,\)と書けます。
故にこの\(\,1\,\)次の係数は
\[(-1)^{|V|-1}\prod_{i=1}^{|V|-1}\lambda_i\]
となります。
上で得られた表式と比べて
\[\,C=\frac{1}{|V|}\prod_{i=1}^{|V|-1}\lambda_i\,\]
を得ます。
参考文献
- \([1]\) 斎藤正彦.”線形代数入門 基礎数学1″.初版.東京大学出版.1966出版.p.117.
- \([2]\) “ビネ・コーシーの定理とその証明”.高校数学の美しい物語.2020-08-27更新.https://manabitimes.jp/math/1305.2026-02-11参照.
- \([3]\) Martin Aigner,Günter M. Ziegler.”Proofs from THE BOOK”.Sixth Edition.Springer.2018出版.p.237.
