行列木定理とCayleyの定理

$\Delta_{11}=\Delta_{12}$ を示す。他の余因子が等しいことも同様に示せる。

わかりやすさのために $n=5$ の場合で示す。一般の $n$ でも同様。

$$\Delta_{11}=\det\begin{pmatrix}d_2&a_{23}&a_{24}&a_{25}\\a_{23}&d_3&a_{34}&a_{35}\\a_{24}&a_{34}&d_4&a_{45}\\a_{25}&a_{35}&a_{45}&d_5\end{pmatrix}$$ である。ただし，$d_i$ は頂点 $i$ の次数である。1列目に1列目以外の各列を加えることで， $$\Delta_{11}=\det\begin{pmatrix}-a_{12}&a_{23}&a_{24}&a_{25}\\-a_{13}&d_3&a_{34}&a_{35}\\-a_{14}&a_{34}&d_4&a_{45}\\-a_{15}&a_{35}&a_{45}&d_5\end{pmatrix}$$ となる（もとのラプラシアン行列で各行の和が $0$ であることを使った） これはまさに符号まで含めて $\Delta_{12}$ である。

$G$ の点枝接続行列を $E$ とする。ただし，$i<j$ なる頂点 $i,j$ 間に枝があるとき，$i$ 側の要素は $1$，$j$ 側の要素は $-1$ とする。 例えば，図の例だと $$E=\begin{pmatrix}1&1&1&0\\-1&0&0&1\\0&-1&0&0\\0&0&-1&-1\end{pmatrix}$$ である。行数＝$G$ の頂点数，列数＝$G$ の枝数となる行列である。例えば $E$ の3行目より，頂点1と4を結ぶ枝（$e_3$）があることがわかる。$E$ とラプラシアン $L$ の定義より，$L=EE^{\top}$ となる。よって，$E$ の1行目を除いた行列を $E'$ とすると， $$\Delta_{11}=\det E'E'^{\top}$$ となる。右辺にビネ・コーシーの定理を使うと， $$\Delta_{11}=\displaystyle\sum_{S}\det(E'[S])\det(E'^{\top}[S])=\displaystyle\sum_{S}\det(E'[S])^2$$ となる。ただし，$S$ は枝のラベル $\{1,2,3,...,n\}$ から $|V|-1$ 個（$|V|$ は $G$ の頂点数）選んだ集合全体を動く。

つまり，$S$ により $G$ の枝が $|V|-1$ 個決まるが，

• これらが全域木をなさない，つまり閉路を含むとき $\det(E'(S))=0$ である。 実際，頂点1を含まない閉路があるときは，$$E'(S)=\begin{pmatrix}1&1&0\\-1&0&1\\0&-1&-1\end{pmatrix}$$ のように，行和が $0$ ベクトルになるので行列式が $0$。頂点1を含む閉路があるときは，頂点1以外に孤立点があり，$E'(S)$ のその行はすべて $0$ なので行列式は $0$
• これらが全域木をなすとき，$\det(E'(S))=\pm 1$ である。 実際，$$E'(S)=\begin{pmatrix}-1&0&1\\0&0&-1\\0&-1&0\end{pmatrix}$$ などとなるが，置換による行列式の定義を考えたとき，$0$ を選ばない置換がただ1つになる。もう少し詳しく言うと「木は次数1の頂点を2つ以上含む（頂点1以外で次数1のものが存在する）」ことと「木から次数1の頂点を1つ除いても木のまま」であることから，$0$ を選ばない置換を構成しようとするとただ1つになる。

よって，$\Delta_{11}$ は $G$ の全域木の個数と等しい。

わかりやすさのために $n=5$ で計算する。一般の $n$ でも同様。

頂点数 $5$ の完全グラフに行列木定理を使うと

$$T(5)=\det\begin{pmatrix}4&-1&-1&-1\\-1&4&-1&-1\\-1&-1&4&-1\\-1&-1&-1&4\end{pmatrix}$$

1行目以外の各行から1行目を引くことで， $$T(5)=\det\begin{pmatrix}4&-1&-1&-1\\-5&5&0&0\\-5&0&5&0\\-5&0&0&5\end{pmatrix}$$

1列目以外の各列を1列目に加えることで， $$T(5)=\det\begin{pmatrix}1&-1&-1&-1\\0&5&0&0\\0&0&5&0\\0&0&0&5\end{pmatrix}$$

上三角行列の行列式は対角成分の積なので $T(5)=5^3$ と等しい。