线性代数学习笔记
Lucky_Xiang
·
·
算法·理论
行列式
定义
对于方阵 A，其行列式用以下方式表示：
\det A=\begin{vmatrix}a_{1,1} &a_{1,2} &\dots & a_{1,n} \\ a_{2,1} &a_{2,2} &\dots & a_{2,n} \\ \vdots &\vdots & \ddots &\vdots \\ a_{n,1} &a_{n,2} &\dots &a_{n,n}\end{vmatrix}
设 p 为一个排列，\tau(p) 表示 p 的逆序对个数，则：
\det A=\sum\limits_{p}(-1)^{\tau(p)}\prod\limits_{i=1}^n a_{i,p_i}
行列式表示 n 个 n 维向量形成的有向体积。
性质
- 行列式中交换两行会使其结果乘 -1。
- 行列式中将一行乘 k 的结果加到另一行上，结果不变。
- 将行列式一行乘 k，其结果也乘 k。
- 将行列式转置（a_{i,j}'=a_{j,i}），结果不变。
求值
如果将通过以上性质，将所有的 a_{i,j}(i>j) 都变成 0，则最终结果为 \prod\limits_{i=1}^n a_{i,i}。
这可以用高斯消元进行完成。但是如果模数不是质数，就不能做了。
于是可以用辗转相除法进行代替。
LL solve()
{
int w=1;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
while(a[i][i])
{
LL D=a[j][i]/a[i][i];
for(int k=i;k<=n;k++)
{
a[j][k]-=D*a[i][k];
a[j][k]%=mod;
}
swap(a[i],a[j]); w*=-1;
}
swap(a[i],a[j]); w*=-1;
}
}
LL s=w;
for(int i=1;i<=n;i++)s=s*a[i][i]%mod;
return (s%mod+mod)%mod;
}
发现每进行两次辗转相除，a_{i,i} 都会减半。所以复杂度均摊 O(n^2\log n+n^3)。
矩阵树定理
给定一个无向图，求出它的生成树个数。
A=\begin{pmatrix}a_{1,1} &a_{1,2} &\dots & a_{1,n} \\ a_{2,1} &a_{2,2} &\dots & a_{2,n} \\ \vdots &\vdots & \ddots &\vdots \\ a_{n,1} &a_{n,2} &\dots &a_{n,n}\end{pmatrix}
其中 a_{x,y} 表示 x\longleftrightarrow y 的边数乘 -1，而 a_{x,x} 表示 x 的度数。
将 A 去掉第 k 行和第 k 列得到 A'，\det A' 即为答案。（可以证明结果与 k 的选取无关）
如果要边要加权，求出所有生成树边权之积的和，则相当于是加重边。
内向树/外向树
如果是求内向树个数，则 a_{x,y} 表示 x\longrightarrow y 的边数乘 -1，a_{x,x} 表示 x 的出度数。
如果是求外向树个数，则 a_{x,y} 表示 x\longleftarrow y 的边数乘 -1，a_{x,x} 表示 x 的入度数。
总之无论怎样，每行之和都是 0。如果忘记了，可以把两种情况都试一下。
特别的，若 rt 为根，则 A 必须删除第 rt 行和第 rt 列，再计算 \det A'。
LGV 引理
设 \tau(\sigma) 表示排列 \sigma 的逆序对个数，\omega(P) 表示路径 P 上边权的乘积。再设 e(a,b) 表示 \sum\limits_{P:a\to b} \omega(P) 。
在一个有向无环图（DAG）中，有起点 A=\{a_1,a_2,\dots,a_n\}，和终点 B=\{b_1,b_2,\dots, b_n\}。
对于 A\to B 的 n 条路经 P=(P_1,P_2,\dots,P_n)，其中第 i 条路径从 a_i\to b_{c_i}，且所有路径不交（指没有公共点），则将排列 c 记作 \sigma(P)。
则有：
\det M=\sum_{P:A\to B}(-1)^{\tau(\sigma(P))} \prod\limits_{i=1}^n \omega(P_i)
其中：
M=\begin{pmatrix}e(1,1) &e(1,2) &\dots & e(1,n) \\ e(2,1) &e(2,2) &\dots & e(2,n) \\ \vdots &\vdots & \ddots &\vdots \\ e(n,1) &e(n,2) &\dots &e(n,n)\end{pmatrix}
注意到，若在一些特殊的图中，仅存在 a_i\to b_i 的不交路径，则 \det M 即为不交路径个数。