线性代数

· · 算法·理论

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

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

矩阵

行列式

行列式求值，其中 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;
}

矩阵的秩

矩阵的秩，指的是矩阵中线性无关的行（或列）的最大数目。

一个关键且优美的结论是：对于任何矩阵，其行秩始终等于其列秩。因此，我们统称为矩阵的秩。

设 A 是一个 m\times n 矩阵，其秩记为 \text{rank}(A)，并且满足 0\le \text{rank}(A)\le \min(n,m)。

通俗的说

所以 \text{rank}(A) 是将 A 化为行阶梯形后（高斯消元）非零行的个数，或者说非零子式（任选 k 行 k 列构成行列式）的最高阶数。

## 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$ 必然有边，产生贡献的边形成了若干个环。 注意到如果这些环中有奇环，那么把环翻转后 $G$ 的乘积恰好取反，而逆序对不变。因此奇环的两种情况抵消。 所以只需要考虑只有偶环的情况。此时每个偶环内的点必然存在匹配。而如果存在匹配，那么这些点两两成环必然合法。证毕。 ### 最大匹配 考虑怎么求最大匹配，大胆猜测：答案是 $\frac{\text{rank}(G)}{2}$。回忆一下，矩阵的秩是什么？ 设 $M$ 为其最大匹配， - 证明 $\text{rank}(G)\ge 2|M|$。假设 $M$ 覆盖的顶点集合为 $S$，$|S|=2|M|$。将顶点重新排序，使得 $S$ 中的顶点对应前 $2|M|$ 行和前 $2|M|$ 列，考虑 $G$ 的由 $S$ 诱导的主子矩阵 $G[S]$，它是一个 $2|M|\times 2|M|$ 的斜对称矩阵。 因为 $M$ 是 $S$ 的一个完美匹配，所以根据上面的结论有 $\det(G[S])\ne0$，所以 $G[S]$ 满秩，$\text{rank}(G)\ge \text{rank}(G[S])=2|M|$。 - 证明 $\text{rank}(G)\le 2|M|$。设 $r=\text{rank}(G)$，因为 $G$ 是斜对称矩阵，所以 $r$ 是偶数。根据秩的定义，$G$ 存在一个 $r$ 阶主子矩阵 $T$ 满足 $\det(T)\ne 0$。设 $S$ 为其对应的顶点集合，那么 $T$ 事实上就是子图 $G[S]$ 的 Tutte 矩阵，因为 $\det(T)\ne 0$，所以 $G[S]$ 存在完美匹配，也是原图的一个匹配，并且匹配数为 $\frac{r}{2}$。所以得到 $|M|\ge \frac{r}{2}$ 即 $2|M|\ge r$。 ### 最小（大）权完美匹配 更改一下 $G$ 的定义，在每个 $G_{i,j}$ 后面乘一个 $y^{w_{i,j}}$，然后 $\det(G)$ 求出来就是一个关于 $y$ 的多项式。以最小权完美匹配为例，结论：**最小权完美匹配的权值等于 $\det(G)$ 的系数非零项里 $y$ 的最低次数除以 $2$。** 假设其最小权完美匹配是 $M=\{(u_1,v_1),(u_2,v_2),\cdots\}$，权值是 $k$。那么在算行列式时排列 $p_{u_i}=v_i,p_{v_{i}}=u_i$ 一定会对 $y^k$ 产生贡献，所以 $y^k$ 系数是非零的。所以只需要证明次数 $<k$ 的系数全零即可。考虑反证，假设排列 $\sigma$ 对小于 $y^r(r<k)$ 产生贡献，即 $\sigma$ 是若干偶环。考虑将环长 $\ge 4$ 的偶环拆成若干二元环。假设这个偶环上点集 $\{s_1,s_2,\cdots,s_{2l}\}$，那么要么将其拆为 $\{\{s_1,s_2\},\{s_3,s_4\},\cdots,\{s_{2l-1},s_{2l}\}\}$，要么就是 $\{\{s_2,s_3\},\{s_4,s_5\},\cdots,\{s_{2l},s_{1}\}\}$，然后拆成权值和最小。注意到 $$ 2\min(w_{s_1,s_2}+w_{s_3,s_4}+\cdots,w_{s_2,s_3}+w_{s_4,s_5}+\cdots)\le w_{s_1,s_2}+w_{s_2,s_3}+\cdots $$ 所以这样拆之后权值和不会 $>r$。然后不断操作，最后一定拆成若干二元环且权值和 $\le r$，又因为这若干二元环肯定是一个完美匹配，所以就与 $k$ 是最小权完美匹配矛盾。 # 线性基 将长度为 $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$，定义 - 出度矩阵 $$ D^{\text{out}}_{i,j}(G)=\left\{\begin{matrix} \deg^{\text{out}}(i) & i=j \\ 0 & i\ne j \end{matrix}\right. $$ - 邻接矩阵，设 $\#e(i,j)$ 为 $i$ 连向 $j$ 的边数。 $$ A_{i,j}(G)=\left\{\begin{matrix} 0 & i=j \\ \#e(i,j) & i\ne j \end{matrix}\right. $$ - 出度 Laplace 矩阵 $$ L^{\text{out}}(G)=D^{\text{out}}(G)-A(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 公式 $n$ 个点的完全图生成树数量为 $n^{n-2}$，写出 Laplace 矩阵，用行列式知识可以得到。 ### 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)$ 次，去重后便得到上式。 可以感性理解方案与欧拉回路间构成双射。