矩阵树定理学习笔记

2024-02-17 23:26:16

全是在抄写 czy 的课件，其实也不是很全面和严谨。

矩阵行列式

定义

矩阵 $A$ 行列式记为 $\det(A)$ 或 $|A|$。

\[\det(A)=\sum_{\text{$p$ 为 $1\dots n$ 的全排列}}(-1)^{\text{$p$ 的逆序对数}}\prod_{i}A_{i,p_i} \]

性质

$A$ 中某一行（列）同乘 $k$，行列式乘 $k$。
$\det(A)=\det(A^T)$。
$A$ 交换两行（列），行列式乘 $-1$；
因为交换两行会使所有排列 $p$ 逆序对数 $+1$ 或 $-1$。
$A$ 中存在两行（列）相等，行列式为 $0$；
因为若 $r_1,r_2$ 两行相等，那么包含 $A_{r_1,i},A_{r_2,j}$ 的排列和包含 $A_{r_1,j},A_{r_2,i}$ 的排列一一对应，乘积相等，符号相反。
$A$ 中某一行（列）各元同乘一个数加到另一行（列）对应元上，行列式不变；
因为行列式是关于某一行（列）的线性函数，在其它行不变的情况下，某一行相加，行列式也就相加；
可以将 $A'$ 拆分成 $A$ 和一个行列式为 $0$ 的矩阵的和。

约定与定义

无向图（有向图）$G=(V,E)$。
$n=|V|$，$m=|E|$。
关联矩阵 $M(G)[n\times m]$：

\[M_{i,j}=\begin{cases} -1&\text{$v_i$ 是 $e_j$ 的起点}\\ 1&\text{$v_i$ 是 $e_j$ 的终点}\\ 0&\text{otherwise} \end{cases} \]

当 $G$ 为无向图时，每条边是随意定向的。

$M$ 的简约关联矩阵 $M_0[(n-1)\times m]$，是 $M$ 去掉最后一行得到的。
$M$ 的抽列矩阵 $M_0(S)[(n-1)\times (n-1)]$，其中 $S\subseteq E$ 是大小为 $n-1$ 的边集。
拉普拉斯矩阵 $L(G)[n\times n]$：

\[L_{i,j}=\begin{cases} -m_{i,j}&i\neq j,~\text{$i,j$ 之间有 $m_{i,j}$ 条边}\\ \mathrm{deg}(v_i)&i=j \end{cases} \]

Lemma I

\[M\times M^T=L \]

\[\begin{aligned} (M\times M^T)_{i,j}&=\sum_k M_{i,k}\times M^T_{k,j}\\ &=\sum_k M_{i,k}\times M_{j,k} \end{aligned} \]

若 $i\neq j$，$M_{i,k}\times M_{j,k}=-1\times [e_k\in E]$，所以 $\text{上式}=-m_{i,j}$；
若 $i=j$，$M_{i,k}\times M_{j,k}=(M_{i,k})^2=[e_k\in E]$，所以 $\text{上式}=\mathrm{deg}(v_i)$。

Lemma II

设 $S\subseteq E$，$|S|=n-1$，$G'=(V,S)$，则

\[\det(M_0(S))=\pm[\text{$G'$ 构成树}] \]

若 $G'$ 不构成树，那么 $M_0$ 会存在若干列线性相关，行列式为 $0$。

若 $G'$ 构成树：

取树上的点拓扑排序后前 $n-1$ 个点，记为 $u_1,u_2\dots u_{n-1}$，以及其对应边 $c_1,c_2,\dots c_{n-1}$。

交换 $M_0$ 的行，使得第一行对应 $u_1$，第二行对应 $u_2$……

交换 $M_0$ 的列，使得第一列对应 $c_1$，第二列对应 $c_2$……

此时 $M_0$ 变为下三角矩阵，主对角线乘积为 $\pm 1$，行列式为 $\pm 1$。

Binet-Cauchy 定理

设 $A[n\times m],B[m\times n]$，则

\[\det(A\times B)=\sum_{\substack{S\subseteq \{1,2,\dots m\}\\|S|=n}}\det(A[S])\times\det(B[S]) \]

其中 $A[S]$ 表示取出列集合为 $S$ 的子矩阵，$B[S]$ 表示取出行集合为 $S$ 的子矩阵。

太顶了，看不懂证明。

特别地，当 $A,B$ 是同阶方阵时，$\det(A\times B)=\det(A)\times \det(B)$。