线性代数

· · 算法·理论

\scriptsize\text{\color{Red}该变量不应为空。}

线性代数在 OI 中没有用处。

Gauss-Jordan 求解逆矩阵。

行列式求值，其中 P 是排列，\pi(P) 是逆序对数。

\det(A)=\sum_{P}(-1)^{\pi(P)}\prod_{i=1}^{n}a_{i,p_i}

另一种递归式定义：

\det(A)=\sum_{j=1}^{n}a_{i,j}A_{i,j}=\sum_{i=1}^{n}a_{i,j}A_{i,j}

注意到 gauss 消元后形成一个上三角矩阵，而该矩阵的行列式很好算，即 \prod a_{i,i}。由于 gauss 消元过程中都是初等行变换，考虑计算变换后行列式的变化。

int det(int n){
    int res=1;
    for(int i=2;i<=n;i++){
        int r=i;
        for(int j=i+1;j<=n;j++)if(a[j][i]>a[r][i])r=j;
        if(!a[r][i])continue;
        if(r!=i){
            res=-res;
            for(int j=i;j<=n;j++)swap(a[i][j],a[r][j]);
        }
        for(int j=i+1;j<=n;j++){
            while(a[j][i]){
                int d=a[i][i]/a[j][i];res=-res;
                for(int k=i;k<=n;k++)a[i][k]=mod(a[i][k]+p-(ll)d*a[j][k]%p),swap(a[i][k],a[j][k]);
            }
            //有逆时直接乘逆元也行 
        }
    }
    if(res<0)res+=p;
    for(int i=2;i<=n;i++)if(a[i][i])res=(ll)res*a[i][i]%p;
    return res;
}

LGV 引理。

Tutte 矩阵。

考虑设计矩阵 G。

对于 i\le j，如果 i 到 j 有边，那么 G_{i,j}=x_{i,j}，G_{j,i}=-x_{i,j}。否则 G_{i,j}=G_{j,i}=0。

结论：\det(G)\ne 0 等价于图存在完美匹配。

证明可以考虑 \det(G) 的定义

\det(G)=\sum_{P}(-1)^{\pi(P)}\prod_{i=1}^{n}G_{i,p_i}

如果该式存在贡献，那么对于 \forall i，i 到 p_i 必然有边，产生贡献的边形成了若干个环。

注意到如果这些环中有奇环，那么把环翻转后 (-1)^{\pi(P)} 恰好取反，因此奇环的两种情况抵消。

所以只需要考虑只有偶环的情况。此时每个偶环内的点必然存在匹配。而如果存在匹配，那么这些点两两成环必然合法。证毕。

考虑怎么求最大匹配，大胆猜测：答案是 \frac{rank(G)}{2}。证明忘了，时间复杂度 O(n^3)。

线性基

将长度为 n 的序列映射到长度为 \log V 的序列上。使其子集的异或集合相等。

可以 O(\log V) 插入，O(\log^2 V) 合并。通常解决子集异或问题，求 k 大的时候需要先通过线性变换使得任意 a,b\in S 满足 a\oplus b\ge\max(a,b)。

通常搭配 O(1) 合并的数据结构如 st 表。

可删线性基离线可做到 O(\log V)，记录每个数的删除时间，每次插入从高位到低位贪心地选择最晚删除的数。在线 O(\log^2 V)，https://www.luogu.com.cn/article/vd9qdrcd。

Matrix-Tree 定理

对于有向图 G，定义

入度类似。于是有以 k 为根的内向生成树数量 t^{\text{root}}(G,k) 和外向生成树数量 t^{\text{leaf}}(G,k) 为

t^{\text{root}}(G,k)=\det L^{\text{out}}(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}\\ t^{\text{leaf}}(G,k)=\det L^{\text{in}}(G)_{[n]\setminus\{k\},[n]\setminus\{k\}}

相当于将第 k 行第 k 列去掉后行列式的值。

定义 m\times n 的关联出度矩阵 M^{out} 为

