LGV 引理 & 矩阵树定理 & BEST 定理学习笔记

符号规定

$P(n)$ 为所有 $n$ 阶排列构成的集合；
$\sigma(p)$ 为排列 $p$ 的逆序对个数；
$p^{-1}$ 为排列 $p$ 的逆排列，即满足 $p^{-1}_{p_i}=i$ ；
$A^T$ 为矩阵 $A$ 的转置矩阵；
$[n]$ 为集合 $\{1,2,3,\dots,n\}$ ；
$\binom{[n]}{m}$ 为从 $\{1,2,3,\dots,n\}$ 中所有大小为 $m$ 的子集构成的集合；

行列式

对于一个 $n\times n$ 的方阵 $A$ ，定义其行列式：

|A|=\sum\limits_{p\in P(n)} (-1)^{\sigma(p)}\prod\limits_{i=1}^n A_{i,p_i}

非方阵的行列式为 $0$ 。

几何意义：线性变换后”体积“的变化量，即原先 $1$ 单位变为 $|A|$ 单位。

行列式的基本性质 & 高斯消元求解

若 $A$ 非满秩矩阵，则 $|A|=0$ ；

证明

考虑行列式的几何意义，若 $A$ 非满秩，则变换后的基向量会共线，则”体积“显然为 $0$ 。
$|A^T|=|A|$ ；
对于 $A$ ，将其中的某一行同时乘常数 $k$ ，则 $|A|$ 也会乘上 $k$ ；
对于 $A$ ，交换其中的某两行，则 $|A|$ 会变为 $-|A|$ ；

证明

相当于证明交换排列 $p$ 中任意两个不同的数会改变排列逆序对个数的奇偶性。

不难发现交换 $p_i$ 和 $p_{i+1}$ 是成立的，而交换 $p_i$ 和 $p_j$ （ $i<j$ ）可以看作先将 $p_i$ 一个一个往右交换到 $p_{j}$ 的右边，再将 $p_j$ 一个一个往左交换到 $p_i$ 原来的位置。

第一步交换总共需要 $j-i$ 次，第二步则需要 $j-i-1$ 次，而 $2(j-i)-1$ 是一个奇数，所以整个过程逆序对个数奇偶性一定会改变。
对于 $A$ ，将一行乘上常数 $k$ 再整体加到另一行，则 $|A|$ 不变；

证明

记新的方阵为 $A'$ ，假设是将第 $i$ 行加到第 $j$ 行。

考虑乘法分配律，将被加的行拆开，则 $|A'|=|A|+k|B|$ ，其中 $B$ 的第 $j$ 行和第 $i$ 行相同，则显然 $B$ 非满秩， $|B|=0$ ，得证。

那么根据这些基本性质，可以使用高斯消元将方阵的下半消成全 $0$ ，即 $\forall j<i,A_{i,j}=0$ 。

这样显然 $|A|=\prod\limits_{i=1}^n A_{i,i}$ ，因为其它排列必然会存在某个 $i$ 使得 $A_{i,p_i}=0$ 。

当然将上半消成全 $0$ 也是可以的。

交换两行的时候别忘了变号，时间复杂度 $O(n^3)$ 。

参考代码

inline int gauss(int n)
{
	int res=1;
	for(int i=1;i<=n;i++)
	{
		if(a[i][i]==0)
		{
			bool f=false;
			for(int j=i+1;j<=n;j++)
			{
				if(a[j][i]==0) continue;
				f=true;
				for(int k=1;k<=n;k++) swap(a[i][k],a[j][k]);
				break;
			}
			if(!f) return 0;
			res=p-res;
		}
		res=1ll*res*a[i][i]%p;
		for(int j=i+1;j<=n;j++)
		{
			if(a[j][i]==0) continue;
			int ml=1ll*a[j][i]*qpow(a[i][i],p-2)%p;
			for(int k=1;k<=n;k++) add(a[j][k],p-1ll*ml*a[i][k]%p);
		}
	}
	return res;
}

Cauchy-Binet 定理

