正方行列を,要素が全部の行列とする (は定数).本稿ではの固有多項式を,組合せ論を使う方法で計算する.
証明に入る前にグラフの閉路と行列式の関係について復習する.
有限有向グラフの部分グラフで,各節点の入次数と出次数がであるものの集合をとかく.
グラフは,より平易に言えば,に含まれる互いに疎な閉路をいくつか集めてきてできるグラフである.
グラフの連結成分の数をとかく.また,に含まれないの節点の数をとかく.
また,グラフには枝重みが付けられているとし,の部分グラフに対してでに含まれる枝重みの積を表すとする.
以下のことが知られている.
固有多項式とグラフの閉路の関係
行列が枝重み付き有限有向グラフの隣接行列であるとき,の固有多項式は以下の通り書ける.
この事実の証明は例えば [1]を参照してほしい.
ここでは,定理2の証明は書かず具体例を紹介するにとどめておく.
定理1の証明.
定理2を使うと,計算したい行列式は,
と書ける.ただし,は節点の完全有向グラフに,全ての節点へ自己ループを加えてできる有向グラフを表す(下図左を見よ.)
集合の部分集合を,枝のない部分グラフと,自己ループ個だけからなる部分グラフを集めた集合と定義する.例えば,のときは下図右のようになる.
左:.枝は双方向に張られているとする.右:の元.
定理1の右辺は,この集合にわたる和として
とかける.
よって,我々が示すべきことは,集合にわたる重みの和がになること,すなわち
である.
これを示すには,枝の数を変えずに,閉路の数をだけ変化させるような対合
を作ればよい.
グラフの節点をとラベル付けする.
とする.グラフに含まれる節点の中で,ラベルが最小の節点 (とする)と二番目に小さい節点 (とする)に注目する.
- とが同じサイクルに含まれる場合,サイクルを二つに分離する.
つまり,というサイクルを,という二つのサイクルに分ける. - とが違うサイクルに含まれる場合,サイクルを一つに融合する.
つまり,という二つのサイクルをという一つのサイクルにする.
それ以外の部分は変化させない.
この操作をとすれば,これは所望の対合である.
対合のようす
(証明終わり.)