Matrix Tree

$$
t(G) = \det L(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}.
$$

也就是说，无向图的 Laplace 矩阵所有 $n-1$ 阶主子式都相等，且都等于图的生成树的个数．

$$
t(G) = \frac{1}{n}\lambda_1\lambda_2\cdots\lambda_{n-1}.
$$

$$
t^\mathrm{root}(G,k) = \det L^\mathrm{out}(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}.
$$

也就是说，有向图的出度 Laplace 矩阵删去第 $k$ 行第 $k$ 列得到的主子式等于以 $k$ 为根的根向树形图的个数．

$$
t^\mathrm{leaf}(G,k) = \det L^\mathrm{in}(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}.
$$

也就是说，有向图的入度 Laplace 矩阵删去第 $k$ 行第 $k$ 列得到的主子式等于以 $k$ 为根的叶向树形图的个数．

$$
\det(AB)=\sum_{S\subset[m];~|S|=n}\det A_{[n],S}\det B_{S,[n]},
$$

这里求和记号的含义是，$S$ 取遍所有 $[m]$ 中大小为 $n$ 的子集．如果 $n>m$，必然有 $\det(AB)=0$．

$$
\det(C)=\sum_{\sigma\in S_n}\mathrm{sgn}(\sigma)\prod_{i\in[n]}C_{i,\sigma(i)},
$$

其中，$S_n$ 为 $[n]$ 上的置换群，而 $\mathrm{sgn}(\sigma)$ 为置换 $\sigma$ 的符号（当逆序数为偶数时，它等于 $1$；当逆序数为奇数时，它等于 $-1$）．

在理解行列式的组合意义后，可以利用如下的组合模型证明 Cauchy–Binet 公式．对于 $n\times m$ 阶矩阵 $A$ 和 $m\times n$ 阶矩阵 $B$，建立有向无环图 $G=(V,E)$．其中，顶点集为 $V=L\cup D\cup R$，这里，$L=\{l_i=(1,i):i\in[n]\}$，$D=\{d_i=(2,i):i\in[m]\}$ 和 $R=\{r_i=(3,i):i\in[n]\}$；而有向边集为 $E=E_L\cup E_R$，其中，$E_L=\{(l_i,d_j):i\in[n],j\in[m]\}$ 和 $E_R=\{(d_j,r_i):j\in[m],i\in[n]\}$，分别赋以边权 $w(l_i,d_j)=A_{i,j}$ 和 $w(d_j,r_i)=B_{j,i}$．同样考虑自 $L$ 经 $D$ 到 $R$ 的路径组（路径间两两不共用顶点），按照权重计数，并用偶数交点的路径组数减去奇数交点的路径组数．下面说明，Cauchy–Binet 公式的左右两侧分别用两种方式计算了这一数目．

对于左侧，基于上面描述的图 $G$，建立新图 $G'$，其顶点集为 $V'=L\cup R$，边集为 $E'=\{(l_i,r_j):i,j\in[n]\}$，且对于边 $(l_i,r_j)$ 赋以边权 $\sum_{k\in[m]}A_{i,k}B_{k,j}$，即在原图 $G$ 中自 $l_i$ 到 $r_j$ 的简单路径的加权计数．这一边权正是 $(AB)_{i,j}$．这相当于把上述的三层图简化成了两层图．但是，两层图 $G'$ 中的路径组（按权重计）并非和三层图 $G$ 中的路径组一一对应．由于在两层图中，每个路径都对应三层图中若干条简单路径，在对两层图进行路径组的计数时，需要将权重相乘，这相当于对它们对应的三层图中的路径集合两两组合，这必然会造成出现共用中间经停点的情形．但是，这些共用中间经停点的路径对并不会对最后的答案有贡献，因为对于 $i_1< i_2$ 和 $j_1< j_2$ 和任意中间点 $d$，都存在两种简单路径对 $(l_{i_1}\rightarrow d\rightarrow r_{j_1}, l_{i_2}\rightarrow d\rightarrow r_{j_2})$ 和 $(l_{i_1}\rightarrow d\rightarrow r_{j_2}, l_{i_2}\rightarrow d\rightarrow r_{j_1})$，但是这两组路径在三层图中的交点数目奇偶性必然相反，因为如果只看起点和终点，两组路径交换了终点．所以，这些共用中间经停点的路径在简化后的两层图计数时，贡献会两两抵消．对于剩下的情形，如果给定两条路径的起点和终点，那么无论中间的点如何如何选取（只要不选择同一个点），则这两条路径的交点个数的奇偶性不会变．故而，$G'$ 中每一个路径组对应的所有原图 $G$ 中的路径组都具有相同的奇偶性．因而，$\det(AB)$ 提供了前文所述路径组数差值的一种计算方式．

