LGV 引理学习笔记

1.1 矩阵转置

对于矩阵 $A$ ，定义 $A^T$ 为 $A$ 的转置，满足 $A^T_{i,j}=A_{j,i}$ 。

1.2 行列式

几何意义：基向量在空间中组成图形的体积

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

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

其中 $Per(n)$ 为 $n$ 的排列集合， $\sigma(p)$ 为 $p$ 的逆序对个数，非方阵的行列式为 $0$ 。

1.2.1 相关性质

$|A^T|=|A|$ ，故以下关于行的性质关于列也满足；

每行选一个相当于每列选一个。
若 $A$ 不是满秩（有某一个向量可以被其他向量线性组合出来），则 $|A|=0$ ；

根据几何意义，此时基向量没有张成整个 $n$ 维空间，故基向量组成图形体积为 $0$ 。
交换 $A$ 的任意不同两行，则 $|A|$ 取反；

因为交换排列任意不同两位对逆序对的改变都是奇数的。
$|A|$ 是关于每一行的线性函数，即：
- 将 $A$ 中某一行整体乘上任意实数 $a$ ，则 $|A|$ 会乘上 $a$ ；
- $\left|\begin{matrix}a+a'&b+b'\\c&d\end{matrix}\right|=\left|\begin{matrix}a&b\\c&d\end{matrix}\right|+\left|\begin{matrix}a'&b'\\c&d\end{matrix}\right|$
  
  根据乘法分配律易得。
根据这个性质有一个推论：
- 将 $A$ 中某一行整体乘上任意实数 $a$ 再按位加到另一行，则 $|A|$ 不变；

1.2.3 求解

注意到若一个 $n\times n$ 的矩阵 $A$ 只有下半部分非零，则 $|A|=\prod\limits_{i=1}^n A_{i,i}$ 。

那么类似高斯消元，通过 $|A|$ 关于每一行的线性性进行消元，直到 $A$ 只剩下下半部分为止即可。

代码

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

inline int qpow(int x,int y=p-2)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

struct mrt
{
	int n,m,a[S][S];
	inline mrt(){n=m=0,memset(a,0,sizeof(a));}
	inline mrt(int x){n=m=x,memset(a,0,sizeof(a));}
	inline mrt(int x,int y){n=x,m=y,memset(a,0,sizeof(a));}
	inline int* operator[](int x){return a[x];}
	inline int det()
	{
		if(n!=m) return 0;
		mrt b=*this;
		int mul=1;
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n&&b[i][i]==0;j++)
			{
				if(b[j][i]!=0)
				{
					for(int k=1;k<=n;k++) swap(b[i][k],b[j][k]);
					mul=p-mul;
					break;
				}
			}
			int inv=qpow(b[i][i]);
			for(int j=i+1;j<=n;j++)
			{
				if(b[j][i]==0) continue;
				int mul=1ll*b[j][i]*inv%p;
				for(int k=1;k<=n;k++) add(b[j][k],p-1ll*b[i][k]*mul%p);
			}
		}
		for(int i=1;i<=n;i++) for(int j=1;j<i;j++) if(b[i][j]!=0) mul=0;
		for(int i=1;i<=n;i++) mul=1ll*mul*b[i][i]%p;
		return mul;
	}
};

1.3 LGV 引理

对于一个带边权的 DAG，定义一条路径的权值为路径上所有边的边权积。

对于这个 DAG 上两个大小为 $n$ 的点序列 $S$ 和 $T$ ，设 $S_i\to T_i$ 的所有路径权值的和为 $w_{i,j}$ 。

定义一个路径组为一个大小为 $n$ 的排列 $p$ 和大小为 $n$ 的路径序列 $P$ 组成的二元组 $(p,P)$ ，其中 $P_i$ 起点为 $S_i$ ，终点为 $T_{p_i}$ 。定义路径组 $(p,P)$ 的权值 $v_{(p,P)}$ 为 $P$ 中路径权值的积。

对于一个路径组 $(p,P)$ ，如果 $P$ 中任意两条路径没有公共点，则称其为不交路径组，记这样的路径组为 $(p,P)^*$ 。

设 $A$ 为一个 $n\times n$ 的方阵，且 $A_{i,j}=w_{i,j}$ ，则 $|A|=\sum\limits_{(p,P)^*}(-1)^{\sigma (p)}v_{(p,P)^*}$ 。

证明很简单，先乘法分配律拆开，显然 $|A|=\sum\limits_{(p,P)}(-1)^{\sigma (p)}v_{(p,P)}$ 。

假若两条路径有公共点，那么把最后一个公共点后的路径交换一下，则 $v_{(p,P)}$ 不变，而 $(-1)^{\sigma(p)}$ 会变为相反数，故会互相抵消，证毕。

1.3.1 Cauchy–Binet 定理

对于一个 $n\times m$ 的矩阵 $A$ 和一个 $m\times n$ 的矩阵 $B$ ，有：
$|AB|=\sum\limits_{s\in\{1,2,3,\dots,m\},|s|=n} \left|\begin{matrix}A_{1,s_1}&A_{1,s_2}&\dots&A_{1,s_n}\\A_{2,s_1}&A_{2,s_2}&\dots&A_{2,s_n}\\\vdots&\vdots&\ddots&\vdots\\A_{n,s_1}&A_{n,s_2}&\dots&A_{n,s_n}\end{matrix}\right|\times\left|\begin{matrix}B_{s_1,1}&B_{s_1,2}&\dots&B_{s_1,n}\\B_{s_2,1}&B_{s_2,2}&\dots&B_{s_2,n}\\\vdots&\vdots&\ddots&\vdots\\B_{s_n,1}&B_{s_n,2}&\dots&B_{s_n,n}\end{matrix}\right|$
也就是分别拿出 $A$ 的 $n$ 列，拿出 $B$ 的 $n$ 行，算出其行列式，乘起来。

证明很简单，构造一个三层图，头尾两层 $n$ 个点，中间一层 $m$ 个点。第一层第 $i$ 个点向第二层第 $j$ 个点连 $A_{i,j}$ ，第二层向第三层连 $B_{i,j}$ 。

那么应用 LGV 引理不难发现等式两边都在计算从 $S$ 为第一层的点， $T$ 为第三层的点的 $\sum\limits_{(p,P)^*}(-1)^{\sigma (p)}v_{(p,P)^*}$ ，得证。