设 $A$ 是一个 $n\times m$ 的矩阵， $B$ 是一个 $m\times n$ 的矩阵，则：
$|AB|=\begin{cases} 0&m<n\\ \sum\limits_{S\in \binom{[m]}{n}} |A_{[n],S}|\times |B_{S,[n]}| &m\ge n \end{cases}$
第二条的意思是，枚举 $\{1,2,3,\dots,m\}$ 的所有大小为 $n$ 的子集 $S$ ，将 $1\le i\le n,j\in S$ 的所有 $A_{i,j}$ 拿出来按照原来的顺序组成一个方阵，记为 $A_{[n],S}$ ，同理定义 $B_{S,[n]}$ ，求出其行列式的积的和。

证明

考虑矩阵乘法的本质，有：
$\begin{aligned} |AB|&=\sum\limits_{p\in P(n)}(-1)^{\sigma(p)}\prod\limits_{i=1}^{n}(AB)_{i,p_i}\\ &=\sum\limits_{p\in P(n)}(-1)^{\sigma(p)}\prod\limits_{i=1}^{n}\sum\limits_{j=1}^m A_{i,j}\times B_{j,p_i}\\ &=\sum\limits_{p\in P(n)}(-1)^{\sigma(p)}\sum\limits_{j_1=1}^m\sum\limits_{j_2=1}^m\sum\limits_{j_3=1}^m\dots \sum\limits_{j_n=1}^m\prod\limits_{i=1}^{n}A_{i,j_i}\times B_{j_i,p_i}\qquad \text{(应用乘法分配律)}\\ &=\sum\limits_{j_1=1}^m\sum\limits_{j_2=1}^m\sum\limits_{j_3=1}^m\dots \sum\limits_{j_n=1}^m\sum\limits_{p\in P(n)}(-1)^{\sigma(p)}\prod\limits_{i=1}^{n}A_{i,j_i}\prod\limits_{i=1}^nB_{j_i,p_i}\\ &=\sum\limits_{j_1=1}^m\sum\limits_{j_2=1}^m\sum\limits_{j_3=1}^m\dots \sum\limits_{j_n=1}^m\left(\prod\limits_{i=1}^{n}A_{i,j_i}\right)\sum\limits_{p\in P(n)}(-1)^{\sigma(p)}\prod\limits_{i=1}^nB_{j_i,p_i}\\ \end{aligned}$
注意到 $\sum\limits_{p\in P(n)}(-1)^{\sigma(p)}\prod\limits_{i=1}^nB_{j_i,p_i}$ 就是 $|B_{\{j_i\},[n]}|$ （逆排列逆序对个数不变，即按行描述和按列描述本质相同），而若 $j_i$ 中有重复元素，则其非满秩，行列式为 $0$ ，故有：
$\begin{aligned} |AB|&=\sum\limits_{S\in\binom{[m]}{n}}\sum\limits_{q\in P(n)}\left(\prod\limits_{i=1}^{n}A_{i,S_{q_i}}\right)\sum\limits_{p\in P(n)}(-1)^{\sigma(p)}\prod\limits_{i=1}^nB_{S_{q_i},p_i}\\ &=\sum\limits_{S\in\binom{[m]}{n}}\sum\limits_{q\in P(n)}\left(\prod\limits_{i=1}^{n}A_{i,S_{q_i}}\right)\sum\limits_{p\in P(n)}(-1)^{\sigma(p)}\prod\limits_{i=1}^nB_{S_i,q^{-1}_{p_i}}\\ &=\sum\limits_{S\in\binom{[m]}{n}}\sum\limits_{q\in P(n)}\left(\prod\limits_{i=1}^{n}A_{i,S_{q_i}}\right)\sum\limits_{p\in P(n)}(-1)^{\sigma(q^{-1})}(-1)^{\sigma(p)}\prod\limits_{i=1}^nB_{S_i,p_i}\\ &=\sum\limits_{S\in\binom{[m]}{n}}\left(\sum\limits_{q\in P(n)}(-1)^{\sigma(q)}\prod\limits_{i=1}^{n}A_{i,S_{q_i}}\right)\sum\limits_{p\in P(n)}(-1)^{\sigma(p)}\prod\limits_{i=1}^nB_{S_i,p_i}\\ &=\sum\limits_{S\in \binom{[m]}{n}} |A_{[n],S}|\times |B_{S,[n]}| \end{aligned}$

例题：

Loj #3409. 「2020-2021 集训队作业」Yet Another Linear Algebra Problem

