あーあーあ～のブログ

本記事はVRChat Advent Calendar 2021の12日目の記事です．前回はtamsco274さんの[JP]Tutorial Worldから消えたもの，次回はぺたさんの[VRChat] 相対位置を維持するワールド固定の解説です．

はじめに

本記事では行列木定理を証明します．VRChatと行列木定理には殆ど関係がない訳ですが，次のような理由でVRChat Advent Calender 2021に参加しました：

VRChat民の数学やアルゴリズムに対する興味を高めたい；
数学やアルゴリズムに明るい人にVRChatを知ってもらうきっかけにしたい；
12日目を予約していた友達が執筆を取りやめ，代わりに入るように勧めてきた．

そこで，VRChat内のコミュニティについての宣伝を挟んだ後で，本題に移りたいと思います．

VRC競プロ部

VRC競プロ部とは，cleanttedさんが管理人を務めている，競技プログラミングに興味のあるVRChat民向けのDiscordサーバーです．主な活動としてAtCoderのコンテスト後の感想会があるほか，以前は有志により『プログラミングコンテストチャレンジブック』（蟻本）を読む会もありました．それらに私自身は数回程度しか参加していませんが，以前蟻本会に参加した際にはネットワークフローに関する問題について忌憚のない議論をすることができました．

それでは本題に移ります．今回証明する行列木定理とは次の定理です．

定理（行列木定理）

無向グラフの全域木の個数はグラフラプラシアンの任意の余因子に一致する．

読者に仮定する知識は線形代数及びグラフ理論の基礎的な内容です．本記事は筆者が種々の資料を参照しながら証明の大枠を把握したあとで，論理を1から構成し直して作成したものです．そのため不正確な点や行間が広すぎる点などあるかもしれませんので，コメント欄でご意見をお寄せいただければ幸いです．

表記

行列 $A$ の行集合が $X$ ，列集合が $Y$ であるとき $A:X\times Y$ と記します． $A:X\times Y$ の $X'\subset X, Y'\subset Y$ に対応する小行列を $A[X',Y']$ と記します．要素数 $1$ の集合について，意味が明らかな場合に波括弧を省略します．

行列とグラフ

本章では行列木定理を証明する準備として，接続行列の性質について議論します．

接続行列

今，自己ループを持たない有向グラフ $G(V,E)$ を考えます．ただし $V, E$ には適当な順序が入っているものとします．このとき $G$ の接続行列とは行列 $C:V\times E$ で，

$C _ {ve}= \begin{cases} -1 & \text{$v$は$e$の始点} \\ 1 & \text{$v$は$e$の終点} \\ 0 & \text{otherwise} \end{cases}$

となるものです．

接続行列の小行列式

任意の自己ループを持たない有向グラフに対する接続行列は完全単模です．ここで完全単模行列とは，任意の小行列式が $\lbrace -1,0,1\rbrace$ のいずれかである行列です．以下，接続行列が完全単模であることを証明します．小行列の各列に含まれる $1, -1$ はそれぞれ高々 $1$ 個であることに注意します．

補題

接続行列は完全単模．

証明　小行列の次数に関する帰納法で示す．次数 $1$ の場合成立する．次数 $n$ の場合，任意の列（これを $e\in E$ とする）に注目すると次の3つの場合に分けられる：

$e$ 列に $1, -1$ の両方が含まれる場合

$1, -1$ が含まれる行をそれぞれ $u, v\in V$ とする．このとき $v$ 行を $u$ 行に足して $1$ 列に関するLaplace展開を考えると，次数 $n-1$ の小行列式と符号を除いて等しくなる．また，この小行列は，元のグラフから $uv$ 間の枝を削除し $u, v$ を縮約したグラフにおける小行列に一致する．帰納法の仮定からこれは $\lbrace -1,0,1\rbrace$ のいずれかである．

$e$ 列に $1, -1$ の一方のみが含まれる場合

$1$ 列に関するLaplace展開を考えると次数 $n-1$ の小行列式と符号を除いて等しくなるが，帰納法の仮定からこれは $\lbrace -1,0,1\rbrace$ のいずれかである．

$e$ 列に $1, -1$ のどちらも含まれない場合

小行列式は $0$ となる．

よって示された．証明終

グラフラプラシアン

グラフラプラシアンとは，自己ループを持たない有向グラフ $G$ に対し接続行列 $C$ を用いて $L\triangleq CC^\top$ で定義される行列です．グラフラプラシアンの要素は次のように書けます：