对于右侧，它相当于枚举了所有可能的中间点的组合．给定任何中间点集合 $S\subset D=[m]$ 且 $|S|=n$，分别考虑自 $L$ 到 $S$ 的路径组和自 $S$ 到 $R$ 的路径组，可以连接得到 $L$ 到 $R$ 的路径组，且前两个路径组对应的置换的复合就等于之后的路径组对应的置换，故而前两个路径的奇偶性的乘积等于之后的路径组的奇偶性．所以，所有中间点集合为 $S$ 的路径组的计数的差值正等于自 $L$ 到 $S$ 的路径组的计数的差值和自 $S$ 到 $R$ 的路径组的计数的差值的乘积．对所有可能的 $S$ 求和，即得到右式，故而它正是前文所述路径组数差值．

$$
\mathrm{rank}(AB)\le \min\{\mathrm{rank}(A),\mathrm{rank}(B)\}\le m< n.
$$

当 $m=n$ 时，Cauchy–Binet 公式就是，方阵的积的行列式等于方阵的行列式的积．

当 $m>n$ 时，注意到

$$
x^{m-n}\det(xI_n+AB) = \det(xI_m+BA).
$$

又已知结论，$\det(xI_n+C)$ 中 $x^{n-k}$ 的系数是 $C$ 的所有 $k$ 阶主子式的和．故而，比较上式中两侧系数，有

$$
\det(AB) = \sum_{S\subset[m];~|S|=n}\det(BA)_{S,S} = \sum_{S\subset[m];~|S|=n}\det(B)_{S,[n]}\det(A)_{[n],S} = \sum_{S\subset[m];~|S|=n}\det(A)_{[n],S}\det(B)_{S,[n]}.
$$

这里，第二个等号用到了 $m=n$ 的情形的结论．

$$
\det(M^\mathrm{out}_{S,W})\det(M^\mathrm{out}_{S,W}-M^\mathrm{in}_{S,W})
$$

不为零．而且，该式当不为零时，必然等于 $\prod_{e\in S}w(e)$，记作 $w(T)$．

首先分析两个因子等于零的条件．前一个因子 $\det(M^\mathrm{out}_{S,W})$ 每行至多一个不为零的数字，即 $+1$．如果有任何一行全为零，则该行列式必然为零．所以，该行列式不为零，当且仅当每行恰好一个 $+1$，亦即 $W$ 中每个点都恰好是 $S$ 中一条边的起点，且没有两个边共用同一个起点．已知 $T$ 成为以 $V\setminus W$ 为根的根向森林，一个必要条件就是除了根之外，所有顶点有且只有一个父节点，这必然使得该因子不为零；但反过来并不一定成立，因为不能保证不存在环，所以还需要考察第二个因子．注意，$S$ 的终点未必在 $W$ 中．

假定前一个因子不为零，则此时子图 $T$ 成为根向森林，当且仅当 $T$ 中没有环．此时，后一项 $\det(M^\mathrm{out}_{S,W}-M^\mathrm{in}_{S,W})$ 每行中都有一个 $+1$，但可能有一个或零个 $-1$．对于终点也在 $W$ 中的边，如果 $e_i$ 的终点是 $e_j$ 的起点，则将 $e_i$ 对应的行加上 $e_j$ 对应的行，可以消去 $e_i$ 行中的 $-1$．可以想象，此时该行描述的是 $e_i$ 和 $e_j$ 首尾相接的简单路径．如果该行出现了新的 $-1$，那么说明 $e_j$ 的终点也在 $W$ 内，$-1$ 的位置就是 $e_j$ 的终点，于事，可以继续找到以 $e_j$ 的终点为起点的边，再次加到该行上．这样的边总是存在的，因为上一段论述说明，$W$ 中每个点都恰好是 $S$ 中一条边的起点．这一过程一直持续到该行不在出现 $-1$ 为止，相当于不断添加新的边到简单路径 $e_i\rightarrow e_j\rightarrow \cdots\rightarrow e_k$ 中．此时，如果该行只剩下一个 $+1$，那么说明 $e_k$ 的终点不在所选顶点 $W$ 中，过程终止；如果上次加入的边恰巧抵消了现有的 $+1$，即该行只剩下零，那么说明新边 $e_k$ 的终点就是最开始的边 $e_i$ 的起点，即出现了一个环．所以，没有环的充要条件是该一行列式经上述操作可以变形成每行都恰好只有一个 $+1$ 的形式．由于这些 $+1$ 的位置是各行对应边的起点，此时得到的矩阵实际上就是 $\det(M^\mathrm{out}_{S,W})$．