LGV 引理

对于一个带权 DAG $G$ ，定义如下符号：

对于一条路径 $p$ ， $w_{p}$ 为路径上所有边边权的积；

对于两个点 $u,v$ ， $e_{u,v}$ 为 $u\to v$ 的所有路径 $p$ 的 $w_p$ 之和，即 $e_{u,v}=\sum\limits_{p\in\{u\to v\}} w_p$ ；

一组由起点集合 $A$ 到终点集合 $B$ （ $|A|=|B|$ ）的不相交路径 $(S,p_i)$ ：

$|S|=|A|$ 且 $S_i$ 是一条由 $A_i$ 到 $B_{p_i}$ 的路径，其中 $p\in P(|A|)$ ，且 $\forall i\not=j$ ， $S_i$ 和 $S_j$ 没有公共点；

LGV 引理指出：
$\left|\begin{bmatrix} e_{A_1,B_1}&e_{A_1,B_2}&\dots&e_{A_1,B_n}\\ e_{A_2,B_1}&e_{A_2,B_2}&\dots&e_{A_2,B_n}\\ \vdots&\vdots&\ddots&\vdots\\ e_{A_n,B_1}&e_{A_n,B_2}&\dots&e_{A_n,B_n} \end{bmatrix}\right|=\sum\limits_{(S,p)}(-1)^{\sigma(p)}\prod\limits_{i=1}^{|A|} w_{S_i}$

证明

考虑行列式的定义，设等号左边的矩阵为 $C$ ， $|A|=n$ ，则：
$\begin{aligned} |C|&=\sum\limits_{p\in P(n)}\limits (-1)^{\sigma(p)} \prod \limits_{i=1}^n e_{A_i,B_{p_i}}\\ &=\sum\limits_{p\in P(n)}\limits (-1)^{\sigma(p)} \prod \limits_{i=1}^n \sum\limits_{q\in \{A_i\to B_{p_i}\}}w_q\\ &=\sum\limits_{p\in P(n)}\limits (-1)^{\sigma(p)}\sum\limits_{q_1\in \{A_1\to B_{p_1}\}}\sum\limits_{q_2\in \{A_2\to B_{p_2}\}}\dots \sum\limits_{q_n\in\{A_n\to B_{p_n}\}}\prod\limits_{i=1}^n w_{q_i}\\ \end{aligned}$
不难发现，由于 $w_{q_i}$ 是路径边权积，所以 $\prod\limits_{i=1}^n w_{q_i}$ 实际上相当于 $q_{[1,n]}$ 这些路径经过的可重边集的边权积。

此时若 $q_i$ 与 $q_j$ 有公共点，那么交换它们最后一个公共点后的路径会使得 $\sigma(p)$ 奇偶性改变，而 $\prod\limits_{i=1}^n w_{q_i}$ 并不会变，所以只有 $q_{[1,n]}$ 两两不交才有贡献，那么：
$\sum\limits_{p\in P(n)}\limits (-1)^{\sigma(p)}\sum\limits_{q_1\in \{A_1\to B_{p_1}\}}\sum\limits_{q_2\in \{A_2\to B_{p_2}\}}\dots \sum\limits_{q_n\in\{A_n\to B_{p_n}\}}\prod\limits_{i=1}^n w_{q_i}=\sum\limits_{(S,p)}(-1)^{\sigma(p)}\prod\limits_{i=1}^{|A|} w_{S_i}$

应用：求不交路径数量

LGV 引理还可以求出从起点集合 $A$ 到终点集合 $B$ 的不交路径条数，即找到最大的 $k$ 使得存在一个路径集合 $S$ 满足：

$|S|=k$ ；
$S$ 中每条路径的起点都在 $A$ 中，终点都在 $B$ 中；
$S$ 中的路径两两之间没有公共点；

也可以看成将每个点拆成入点和出点之后的最大流。

先来考虑怎么判定其满流，即 $|A|=|B|$ 时判断 $k=|A|$ 。显然这个相当于给每条边权值设为任意正整数后判断 $\sum\limits_{(S,p)}\prod\limits_{i=1}^{|A|} w_{S_i}$ 是否非 $0$ 。

但这是积和式，是个 NP 问题。

