线性相关
若有 \(\mathbb{a}=\{a_1,a_2,\dots,a_n\}\)，且 \(x\mathbb{a}=0\)，那么这组向量线性相关。
大致可以理解成有一些无用的方程。
一组可以表示原来所有线性组合的向量叫做一组基。
如果值域只有 \(0/1\)，那这就是异或线性基。
否则，上高消就可以搞出一组这样的基。
异或线性基
可以求一堆东西异或起来的最大值，求区间的这玩意（可持久化+贪心选靠后下标）。
合并线性基
直接插入，\(O(\log^2)\)。
- 可结合线段树分治。
矩阵的秩
可以理解成最终高消完还剩下几个。代表了表示空间的维数。
初等变换不影响矩阵的秩（交换两行，一行乘 \(k\)，一行乘 \(k\) 加到另一行）。
逆矩阵
同逆元定义，相乘等于单位矩阵的矩阵。
求法
高斯-约旦消元。右边拼一个单位阵，把左边消成单位阵，如果满秩，右边就是逆矩阵。
行列式
递归定义……咕咕咕。
求法
初等变换对行列式值的影响：
-
交换：取反。
-
乘 \(k\)：乘 \(k\)
-
乘 \(k\) 加到另一行：不变。
高消，成上三角，主对角线相乘，符号取决于交换的次数。
如果模数非质，可以使用辗转相除法。
int f=1,ans=1;
for(int i=1;i<n;++i){
int p=i;
for(int j=i+1;j<n;++j){
if(a[j][i]>a[p][i]) p=j;
}
if(!a[p][i]) return 0;
if(i!=p) swap(a[i],a[p]),f^=1;
for(int j=i+1;j<n;++j){
if(a[j][i]>a[i][i]) swap(a[j],a[i]),f^=1;
while(a[j][i]){
int d=a[i][i]/a[j][i];
for(int k=1;k<n;++k) a[i][k]=(a[i][k]+mod-a[j][k]*d%mod)%mod;
swap(a[i],a[j]),f^=1;
}
}
ans=ans*a[i][i]%mod;
}
return f?ans:(mod-ans)%mod;
应用
Matrix-Tree 定理
求一个图所有生成树边权之积的和，当边权为 \(1\) 时，即求生成树个数。
构造矩阵
度数矩阵-邻接矩阵。广义地，度数是所连边权和，邻接是两点间边权和。
对于有向图，求内向生成树就是记出度和出边（可以认为每个人都要出 \(1\) 条边）；求外向生成树就是记入度和入边（可以认为每个人都要入 \(1\) 条边）。
Lindström–Gessel–Viennot 引理
DAG 上求起点集合到终点集合不相交路径的带符号乘积和。
构造矩阵
\[A_{i,j}=S_i\rightarrow T_j\text{每一条路径边权的乘积和} \]有点高级，但是有一个简单的部分应用。边权为 \(1\) 即带符号方案数。
符号的来源是起点与终点配对关系 \(S_i\rightarrow T_{p_i}\)，答案中，\(p\) 的逆序对个数奇偶性决定了它的符号 \((-1)^{cnt}\)。
在网格图上划线（单调），就没有符号了，可以直接套板子，但是起点和终点若相同则需偏移。因为交换了之后不合法，正好是要减去的。
此外，一部分题目可以通过分析性质来直接套版，如 [NOI2021] 路径交点。
标签：高消,int,边权,矩阵,异或,线性代数,可以 From： https://www.cnblogs.com/mRXxy0o0/p/17973603