综上所述，如果 $T$ 不是根向森林，则要么 $\det(M^\mathrm{out}_{S,W})=0$，要么 $\det(M^\mathrm{out}_{S,W}-M^\mathrm{in}_{S,W})=0$；否则，两者均不为零，且乘积等于 $\left(\det(M^\mathrm{out}_{S,W})\right)^2=1$．

$$
\sum_{T\in\mathcal T^\mathrm{root}(G,k)}w(T)=\det L^\mathrm{out}(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}.
$$

这里，$\mathcal T^\mathrm{root}(G,k)$ 是 $G$ 的以 $k$ 为根的根向树形图的集合．

$$
\det L^\mathrm{out}(G)_{W,W} = \sum_{S\subset[m];~|S|=n-1}\det(M^\mathrm{out}_{S,W})\det(M^\mathrm{out}_{S,W}-M^\mathrm{in}_{S,W}).
$$

遍历所有的 $S$，由引理 2，当且仅当 $T=(V,S)$ 构成一个以 $V\setminus W=\{k\}$ 为根的根向森林时，亦即 $T$ 是一个以 $k$ 为根的根向树形图时，右侧累加一个 $w(T)$．

$$
\sum_{T\in\mathcal T(G)}w(T) = \det L(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}.
$$

这里，$\mathcal T(G)$ 是 $G$ 的生成树的集合．这也说明，$L(G)$ 的所有 $(n-1)$ 阶主子式都相等．