M^{out}_{i,j}=\left\{\begin{matrix} 1 & u_i=j \\ 0 & i\ne j \end{matrix}\right.

同理得到关联入度矩阵。

简单推导可得 D^{out}=(M^{out})^{T}M^{out}，A=(M^{out})^TM^{in}。所以有 L^{out}=(M^{out})^T(M^{out}-M^{in})。

引理：

对于图 G(V,E)，如果子图 T(V,S) 是以 V\setminus W 为根的内向森林，当且仅当

\det(M^{out}_{S,W})\det(M^{out}_{S,W}-M^{in}_{S,W})\ne 0

通过分析可以知道，M^{out}_{S,W} 每行至多有一个 1，当 \det(M^{out}_{S,W})\ne 0 时即代表每行恰好一个 1 且每一列恰好一个 1，或者说 W 中每个点与 S 中一条边的起点形成双射，也可以说它们出度都为 1。

前半部分限制出度为 1，那么后半部分应该限制无环。当前面不为 0 时，M^{out}_{S,W}-M^{in}_{S,W} 每行每列恰有一个 1，但是可能有 1 或 0 个 -1。如果存在环，容易发现通过若干次一行加到另一行上最终会使得一行为 0，又由于该操作不改变行列式，故原行列式也为 0，如

\begin{vmatrix} 1 & -1 & 0 & 0\\ 0 & 1 & -1 & 0\\ 0 & 0 & 1 & -1\\ -1 & 0 & 0 & 1 \end{vmatrix}

并且当该式不为 0 时，可以通过该操作使得每行有且仅有一个 1，则此时 \det(M^{out}_{S,W}-M^{in}_{S,W})=\det(M^{out}_{S,W})。所以原式也 =\det(M^{out}_{S,W})^2=1。

Cauchy–Binet 公式：

对于 n\times m 的矩阵

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

联立引理可证明矩阵树定理，令 W=[n]\setminus\{k\}：

\begin{aligned} \det L^{\text{out}}(G)_{W,W}&=\det ((M_{V,W}^{out})^T(M_{V,W}^{out}-M_{V,W}^{in}))\\ &=\sum_{S\subset[m],|S|=n-1}\det (M^{out}_{S,W})\det(M_{W}^{out}-M_{V,W}^{in})\\ &=\sum_{S\subset[m],|S|=n-1}[S 是原图以k为根的生成树] \end{aligned}

扩展

带边权。会发现实际上算的是所有生成树边权乘积的和。

因为将关联矩阵重定义为

M^{out}_{i,j}=\left\{\begin{matrix} \sqrt{w_i} & u_i=j \\ 0 & i\ne j \end{matrix}\right.

则引理算出来的行列式即为 \prod w_i。

求所有生成树边权和的 k 次方的和。

只需要把乘法变成加法，容易想到类似于原根的东西。

相当于将矩阵中的元素变成一个多项式，重定义加减乘除。对于本题来说，有

(f\otimes g)(i)=\sum_{j=0}^{i}\binom{i}{j}f(j)g(i-j)\\ (f\oplus g)(i)=f(i)+g(i)

或者也可以理解为已知 w=w_1+w_2+\cdots w_{k-1} 的 0\sim k 次方，求 (w+w_k) 的 0\sim k 次方。

答案就是 \det(k)。

应用

Cayley 公式

### Best 定理 对于一个有向欧拉图，其不同欧拉回路的数量为 $$ \text{ec}(G)=t^{\text{root}}(G,k)\prod_{u\in V}(\deg(u)-1)! $$ 由于欧拉图出度和入度相等，所以令 $\deg(u)=\deg^{\text{out}}(u)=\deg^{\text{in}}(u)$。只用考虑固定从 $k$ 出发。 容易发现，由欧拉回路的性质，如果每个点除 $k$ 外都取最后一条出边，则会构成一棵树。如果成环，意味着一个点在走完最后一条出边后还走了它的入边，显然不会构成欧拉回路。 于是每条欧拉回路都能对应一棵以 $k$ 为根的内向树，除了树上的边外，其他边的顺序不固定，可以得到 $t^{\text{root}}(G,k)\deg(k)!\prod_{u\in V,u\ne k}(\deg(u)-1)!$，但是 $k$ 会在路径中出现 $\deg(k)$ 次，所以一条路径会计算 $\deg(k)$ 次，去重后便得到上式。 可以感性理解方案与欧拉回路间构成双射。