所以不妨考虑行列式 $\sum\limits_{(S,p)}(-1)^{\sigma(p)}\prod\limits_{i=1}^{|A|} w_{S_i}$ ，那么此时唯一的问题就是 $(-1)^{\sigma(p)}$ 可能让后面的贡献抵消了。但是由于 Schwartz-Zippel 定理，不妨为每条边随机赋一个权值，这样行列式就是 $n$ 次多项式（ $n$ 为 DAG 的点数），故在 $\text{mod }p$ 域下错误率是 $\frac{n}{p}$ 的，足够小了。

回到原问题，不难发现在随机赋权后就相当于要找到最大的 $k$ 使得存在 $A$ 的一个 $k$ 阶子矩阵满秩。这就相当于求 $A$ 的秩，直接线性基即可。

另外，该方法还可以求正常的流量全为 $1$ 的网络流（不经过重复边），仅需将边拆成点即可。

该方法复杂度是 $O(\min(|A|,|B|)^2\times \max(|A|,|B|))$ 的，适用于 $A$ 和 $B$ 中某个集合很小的情况。

例题：

矩阵树定理

对于 $n$ 个点的简单无向图 $G$ ，设点 $i$ 的度数为 $d_i$ ，设 $n\times n$ 的矩阵 $A$ 满足：

$A_{i,j}=\begin{cases}d_i& i=j\\-1&i\not=j,(i,j)\in G\\0&otherwise\end{cases}$

设 $M_{i,j}$ 为 $A$ 删去第 $i$ 行第 $j$ 列后的 $(n-1)\times (n-1)$ 矩阵，则 $G$ 的生成树个数等于 $|M_{i,i}|$ ，其中 $1\le i\le n$ 。

证明

设 $G$ 中有 $m$ 条边 $(u_i,v_i)$ ，定义 $n\times m$ 的矩阵 $E$ 满足：

$\forall 1\le i\le m$ 都有 $E_{i,u_i}=1,E_{i,v_i}=-1$ ；

其它位置 $E_{i,j}=0$ ；

$u_i$ 和 $v_i$ 的顺序没关系，只要一个位置是 $1$ 一个位置是 $-1$ 就行了。

不难发现 $A=E\times E^T$ ，且设 $F_i$ 为 $E$ 删除第 $i$ 行后的矩阵，则 $M_{i,i}=F_i\times F^T_i$ 。

那么根据 Cauchy-Binet 定理，有：
$\begin{aligned} |M_{i,i}|&=|F_i\times F_i^T|\\ &=\sum\limits_{S\in\binom{[m]}{n-1}} |(F_i)_{[n-1],S}|\times |(F^T_i)_{S,[n-1]}|\\ &=\sum\limits_{S\in\binom{[m]}{n-1}} |(F_i)_{[n-1],S}|\times |(F_i)_{S,[n-1]}^T|\\ &=\sum\limits_{S\in\binom{[m]}{n-1}} |(F_i)_{[n-1],S}|^2\\ \end{aligned}$
注意到， $S$ 相当于从 $m$ 条边中无序地选取了 $n-1$ 条，那么仅需证明 $S$ 是生成树时 $|(F_i)_{[n-1],S}|=\pm 1$ ，否则 $|(F_i)_{[n-1],S}|=0$ 即可。

不妨设 $Q=F_1$ ，尝试对 $Q$ 证明该结论。

不难发现，若 $S$ 不是生成树，则其中必定存在环。而对于一个环 $C\in S$ ， $C_1$ 对应的列向量一定能被 $C_{>1}$ 对应的列向量依次乘上 $1$ 或 $-1$ 再求和得到（断环为链后只剩下两边的点未被消去），那么 $Q_{[n-1],S}$ 不会是满秩矩阵，故其行列式为 $0$ 。

并且这一条件显然是充要的，因为若没有环则任意一条链两端的点都无法被消去。

接下来证明 $|Q|\in\{-1,0,1\}$ 。由于我们不关心它的符号，所以从行列式的定义出发， $|Q|$ 相当于要给 $S$ 中的每条边选择一个端点，将这 $n-1$ 个端点对应的系数乘起来。

