觉得很有意思……开始不务正业。
行列式定义
\[|A|=\sum_p (-1)^{\text{inv}(p)} \prod_{i=1}^n a_{i,p_i} \]很基本也很重要，感性理解就是通过类似容斥的方式计算了一个 \(n\) 维体的体积或者说缩放率？
如果 \(A\) 中有若干条行向量/列向量线性相关体积自然是 \(0\)。或者说可以用下面的交换性和倍加性消元。
行列式几个简单性质
可以在网上搜证明。
可乘性：
可倍加性：一行加上另一行的若干倍值不变。
行/列交换性：交换两行/两列值取反。
可转置性：转置后值不变。
可加性：
\[\begin{vmatrix} a_{1,1}+b_{1,1} & \cdots & a_{1,n}+b_{1,n}\\ a_{2,1} & \cdots & a_{2,n} \\ \vdots & \ddots & \vdots \\ a_{n,1} & \cdots & a_{n,n} \\ \end{vmatrix} = \begin{vmatrix} a_{1,1} & \cdots & a_{1,n}\\ a_{2,1} & \cdots & a_{2,n} \\ \vdots & \ddots & \vdots \\ a_{n,1} & \cdots & a_{n,n} \\ \end{vmatrix} + \begin{vmatrix} b_{1,1} & \cdots & b_{1,n}\\ a_{2,1} & \cdots & a_{2,n} \\ \vdots & \ddots & \vdots \\ a_{n,1} & \cdots & a_{n,n} \\ \end{vmatrix} \]对任意一行都有类似的展开方式。
拉普拉斯展开：对于第 \(i\) 行，先按可加性拆开拆成该行只有一个元素有值的 \(n\) 个行列式之和。将这个元素 \(a_{i,j}\) 通过行/列交换性挪到左上角，此时符号变了 \((-1)^{i+j}\)。那么由于该行其它元素都是 \(0\)，所以行列是定义中 \(p_1\) 只能取 \(1\)，剩下的就是一个 \(n-1\) 阶矩阵的行列式，即：
\[|A|=\sum_{j=1}^n a_{i,j} (-1)^{i+j} A_{i,j} \]\(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 引理讲的是：
\[\sum_{P' \text{是不相交路径组}} (-1)^{\text{inv}(\sigma(P'))} \omega(P')= \begin{vmatrix} \omega(S_1,T_1) & \omega(S_1,T_2) & \cdots & \omega(S_1,T_n) \\ \omega(S_2,T_1) & \omega(S_2,T_2) & \cdots & \omega(S_2,T_n) \\ \vdots & \vdots & \ddots & \vdots \\ \omega(S_n,T_1) & \omega(S_n,T_2) & \cdots & \omega(S_n,T_n) \end{vmatrix} \]简要证明：
\[\begin{vmatrix} \omega(S_1,T_1) & \omega(S_1,T_2) & \cdots & \omega(S_1,T_n) \\ \omega(S_2,T_1) & \omega(S_2,T_2) & \cdots & \omega(S_2,T_n) \\ \vdots & \vdots & \ddots & \vdots \\ \omega(S_n,T_1) & \omega(S_n,T_2) & \cdots & \omega(S_n,T_n) \end{vmatrix} =\sum_p (-1)^{\text{inv}(p)} \prod_{i=1}^n \omega_{S_i,T_{p_i}}=\sum_{P' \text{是不相交路径组}} (-1)^{\text{inv}(\sigma(P'))} \omega(P')+\sum_{P' \text{是相交路径组}} (-1)^{\text{inv}(\sigma(P'))} \omega(P') \]对于相交路径组，我们考虑构造变换 \(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\)，有：
\[|AB|= \begin{cases} 0 & n>m \\ |A||B| & n=m\\ \sum_{S\subset \{1,2,\cdots,m\}} |A_{\{1,2,\cdots,n\},S}| |B_{S,\{1,2,\cdots,n\}}| & n<m \end{cases} \]其中 \(A_{S,T}\) 是 \(A\) 矩阵选出 \(S\) 中的行与 \(T\) 中的列构成的矩阵。
第一个 case 是映射 \(A\) 将一个 \(n\) 维向量压缩到 \(m\) 维，一定会丢失 \(n\) 维中的信息，于是再用 \(B\) 映射回 \(n\) 维时伸缩律为 \(0\)。
第二个 case 是一个特殊情况，我们考虑直接验证第三个 case。
方法一
常规证法。
我们构造两个分块矩阵的行列式 \(\begin{vmatrix} A&O\\ -I&B \end{vmatrix}\) 和 \(\begin{vmatrix} O&AB\\ -I&B \end{vmatrix}\)。\(O\) 是零矩阵，\(I\) 是单位矩阵。
施工中……
标签：图论,text,路径,vmatrix,cdots,线性代数,vdots,omega,小记 From： https://www.cnblogs.com/yyyyxh/p/linear_algebra_with_graph.html