行列木定理

$A$ の第 $k$ 列を $a_k$ とする。$AB$ の第 $j$ 列は $\sum_{k=1}^qB_{kj}\,a_k$ である。行列式は列について多重線形なので
$$ \det(AB)=\sum_{k_1,\dots,k_p}B_{k_11}B_{k_22}\cdots B_{k_pp}\,\det(a_{k_1},a_{k_2},\dots,a_{k_p}) $$
であり、和は $\{1,\dots,q\}$ の元の列 $(k_1,\dots,k_p)$ すべてにわたる。行列式は交代的なので、$k_j$ に重複がある項は $0$ である。とくに $p>q$ なら重複のない列はなく、$\det(AB)=0$ である。
$p\le q$ とし、重複のない列 $(k_1,\dots,k_p)$ を考える。その値の集合を $S=\{s_1< s_2<\dots< s_p\}$ とすると、$k_j=s_{\sigma(j)}$ となる $\{1,\dots,p\}$ の置換 $\sigma$ がただ 1 つある。逆に $S$ と $\sigma$ から重複のない列が 1 つ決まる。列の並べ替えで行列式は置換の符号倍になるので $\det(a_{k_1},\dots,a_{k_p})=\operatorname{sgn}(\sigma)\det A_{\bullet S}$ である。よって
$$ \det(AB)=\sum_S\det A_{\bullet S}\sum_{\sigma}\operatorname{sgn}(\sigma)\prod_{j=1}^pB_{s_{\sigma(j)}\,j} $$
である。$B_{S\bullet}$ の $(i,j)$ 成分は $B_{s_ij}$ なので、内側の和は $B_{S\bullet}$ の行列式の Leibniz の展開式 $\det M=\sum_\sigma\operatorname{sgn}(\sigma)\prod_jM_{\sigma(j)j}$ そのものであり、$\det B_{S\bullet}$ に等しい。$\square$

2 の証明．$(V,S)$ は $n$ 頂点で $n-1$ 本の辺をもつので、全域木 の記事の命題「木の判定」により、木でなければ連結でない。$(V,S)$ の連結成分のうち $x$ を含まないものの頂点集合を $C$ とする（$C\neq\emptyset$）。$C$ の頂点の行はすべて $(N_x)_{\bullet S}$ に残っている。$e\in S$ の列で、$C$ の行の和 $\sum_{v\in C}N_{ve}$ を考える。$e$ の両端がともに $C$ にあれば $1+(-1)=0$、両端とも $C$ になければ $0$ である。$C$ は $(V,S)$ の連結成分なので、$S$ の辺で一端だけが $C$ にあるものはない。よって $C$ の行の和は零ベクトルで、行が線形従属なので $\det(N_x)_{\bullet S}=0$ である。
1 の証明．$n$ についての帰納法で示す。$n=1$ なら $S=\emptyset$ で、$0$ 次の行列の行列式は $1$ である。$n\ge2$ とする。$T=(V,S)$ は木なので、Cayleyの公式 の記事の補題「葉の存在と葉の付け外し」の 1 により葉（次数 $1$ の頂点）を 2 つ以上もち、そのうち $x$ でないもの $v$ がある。$v$ に接続する $S$ の辺はただ 1 本 $e$ だけなので、$(N_x)_{\bullet S}$ の $v$ の行は、$e$ の列の成分 $N_{ve}=\pm1$ 以外が $0$ である。この行について余因子展開すると
$$ \det(N_x)_{\bullet S}=\pm\det M $$
となる。ここで $M$ は $(N_x)_{\bullet S}$ から $v$ の行と $e$ の列を除いた行列であり、それは木 $T-v$（頂点集合 $V\setminus\{v\}$、辺集合 $S\setminus\{e\}$。同補題の 2 により木である）の、同じ向きの接続行列から $x$ の行を除いたものに等しい。帰納法の仮定により $\det M=\pm1$ なので、$\det(N_x)_{\bullet S}=\pm1$ である。$\square$

