线性代数

基础知识

行列式

一个 (n) 阶行列式可以写作一个 (n imes n) 的数表，其中数表的第 (i) 行第 (j) 列的元素可以用下标 (ij) 来表示，例如

[left|egin{array}{} a_{11} & a_{12} & a_{13} & cdots & a_{1n}\ a_{21} & a_{22} & a_{23} & cdots & a_{2n}\ cdots & cdots & cdots & ddots &cdots\ a_{n1} & a_{n2} & a_{n3} & cdots & a_{nn} end{array} ight| ]

为了定义行列式的值，我们先定义排列

排列

由 (1,2,dots,n(nge 2)) 组成的有序数组称 (n) 阶排列，通常用 (i_1,i_2,dots,i_n) 来表示。

我们用排列中的逆序对数量来定义排列的奇偶性，有奇数个逆序对的排列是奇排列，记做 (sgn(i_1i_2dotsi_n)=-1) ，否则为偶排列，记做 (sqn(i_1i_2dots i_n))

性质
1. 任意交换任意两个位置的数改变排列的奇偶性
2. 在所有 (n) 阶排列中，奇偶排列数量相等

行列式的定义

一个 (n) 阶行列式的值定义为

[egin{aligned} left|egin{array}{} a_{11} & a_{12} & a_{13} & cdots & a_{1n}\ a_{21} & a_{22} & a_{23} & cdots & a_{2n}\ cdots & cdots & cdots & ddots &cdots\ a_{n1} & a_{n2} & a_{n3} & cdots & a_{nn} end{array} ight| end{aligned}=sum_{i_1i_2dots i_n}(-1)^{sqn(i_1i_2dots i_n)}a_{1i_1}a_{2i_2}dots a_{ni_n} ]

上三角行列式

[egin{aligned} left|egin{array}{} a_{11} & a_{12} & a_{13} & cdots & a_{1n}\ 0 & a_{22} & a_{23} & cdots & a_{2n}\ 0 & 0 & a_{33} & cdots & a_{2n}\ cdots & cdots & cdots & ddots &cdots\ 0 & 0 & 0 & cdots & a_{nn} end{array} ight| end{aligned}=prod_{i=1}^n a_{ii} ]

代入定义式即可验证

行列式的性质

行列互换不改变行列式的值
用一个数乘行列式的某一行等于用这个数乘该行列式
将行列式中某一行写作两组数的和，则这个行列式等于两个行列式之和
对换行列式两行的位置，行列式反号
如果行列式中有两行成比例，则行列式等于0
把行列式一行的某个倍数加到另一行，行列式的值不变

这些性质都很 trivial ，比较好证。于是我们可以用高斯消元的方法把矩阵消除上三角并计算行列式，复杂度 (O(n^3))

拉普拉斯展开

设 (A) 是一个 (n) 阶方阵，我们直接用 (|A|) 来记其对应的行列式。

(M_{ij}) 表示矩阵 (A) 删去第 (i) 行第 (j) 列后 (n-1) 阶方阵对应的行列式的值，称为 (A) 的余子式。

拉普拉斯展开定理（在后面线性递推的推导中需要使用）

(forall 1le ile n) ，有 (|A|=sum_{1le jle n} (-1)^{i+j}a_{ij}M_{ij})

生成树计数

矩阵树定理