$L _ {uv}= \begin{cases} -(\text{$uv$間の辺数}) \,\,& u\neq v\\ \text{$u$の次数} & u=v \end{cases}$

このことは，具体的に積を展開することで示せます．グラフラプラシアンは任意の列和及び行和が $0$ です．また，無向グラフについても同様に書けます．

行列木定理

行列木定理の証明を追いながら，必要なステートメントを述べていきます．

定理（行列木定理）

無向グラフの全域木の個数はグラフラプラシアンの任意の余因子に一致する．

まず，次の補題は明らかに行列木定理の必要条件となります．

補題

グラフラプラシアンの任意の余因子は等しい．

証明　 $L$ の $(u,v)$ 余因子を $\Delta _ {uv}$ とする．任意の $u, v, w\in V$ に対し $\Delta _ {uv}=\Delta _ {uw}$ を示す．行方向についても同様に示せる．

$L$ の $u$ 行目を $\mathbf{e}^\top _ v$ で置き換えた行列を考えると， $u$ 行に関するLaplace展開から行列式は $\Delta _ {uv}$ に等しい．ここで $w$ 以外の列を $w$ 列に足すと， $L$ の任意の行和が $0$ であることから， $w$ 行は $\mathbf{e} _ u$ となる．ここで $w$ 列に関するLaplace展開からこの行列式は $\Delta _ {uw}$ に等しい．証明終

したがって，一般性を失わずに $u=v$ とします．ここでCauchy-Binetの公式を用います．

定理（Cauchy-Binet）

行列 $A:X_1\times X_2, B:X_2\times X_1$ について，
$\det(AB)=\sum_{Y:Y\subset X_2, |Y|=|X_1|}\det(A[X_1,Y])\det(B[Y,X_1])$
である．

以降の議論では今考えている無向グラフの各枝に対し任意に向き付けを行ったときの有向接続行列 $C$ を考えます．向き付けによりグラフラプラシアンは保たれるので問題ありません．任意に $u\in V$ を選ぶと， $(u,u)$ 余因子は次のように書けます：

$\begin{align} \Delta _ {uu} &= \det(L[V-u, E]L^\top[E, V-u])\\ &=\sum_{F:F\subset E, |F|=|V|-1}\det(C[V-u,F])\det(C^\top[F,V-u])\\ &=\sum_{F:F\subset E, |F|=|V|-1}\det(C[V-u,F])^2 \end{align}$

3行目でCauchy-Binetの公式を適用しました．ここで次の補題を用います．

補題

$F\subset E, |F|=|V|-1$ とする． $F$ が全域木をなす場合，またその場合に限り $\det(C[V-u,F])=\pm1$ となる．

証明　 $|F|=|V|-1$ 及び $L$ の完全単模性から，「 $F$ が無向閉路を含む $\Leftrightarrow C[V-u,F]$ が非正則」を示せばよい．ここで $C[V-u,F]$ が正則であることは $C[V,F]$ が列フルランクであることと同値である（ $\because$ 右向きは明らか．左向きは $C$ の任意の列和が $0$ から従う．）．さらに， $C[V,F]$ が列フルランクでないことは $F$ が無向閉路を含むことと同値である（ $\because$ 列の線形結合が $0$ となるとき，非零係数を持つ辺集合から閉路を構成できる．逆に閉路が存在する場合，対応する係数を $1$ または $-1$ から適切に選ぶと列の線形結合が $0$ となる．）．よって示された．証明終

これにより， $\Delta _ {uu} =\sum _ {F:F\subset E, |F|=|V|-1}\det(C[V-u,F]) ^ 2$ の和の中身は， $F$ が全域木をなす場合に $1$ ，なさない場合に $0$ となります．よってこの和は全域木の個数に一致します．以上により行列木定理が証明されました．

あとがき

いかがでしたでしょうか．線形代数と組合せ論を結びつける行列木定理の面白さを少しでも理解していただけていたら嬉しいです．私自身，急遽執筆を頼まれたときは少し焦りましたが，結果的には以前から気になっていた行列木定理について考察する良い機会となりました．途中で離脱された方も含め全ての読者，VRChat Advent Calender 2021を主催してくださったがとーしょこらさん，そしてこのような機会を提供してくれた某友人に最大限の感謝の意を表したいと思います．