觉得很有意思……开始不务正业。
行列式定义
很基本也很重要，感性理解就是通过类似容斥的方式计算了一个 \(n\) 维体的体积或者说缩放率？
如果 \(A\) 中有若干条行向量/列向量线性相关体积自然是 \(0\)。或者说可以用下面的交换性和倍加性消元。
行列式几个简单性质
可以在网上搜证明。
可乘性：
可倍加性：一行加上另一行的若干倍值不变。
行/列交换性：交换两行/两列值取反。
可转置性：转置后值不变。
可加性：
对任意一行都有类似的展开方式。
拉普拉斯展开：对于第 \(i\) 行，先按可加性拆开拆成该行只有一个元素有值的 \(n\) 个行列式之和。将这个元素 \(a_{i,j}\) 通过行/列交换性挪到左上角，此时符号变了 \((-1)^{i+j}\)。那么由于该行其它元素都是 \(0\)，所以行列是定义中 \(p_1\) 只能取 \(1\)，剩下的就是一个 \(n-1\) 阶矩阵的行列式，即：
\(A_{i,j}\) 被称为 \(i,j\) 处的余子式，方阵被去掉了第 \(i\) 行第 \(j\) 列的行列式。
LGV 引理
给定有向图 \(G\)，每条边有权值 \(e_{u,v}\)，定义一条路径 \(P:u\to v\) 的权值 \(\omega(P)\) 为其经过的所有边的权值之积，定义两个点间的权值 \(\omega(u,v)=\sum_{P:u\to v} \omega(P)\)。
大多数情况下边的权值都可以理解成边的重数，\(\omega\) 可以直接理解为路径的方案数。然而 LGV 引理和下面的矩阵树定理在交换环上成立，所以我们可以把边权换成诸如多项式之类的奇怪东西。（省选联考考过这个套路）
定义大小为 \(n\) 起点集合和终点集合间的路径组 \(P'=(P_1,P_2,\cdots,P_n)\) 为存在一个排列 \(\sigma\) 满足 \(P_i:S_i\to T_{\sigma(i)}\)，由这个路径组确定的 \(\sigma\) 我们记为 \(\sigma(P')\)。路径组的权值 \(\omega(P')=\prod_{i=1}^n \omega(P_i)\)。若 \(P'\) 中有两条路径有公共点那么称 \(P'\) 为相交路径组。
LGV 引理讲的是：
简要证明：
对于相交路径组，我们考虑构造变换 \(f(x)\)，我们取出 \(P'\) 中字典序最小的两条相交路径有序路径对 \((P_i,P_j)\)，找到字典序最小的点对 \((x,y)\) 满足 \(P_i\) 的第 \(x\) 个顶点与 \(P_j\) 第 \(y\) 个顶点相同。
我们交换 \(P_i\) 在 \(x\) 后面和 \(P_j\) 在 \(y\) 后面的路径，此时两个终点互换，\(\text{inv}(\sigma(P'))\) 取反。而由于字典序最小元的唯一性，我们发现 \(f(f(P'))=P'\)。那么相交排列成对出现，一个奇排列一个偶排列正好抵消。引理得证。
Binet-Cauchy 定理
更有趣的东西来了！由于行列式代表体积/缩放率，复合两个线性映射那么缩放率相乘，有对于同阶方阵 \(|AB|=|A||B|\)，我们考虑扩展这个结论。
对于一个 \(n\times m\) 的矩阵 \(A\) 和一个 \(m\times n\) 的矩阵 \(B\)，有：
其中 \(A_{S,T}\) 是 \(A\) 矩阵选出 \(S\) 中的行与 \(T\) 中的列构成的矩阵。
第一个 case 是映射 \(A\) 将一个 \(n\) 维向量压缩到 \(m\) 维，一定会丢失 \(n\) 维中的信息，于是再用 \(B\) 映射回 \(n\) 维时伸缩律为 \(0\)。
第二个 case 是一个特殊情况，我们考虑直接验证第三个 case。
施工中……