$$
\sum_{T\in\mathcal T(G)}w(T) = \sum_{T\in\mathcal T^\mathrm{root}(G',k)}w(T) = \det L^\mathrm{out}(G')_{[n]\setminus\{k\},[n]\setminus\{k\}} = \det L(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}.
$$

此处用到了结论 $L^\mathrm{out}(G')=L(G)$，这容易直接验证．

$$
\chi(x_1,\cdots,x_n)=\det(\mathrm{diag}(x_1,\cdots,x_n)-L^\mathrm{out}(G)).
$$

这里，$\mathrm{diag}(x_1,\cdots,x_n)$ 是指以 $x_1,\cdots,x_n$ 为对角线元素的对角矩阵．那么，

$$
(-1)^{n-r}[x_{k_1},\cdots,x_{k_r}]\chi(x_1,\cdots,x_n)
$$

就等于 $G$ 的以 $\{k_1,\cdots,k_r\}$ 为根的根向森林的（带权的）计数．

$$
\det L^\mathrm{out}(G)_{W,W} = \sum_{S\subset[m];~|S|=n-r}\det(M^\mathrm{out}_{S,W})\det(M^\mathrm{out}_{S,W}-M^\mathrm{in}_{S,W}).
$$

遍历所有的 $S$，由引理 2，当且仅当 $T=(V,S)$ 构成一个以 $V\setminus W=\{k_1,\cdots,k_r\}$ 为根的根向森林时，右侧累加一个 $w(T)$．

$$
(-1)^{n-k}[x^k]P(x).
$$

$$
\sum_{T\in\mathcal T_k(G)}w(T)Q(T) = (-1)^{n-k}[x^k]P(x).
$$

这里，$Q(T)$ 为森林 $T$ 中每个连通分量的顶点数目的乘积．特别地，当 $k=1$ 时，有 $Q(T)=n$，故而

$$
n\sum_{T\in\mathcal T(G)}w(T) = \lambda_1\lambda_2\cdots\lambda_{n-1}.
$$

$$
L(G) = \left(\begin{matrix} n-1 & -1 & \cdots & -1 \\ -1 & n-1 & \cdots & -1 \\ \vdots & \vdots & \ddots & \vdots \\ -1 & -1 & \cdots & n-1  \end{matrix}\right)_{n\times n}.
$$

计算它的任意主子式，有

$$
\det(nI_{n-1}-{\bf 1}{\bf 1}^T) = n^{n-1}\det(I_{n-1}-n^{-1}{\bf 1}{\bf 1}^T) = n^{n-1}(1-n^{-1}{\bf 1}^T{\bf 1}) = n^{n-1}(1-(n-1)/n) = n^{n-2}.
$$

应用定理 1 即得到结论．

$$
\mathrm{ec}(G) = t^\mathrm{root}(G,k)\prod_{v\in V}(\deg (v) - 1)!.
$$

这也说明，对欧拉图 $G$ 的任意两个节点 $k, k'$，都有 $t^\mathrm{root}(G,k)=t^\mathrm{root}(G,k')$．

$$
\mathrm{deg}(k)\mathrm{ec}(G) = t^\mathrm{root}(G,k)\deg(k)!\prod_{v\neq k}(\deg (v) - 1)!.
$$

这一计数的组合含义对应的构造如下．对于起点为 $k$ 的欧拉回路，根据回路中每条边的出现顺序，可以构造出

-   一个以 $k$ 为根的根向树形图，由所有非根顶点处的最后一条出边组成，即 $t^\mathrm{root}(G,k)$，
-   根 $k$ 处所有出边的排列顺序，即 $\mathrm{deg}(k)!$，和
-   非根顶点 $v\neq k$ 处除去最后一条出边之外的其他所有出边的排列顺序，即 $(\mathrm{deg}(v)-1)!$．

下面说明，这样的构造得到的映射是双射．

一方面，给定欧拉回路，要证明所有非根顶点处的最后一条出边组成了一个根向树形图．根据构造，树中每个非根顶点的确只有一条出边，所以只需要证明这些出边不会成环．注意到，如果将所有顶点根据它在欧拉回路最后一次出现的顺序排序，那么非根顶点的最后一次出边必然指向顺序严格更靠后的顶点．如果存在环，那么环中就有一个顺序最靠后的顶点，因为它在环中，所以它指向了一个顺序并不靠后的点，这与上文矛盾．所以，非根顶点的最后一次出边必然构成根向树形图．

另一方面，给定任意根向树形图和其余出边的排列顺序，可以复原出一条欧拉回路，使得该欧拉回路经上述构造后可以得到给定的根向树形图和其余出边的排列顺序．对此，只需要从根 $k$ 出发，每当到达一个顶点时，都根据给定的该顶点的出边排列顺序，选择顺序最靠前的、尚未经过的出边作为欧拉回路中本次的出边；如果该顶点处的排列中所有出边都已经经过了，就选择根向树形图中该顶点的出边作为欧拉回路中本次的出边．因为图是欧拉图，每个顶点的入度都等于出度，所以，这一过程不会在非根顶点处终止，即所得路径的确是回路．要证明所得路径是合法的欧拉回路，只需要证明这一过程能够遍历所有边就可以．

如果不能，则必然有某个顶点 $v$ 的某个出边没有遍历到．考察顶点 $v$．顶点 $v$ 不能是根，因为最后会终止在根，如果根仍有出边剩余，这与过程终止矛盾．所以，$v$ 必然不是根．根据前文描述的过程，只要非根顶点 $v$ 有任何出边剩余，那么非根顶点在树中的出边 $e$ 必然剩余．记 $e=(v,u)$．因为 $u$ 的某个入边没有遍历到，根据 $u$ 的出度等于入度，必然有 $u$ 的某条出边没有遍历到．然后，可以类似地考察顶点 $u$．这些推理将考察的顶点从 $v$ 移动到了 $u$，即沿着根向树形图向树的根移动了一步．可以归纳地证明，此时必有根 $k$ 的某个出边没有遍历到．前文已经说明这不可能，故得到矛盾．这说明，上一段所得路径的确是合法的欧拉回路．

可以验证这些映射都是单射，则必然同为双射．原命题得证．

struct matrix {
  static constexpr int MAXN = 20;
  int n, m;
  double mat[MAXN][MAXN];

  matrix() { memset(mat, 0, sizeof(mat)); }

  void print() {
    cout << "MATRIX " << n << " " << m << endl;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cout << mat[i][j] << "\t";
      }
      cout << endl;
    }
  }

  void random(int n) {
    this->n = n;
    this->m = n;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) mat[i][j] = rand() % 100;
  }

  void initSquare() {
    this->n = 4;
    this->m = 4;
    memset(mat, 0, sizeof(mat));
    mat[0][1] = mat[0][3] = 1;
    mat[1][0] = mat[1][2] = 1;
    mat[2][1] = mat[2][3] = 1;
    mat[3][0] = mat[3][2] = 1;
    mat[0][0] = mat[1][1] = mat[2][2] = mat[3][3] = -2;
    this->n--;  // 去一行
    this->m--;  // 去一列
  }

  double gauss() {
    double ans = 1;
    for (int i = 0; i < n; i++) {
      int sid = -1;
      for (int j = i; j < n; j++)
        if (abs(mat[j][i]) > eps) {
          sid = j;
          break;
        }
      if (sid == -1) continue;
      if (sid != i) {
        for (int j = 0; j < n; j++) {
          swap(mat[sid][j], mat[i][j]);
          ans = -ans;
        }
      }
      for (int j = i + 1; j < n; j++) {
        double ratio = mat[j][i] / mat[i][i];
        for (int k = 0; k < n; k++) {
          mat[j][k] -= mat[i][k] * ratio;
        }
      }
    }
    for (int i = 0; i < n; i++) ans *= mat[i][i];
    return abs(ans);
  }
};