由于第 $1$ 行已经被删去，所以 $u_i=1$ 的边都只能选 $v_i$ 。而由于选点不能重复，所以可以以 $1$ 为根从上至下确定每条边选择的点（儿子），那么选点方案只有一种，故此时 $|Q|\in\{-1,1\}$ 。

那么 $Q$ 的情况证毕，而对于 $F_i$ （ $i\not =1$ ）都是等价的，其实只是相当于钦定的根不一样。

拓展形式：

无向带边权 $w_{(i,j)}$ （计算的是所有生成树边权积的和）：

$A_{i,j}=\begin{cases}\sum\limits_{(i,v)\in G} w_{(i,v)}& i=j\\-w_{(i,j)}&i\not=j,(i,j)\in G\\0&otherwise\end{cases}$

证明仅需将 $E$ 改为一个 $\sqrt{w_{(i,j)}}$ ，另一个 $-\sqrt{w_{(i,j)}}$ 即可。

有向带边权：

根向树，根为 $r$ ：
$A_{i,j}=\begin{cases}\sum\limits_{i\to v\in G} w_{i\to v}&i=j\\ -w_{i\to j}&i\not=j,i\to j\in G\\ 0&otherwise\end{cases}$
根向树边权积的和为 $|M_{r,r}|$ 。

证明和无向图情况类似，改变一下 $E$ 的定义：

$(E_{out})_{i,j}=\begin{cases}\sqrt{w_{e_j}}&e_j=i\to x\\0&otherwise\end{cases}$

$(E_{in})_{i,j}=\begin{cases}\sqrt{w_{e_j}}&e_j=x\to i\\0&otherwise\end{cases}$

则有 $A=E_{out}\times (E_{out}-E_{in})^T$ ，后面的步骤套用无向图情况即可。

叶向树，根为 $r$ ：
$A_{i,j}=\begin{cases}\sum\limits_{v\to i\in G} w_{v\to i}&i=j\\ -w_{i\to j}&i\not=j,i\to j\in G\\ 0&otherwise\end{cases}$
叶向树边权积的和为 $|M_{r,r}|$ ，证明和根向树类似。

边权只要在同一个域下就行了，例如可以是多项式。

应用：最小生成树计数

考虑 Kruskal 的过程，每次把边权最小的边加入图中，对每个联通块求出生成树个数，然后将整个连通块缩点即可。

例题：

P2143 [JSOI2010] 巨额奖金

应用：复杂边权

注意到矩阵树定理做的实际上是：

\sum\limits_{T}[T\text{ is a tree}]\prod\limits_{e\in T} w_e

那么边权不一定要是数，只要可以在其上定义加法和乘法即可（是个环）。

例如边权可以是多项式、集合幂级数，只需要先做一遍 DFT/FWT 求出点值，再对每个点值分别跑矩阵树，最后合并起来跑 IDFT/IFWT 即可。

例题：

BEST 定理

对于一个存在欧拉回路的有向图 $G$ ，其从 $s$ 出发的欧拉回路个数为：
$T(s)\times d_s!\times \prod\limits_{u\not=s} (d_u-1)!$
其中 $T(s)$ 为 $G$ 中以 $s$ 为根的根向树个数， $d_u$ 为 $u$ 的出度（入度等于出度）。

而 $G$ 的所有欧拉回路个数为：
$T(1)\times \prod\limits_{u}(d_u-1)!$

证明

先证第一条。

考察除去 $s$ 外每个点最后的一条出边，不难发现这些边不可能成环，因为每次进入一个非 $s$ 的点后一定要离开它，那么这些边构成了一棵根向树。

由此我们构建了一个从欧拉回路到根向树的映射。

而不难发现，由于欧拉回路存在的充要条件是弱联通且每个点度数为偶数，则除去根向树外，每个点的出边可以任意确定走的次序。这是因为无论怎么走，根向树的树边总是最后一个删掉的，图必定一直弱联通，而度数的条件更不用说了。

对于起点 $s$ ，它没有树边，所以所有出边可以以任意次序走，自然没有 $-1$ 。

第二条也是同理，先计算出从 $1$ 出发的欧拉回路个数，而由于 $1$ 的出度为 $d_1$ ，故其在同一条回路中出现了 $d_1$ 次，那么每次出现都可以作为一个起点而将该回路计算一次，故总数需要除掉 $d_1$ 。