Cauchy-Binetの公式による行列木定理の証明
本記事は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から構成し直して作成したものです.そのため不正確な点や行間が広すぎる点などあるかもしれませんので,コメント欄でご意見をお寄せいただければ幸いです.
表記
行列の行集合が,列集合がであるときと記します.のに対応する小行列をと記します.要素数の集合について,意味が明らかな場合に波括弧を省略します.
行列とグラフ
本章では行列木定理を証明する準備として,接続行列の性質について議論します.
接続行列
今,自己ループを持たない有向グラフを考えます.ただしには適当な順序が入っているものとします.このときの接続行列とは行列で,
となるものです.
接続行列の小行列式
任意の自己ループを持たない有向グラフに対する接続行列は完全単模です.ここで完全単模行列とは,任意の小行列式がのいずれかである行列です.以下,接続行列が完全単模であることを証明します.小行列の各列に含まれるはそれぞれ高々個であることに注意します.
接続行列は完全単模.
証明 小行列の次数に関する帰納法で示す.次数の場合成立する.次数の場合,任意の列(これをとする)に注目すると次の3つの場合に分けられる:
列にの両方が含まれる場合
が含まれる行をそれぞれとする.このとき行を行に足して列に関するLaplace展開を考えると,次数の小行列式と符号を除いて等しくなる.また,この小行列は,元のグラフから間の枝を削除しを縮約したグラフにおける小行列に一致する.帰納法の仮定からこれはのいずれかである.
列にの一方のみが含まれる場合
列に関するLaplace展開を考えると次数の小行列式と符号を除いて等しくなるが,帰納法の仮定からこれはのいずれかである.
列にのどちらも含まれない場合
小行列式はとなる.
よって示された.証明終
グラフラプラシアン
グラフラプラシアンとは,自己ループを持たない有向グラフに対し接続行列を用いてで定義される行列です.グラフラプラシアンの要素は次のように書けます:
このことは,具体的に積を展開することで示せます.グラフラプラシアンは任意の列和及び行和がです.また,無向グラフについても同様に書けます.
行列木定理
行列木定理の証明を追いながら,必要なステートメントを述べていきます.
定理(行列木定理)
無向グラフの全域木の個数はグラフラプラシアンの任意の余因子に一致する.
まず,次の補題は明らかに行列木定理の必要条件となります.
グラフラプラシアンの任意の余因子は等しい.
証明 の余因子をとする.任意のに対しを示す.行方向についても同様に示せる.
の行目をで置き換えた行列を考えると,行に関するLaplace展開から行列式はに等しい.ここで以外の列を列に足すと,の任意の行和がであることから,行はとなる.ここで列に関するLaplace展開からこの行列式はに等しい.証明終
したがって,一般性を失わずにとします.ここでCauchy-Binetの公式を用います.
定理(Cauchy-Binet)
行列について,
である.
以降の議論では今考えている無向グラフの各枝に対し任意に向き付けを行ったときの有向接続行列を考えます.向き付けによりグラフラプラシアンは保たれるので問題ありません.任意にを選ぶと,余因子は次のように書けます:
3行目でCauchy-Binetの公式を適用しました.ここで次の補題を用います.
とする.が全域木をなす場合,またその場合に限りとなる.
証明 及びの完全単模性から,「が無向閉路を含むが非正則」を示せばよい.ここでが正則であることはが列フルランクであることと同値である(右向きは明らか.左向きはの任意の列和がから従う.).さらに,が列フルランクでないことはが無向閉路を含むことと同値である(列の線形結合がとなるとき,非零係数を持つ辺集合から閉路を構成できる.逆に閉路が存在する場合,対応する係数をまたはから適切に選ぶと列の線形結合がとなる.).よって示された.証明終
これにより,の和の中身は,が全域木をなす場合に,なさない場合にとなります.よってこの和は全域木の個数に一致します.以上により行列木定理が証明されました.
あとがき
いかがでしたでしょうか.線形代数と組合せ論を結びつける行列木定理の面白さを少しでも理解していただけていたら嬉しいです.私自身,急遽執筆を頼まれたときは少し焦りましたが,結果的には以前から気になっていた行列木定理について考察する良い機会となりました.途中で離脱された方も含め全ての読者,VRChat Advent Calender 2021を主催してくださったがとーしょこらさん,そしてこのような機会を提供してくれた某友人に最大限の感謝の意を表したいと思います.