int main() {
  srand(1);
  matrix T;
  // T.random(2);
  T.initSquare();
  T.print();
  double ans = T.gauss();
  T.print();
  cout << ans << endl;
}
```

$$
L_n = \begin{bmatrix}
n&  -1&  -1&  -1&  \cdots&  -1&  -1\\
-1&  3&  -1&  0&  \cdots&  0&  -1\\
-1&  -1&  3&  -1&  \cdots&  0&  0\\
-1&  0&  -1&  3&  \cdots&  0&  0\\
\vdots&  \vdots&  \vdots&  \vdots&  \ddots&  \vdots&  \vdots\\
-1&  0&  0&  0&  \cdots&  3&  -1\\
-1&  -1&  0&  0&  \cdots&  -1&  3\\
\end{bmatrix}_{n+1}
$$

求出它的 $n$ 阶子式的行列式即可，剩下的只有高精度计算了．

**解** 推导递推式后利用矩阵快速幂即可求得．

推导递推式的过程：

注意到 $L_n$ 删掉第 1 行第 1 列以后得到的矩阵很有规律，因此其实就是在求矩阵

$$
M_n = \begin{bmatrix}
3&  -1&  0&  \cdots&  0&  -1\\
-1&  3&  -1&  \cdots&  0&  0\\
0&  -1&  3&  \cdots&  0&  0\\
\vdots&  \vdots&  \vdots&  \ddots&  \vdots&  \vdots\\
0&  0&  0&  \cdots&  3&  -1\\
-1&  0&  0&  \cdots&  -1&  3\\
\end{bmatrix}_{n}
$$

的行列式．对 $M_n$ 的行列式按第一列展开，得到

$$
\det M_n = 3\det \begin{bmatrix}
3&  -1&  \cdots&  0&  0\\
-1&  3&  \cdots&  0&  0\\
\vdots&  \vdots&  \ddots&  \vdots&  \vdots\\
0&  0&  \cdots&  3&  -1\\
0&  0&  \cdots&  -1&  3\\
\end{bmatrix}_{n-1} + \det\begin{bmatrix}
-1&  0&  \cdots&  0&  -1\\
-1&  3&  \cdots&  0&  0\\
\vdots&  \vdots&  \ddots&  \vdots&  \vdots\\
0&  0&  \cdots&  3&  -1\\
0&  0&  \cdots&  -1&  3\\
\end{bmatrix}_{n-1} + (-1)^n \det\begin{bmatrix}
-1&  0&  \cdots&  0&  -1\\
3&  -1&  \cdots&  0&  0\\
-1&  3&  \cdots&  0&  0\\
\vdots&  \vdots&  \ddots&  \vdots&  \vdots\\
0&  0&  \cdots&  3&  -1\\
\end{bmatrix}_{n-1}
$$

上述三个矩阵的行列式记为 $d_{n-1}, a_{n-1}, b_{n-1}$．  
注意到 $d_n$ 是三对角行列式，采用类似的展开的方法可以得到 $d_n$ 具有递推公式 $d_n=3d_{n-1}-d_{n-2}$．类似地，采用展开的方法可以得到 $a_{n-1}=-d_{n-2}-1$，以及 $(-1)^n b_{n-1}=-d_{n-2}-1$．  
将这些递推公式代入上式，得到：

$$
\det M_n = 3d_{n-1}-2d_{n-2}-2
$$

$$
d_n = 3d_{n-1}-d_{n-2}
$$

于是猜测 $\det M_n$ 也是非齐次的二阶线性递推．采用待定系数法可以得到最终的递推公式为

$$
\det M_n = 3\det M_{n-1} - \det M_{n-2} + 2
$$

改写成 $(\det M_n+2) = 3(\det M_{n-1}+2) - (\det M_{n-2} + 2)$ 后，采用矩阵快速幂即可求出答案．

将行列式的项写成 $w_ix+1$，最后答案是行列式的一次项系数，因为答案实际上是钦定一条边之后的生成树个数 $\times$ 这条边的边权之和，那么被乘上一次项系数的边就是被钦定的边．此时可以把高于一次的项忽略掉，复杂度 $O(n^3)$．

[「北京省选集训 2019」生成树计数](https://www.luogu.com.cn/problem/P5296) 是较为一般化的情况：计算生成树权值之和的 $k$ 次方之和，用类似方法构造行列式的项即可，具体见洛谷题解．