段 1（$\tau(G)=\det L[x]$）．$L=NN^{\mathsf T}$ の第 $x$ 行と第 $x$ 列を除くと、左の因子から $x$ の行を、右の因子から $x$ の列を除くことになるので $L[x]=N_xN_x^{\mathsf T}$ である。thm-mtt-cauchy-binet を $A=N_x$（$(n-1)\times m$ 行列）、$B=N_x^{\mathsf T}$ に使う。$n-1\le m$ なら
$$ \det L[x]=\sum_{|S|=n-1}\det(N_x)_{\bullet S}\,\det\bigl((N_x)_{\bullet S}\bigr)^{\mathsf T}=\sum_{|S|=n-1}\bigl(\det(N_x)_{\bullet S}\bigr)^2 $$
であり、lem-mtt-incidence-minor により各項は $(V,S)$ が全域木なら $1$、そうでなければ $0$ である。全域木の辺はちょうど $n-1$ 本（全域木 の記事の系「全域木の辺の本数」）なので、和は $\tau(G)$ に等しい。$n-1>m$ なら $\det L[x]=0$ であり、辺が $n-1$ 本未満のグラフは全域木をもたないので $\tau(G)=0$ である。
段 2（余因子はすべて等しい）．$L$ の余因子行列（$(y,x)$ 成分が $(x,y)$ 余因子である行列）を $\operatorname{adj}L$ とすると、$L\operatorname{adj}L=\operatorname{adj}L\,L=(\det L)I=0$ である（$L\mathbf 1=0$ より $\det L=0$）。$G$ が連結でないとき、$\ker L$ は 2 次元以上（Laplacian行列 の定理「固有値 $0$ の重複度」）で $L$ の階数は $n-2$ 以下なので、$(n-1)$ 次の小行列式はすべて $0$ であり、余因子はすべて $0$ に等しい。$G$ が連結なとき、$\ker L$ は $\mathbf 1$ で張られる。$L\operatorname{adj}L=0$ から $\operatorname{adj}L$ の各列は $\ker L$ に属し、定数ベクトルである。また $\operatorname{adj}L\,L=0$ を転置すると、$L$ は対称なので $L(\operatorname{adj}L)^{\mathsf T}=0$ となり、$(\operatorname{adj}L)^{\mathsf T}$ の各列、すなわち $\operatorname{adj}L$ の各行も定数ベクトルである。各列も各行も定数なので、$\operatorname{adj}L$ の成分はすべて等しい。
段 3（固有値の積）．固有多項式を $\varphi(t)=\det(tI-L)=t(t-\mu_2)\cdots(t-\mu_n)$ とすると、$t$ の 1 次の係数は $\varphi'(0)=(-1)^{n-1}\mu_2\cdots\mu_n$ である。一方、$tI-L$ の第 $j$ 列は $t$ について 1 次式で、その微分は単位ベクトル $e_j$ である。行列式は列について多重線形なので、積の微分と同様に
$$ \varphi'(t)=\sum_{j=1}^n\det\bigl(\text{$tI-L$ の第 $j$ 列を $e_j$ に替えた行列}\bigr)=\sum_{j=1}^n\det\bigl((tI-L)[j]\bigr) $$
である（2 つ目の等号は第 $j$ 列についての余因子展開）。$t=0$ とおくと $\varphi'(0)=\sum_j\det(-L[j])=(-1)^{n-1}\sum_j\det L[j]$ であり、段 1 により各 $\det L[j]$ は $\tau(G)$ なので $\varphi'(0)=(-1)^{n-1}n\,\tau(G)$ である。2 つの表示を比べて $\mu_2\cdots\mu_n=n\,\tau(G)$ を得る。$\square$

$n=1$ なら全域木は辺のない $1$ 個で、$1^{-1}=1$ である。$n\ge2$ とする。$K_n$ の Laplacian 行列は $nI-J$（$J$ はすべての成分が $1$ の行列）なので、$L[x]=nI_{n-1}-J_{n-1}$ である。$J_{n-1}$ は $\mathbf 1$ を固有値 $n-1$ の固有ベクトルにもち、$\mathbf 1$ に直交する $(n-2)$ 次元の部分空間の上では $0$ である。よって $nI_{n-1}-J_{n-1}$ の固有値は $n-(n-1)=1$（重複度 $1$）と $n$（重複度 $n-2$）であり、thm-mtt-main により
$$ \tau(K_n)=\det(nI_{n-1}-J_{n-1})=1\cdot n^{n-2}=n^{n-2} $$
である。$\square$