定义无重边无自环的无向图 (G) 的度数矩阵为 (D(G)=left{egin{aligned}&d_i,i=j\&0,i ot=jend{aligned} ight.) ，邻接矩阵为 (A(G)=E(i,j))。

其中 (d_i) 表示点 (i) 的度数，(E(i,j)) 表示 (i,j) 之间是否有边

事实上，可以有重边，但不能有自环，自环需要先删去，这点在证明过程中会说明

定义 (K(G)=D(G)-A(G)) ，称为图 (G) 的基尔霍夫矩阵

矩阵树定理

对于一个无向图 (G) ，(G) 的不同生成树个数等于其基尔霍夫矩阵 (K(G)) 的任意一个主余子式的绝对值。

主余子式：矩阵 (A) 去掉第 (i) 行第 (i) 列后方阵对应的余子式，即 (M_{ii})

关于任意性，之后也会提到原因。

下面介绍一些东西，并借助Cauchy-Binet证明矩阵树定理

基尔霍夫矩阵的行列式

对 (n) 个点无向图 (G) 的基尔霍夫矩阵 (K(G)) ，显然有 (forall iin n,sum_{1le jle n}K_{i,j}=0) ，也就是 (K(G)) 的行和为 (0)

模拟高斯消元的过程，我们发现我们的操作仅仅是将某一行乘上一个数并加给另一行，这样并不改变行和

而高斯消元的最后，第 (n) 行的元素前 (n-1) 列已经被消成 (0) ，而又要保证行和为 (0) ，因此 (k_{nn}=0) ，矩阵的行列式为 (0)

因此，我们得到了任意无向图的基尔霍夫矩阵的 (|K(G)|=0)

不连通图的基尔霍夫矩阵

这里讨论的是基尔霍夫矩阵的主余子式

若我们交换图 (G) 的两个点的标号，对应 (K(G)) 的改变是交换两行两列，不改变行列式

因此可以将每个连通子树的序号排列到一起去，(K(G)) 就变成了分块矩阵的样子

[left|egin{array}{} G_{11} & 0 & 0 & cdots & 0\ 0 & G_{22} & 0 & cdots & 0\ 0 & 0 & G_{33} & cdots & 0\ cdots & cdots & cdots & ddots &cdots\ 0 & 0 & 0 & cdots & G_{mm} end{array} ight| ]

(0) 是 (0) 矩阵，(G_{ii}) 是每个连通块矩阵

显然有，(|K(G)|=|G_{11}||G_{22}|dots|G_{mm}|)

可以发现，删去一行一列后，只将一个 (G_{ii}) 变为非 (0) ，因此 (K(G)) 的主余子式一定为 (0)

树的基尔霍夫矩阵

考虑 (K(G)) 的任意主余子式 (M_{rr}) ，将 (r) 视为树的根，将点按照深度从大到小重新标号，深度相等的点随意，这样根就在第 (n) 行

然后我们模拟高斯消元的过程，可以发现实际上每个点会消掉父亲点的一个度数。而每个点度数最终都被消成了 (1) ，因此主对角线全是 (1)，而没有父亲的根就被我们直接删去了

因此 (|M_{rr}|=1)

边矩阵

设图 (G=(V,E)) ，其中 (|V|=n,|E|=m) ，设 (G) 的边矩阵为 (B) ，这是一个 (m) 行 (n) 列的矩阵，其中第 (i) 行描述 (G) 的第 (i) 条边 ((u_i,v_i)) ，(B) 中元素 (b_{i,u_i}=1,b_{i,v_i}=-1)，其余元素为 (0) (这个定向是任意的)

可以代入验证基尔霍夫矩阵 (K(G)=B^TB)

[egin{aligned} K(G)_{ij}=sum_{k=1}^mb_{ik}b_{kj}=left{egin{aligned} &d_i,i=j\ &-1,(i,j)in E\ &0,otherwise end{aligned} ight. end{aligned} ]

同理可以验证 (M_{ii}=|(B_i)^TB_i|)，其中 (B_i) 为把边矩阵 (B) 删去第 (i) 列后的矩阵

Cauchy-Binet定理

Cauchy-Binet定理：

[|AB|=sum_{|s|=n}|A_{s*}B_{*s}| ]

其中 (A) 为 (m imes n) 的矩阵，(B) 为 (n imes m) 的矩阵，(s) 是一个下标的集合，(A_{s*}) 表示只选取 (s) 中的行形成的方阵，(B_{*s}) 表示只选取 (s) 中的列形成的方阵

矩阵树定理

由 Cauchy-Binet 定理可得

[M_{ii}=|(B_i)^TB_i|=sum_{|s|=n-1}|(B_{is*})^TB_{i*s}| ]

其中 ((B_{is*})^TB_{i*s}) 就是恰好选中 (s) 的 (n-1) 条边时构成的图的主余子式，当且仅当它们构成的图是树时，((B_{is*})^TB_{i*s}=1) ，否则 ((B_{is*})^TB_{i*s}=0)

有向图的情况

可以定义有向图 (G) 的度数矩阵 (D(G)) 表示每个节点的入度，定义有向图 (G) 的邻接矩阵 (A(G)) ，其中 (a_{ij}) 描述从 (i) 到 (j) 的边，则对于基尔霍夫矩阵 (K(G)=D(G)-A(G)) ，主余子式 (M_{rr}) 同样表示以 (r)

为根的有向生成树数量。

定义有向图 (G=(V,E)) 的边矩阵 (S) 和 (T) ，对于 (G) 的第 (i) 条边 ((u_i,v_i)) , 定义 (s_{i,u_i}=1) ，且 (t_{i,v_i}=s_{i,v_i}=-1) ，可以验证 (K(G)=S^TT)

剩下的证明过程类似

生成树边权乘积和

实际上，若无向图 (G) 每个边边权为 (v)，使用矩阵树定理求得的实际上是下式

[sum_Tprod_{E(i,j) in T} v_{i,j} ]

线性递推

学屁，不学了