行列式与矩阵树定理-526互联

定义

定义矩阵的行列式：

\[\det A=\sum_{\sigma}(-1)^{\tau(\sigma)}\prod_{i=1}^nA_{i\sigma_i} \]

\(\tau(\sigma)\) 是原排列的逆序对数。

性质：

若矩阵的某一行或某一列全为 \(0\)，则行列式为 \(0\)。
\(\det A = \det A^T\)。
交换 \(A\) 的两行或两列，行列式取反。
某一行或某一列乘上 \(k\)，行列式也乘上 \(k\)。
某一行（列）乘上 \(k\) 后加到另一行上，行列式不变。
行列式不为 \(0\) 则说明其行（列）向量线性无关，即可以作为系数矩阵解出线性方程组，反之亦然。

下证明第二条性质。其他性质显然。

为此，我们先研究 \(\tau(\sigma)\) 的性质。不难证明，交换任意元素后，\(\tau(\sigma)\) 改变奇偶性。

定义 \(c(\sigma)\) 为讲排列看成置换的循环数。考虑对于每个置换环，我们可以花环长减一次交换排序环。所以 \(n-c(\sigma)\) 次即可换为恒等排列（\(1,2,\dots,n\)）。即从恒等排列到此排列需要 \(n-c(\sigma)\) 次交换。

所以 \(n-c(\sigma)\) 与 \(\tau(\sigma)\) 奇偶性相同。

此时考察行列式造成贡献的条件：每一行取一个树，且取得数的列互不相同。所以我们可以直接沿用后面的贡献。只需要考虑 \((-1)^{\tau(\sigma)}\) 的影响。

可以发现，令新的排列（置换）为 \(\sigma'\)，则有：\(\sigma'(\sigma_i)=i\)。

那么 \(c(\sigma)=c(\sigma')\)，那么 \(\tau(\sigma)=\tau(\sigma')\)，于是两者贡献相等。

计算

对于一个除了主对角线均为零的矩阵，容易计算其行列式：即主对角线上的元素乘起来。

我们可以高斯消元计算之。对于模意义下，我们有如下方法：

使用辗转相除，我们需要将某一行下面的某一行置为 \(0\) 时，进行类似于欧几里得算法的操作。这样只会通过交换两行改变答案，而这是容易记录的。

可以证明，这样做的时间复杂度是 \(O(n^3+n^3\log p)\)。

矩阵树定理

描述

对于一个无向图，定义其度数矩阵 \(D\) 与邻接矩阵 \(A\) 为：

\(s(i,j)\) 为 \(i\) 与 \(j\) 之间的边数。

定义其基尔霍夫矩阵为 \(C=D-A\)。

则对于基尔霍夫矩阵划去第 \(r\) 行、列的余子式 \(C_r\)，有 \(\det C_r\) 等于原图的生成树个数。

证明

钦定 \(r\) 为生成树的根。

那么剩下 \(n-1\) 个点都需要连出一条到父亲的边。当且仅当这 \(n-1\) 条边不形成环的时候，连出的是一棵生成树。

考虑对环数容斥。我们用 \(n-1\) 阶排列描述连边：如果 \(\sigma_i=i\)，那么 \(i\) 任意连边（被认为是“根”）；否则连向 \(\sigma_i\)。

设 \(C_r'=-C_r\),得到生成树数量为：

\[\sum_{\sigma}(-1)^{c(\sigma)}\prod_{i=1}^{n-1}{C_r'}_{i\sigma_i} \]

注意到 \(i=\sigma_i\) 的部分不合法。但是不要紧，这里的系数是 \(-\deg i\)，正好抵消掉多余的部分。

我们已经得知 \(n-1-c(\sigma)\) 与 \(\tau(\sigma)\) 奇偶性相同。

所以原式等于

\[\sum_{\sigma}(-1)^{n-1-\tau(\sigma)}\prod_{i=1}^{n-1}{C_r'}_{i\sigma_i}\\ =\sum_{\sigma}(-1)^{n-1+\tau(\sigma)}\prod_{i=1}^{n-1}{C_r'}_{i\sigma_i}\\ \sum_{\sigma}(-1)^{\tau(\sigma)}\prod_{i=1}^{n-1}{C_r}_{i\sigma_i}\\ =\det C_r \]

证毕。

本质上，矩阵树定理求的就是所有生成树权值积的和。

考虑有根树的情形。若要求 \(r\) 为根，求根向生成树个数，我们不妨沿用上面的容斥，将 \(\deg i\) 的定义改为 \(i\) 的出度，然后计算 \(\deg C_r\)，证明和上面完全一
致。
如果要求叶向生成树个数，可以直接将边反向然后求根向生成树个数。但是这样太 Naive 了，将 \(\deg i\) 的定义改为 \(i\) 的入度，然后计算 \(\det C_r\) 即可。