[学习笔记] 行列式与矩阵树定理

行列式

线性代数真是好东西

定义

设 $n$ 阶方阵 $ A$ 的行列式为 $\det(A)$, 则:

其中 $P$ 为所有 $n$ 阶排列组成的集合, $\delta(p)$ 表示排列 $p$ 中的逆序对个数.

本质上是 $n$ 维欧氏空间应用线性变换 $A$ 后 $n$ 维超体积产生的变化系数.

性质

只说几个比较显然比较常用的好了…

1. $|A|=|A^T|$. (定义式并没有行和列的区别)

2. $|AB|=|A|\times|B|$. (从本质理解. 矩阵乘法相当于连续应用两个线性变换, 体积变化应该相乘.)

3. 行列式某一行/列都乘 $k$, 行列式值变为原来 $k$ 倍. (定义中的和式的每一项都恰好包含某一行中的一项, 于是刚好每一项都多了个 $k$.)

   $$ D={\begin{vmatrix}a_{11}&a_{12}&\dots &a_{1n}\\\vdots &\vdots &\dots &\vdots \\{\color {blue}k}a_{i1}&{\color {blue}k}a_{i2}&\dots &{\color {blue}k}a_{in}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\dots &a_{nn}\end{vmatrix}}={\color {blue}k}{\begin{vmatrix}a_{11}&a_{12}&\dots &a_{1n}\\\vdots &\vdots &\dots &\vdots \\a_{i1}&a_{i2}&\dots &a_{in}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\dots &a_{nn}\end{vmatrix}}={\color {blue}k}D_{1} $$

4. 行列式某两行/列线性相关, 则行列式值为 $0$. (从行列式的本质理解. 非满秩的矩阵会降维, 于是体积就被压没了.)

   $$ {\begin{vmatrix}{\color {blue}2}&{\color {blue}2}&\dots &{\color {blue}2}\\{\color {blue}8}&{\color {blue}8}&\dots &{\color {blue}8}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\dots &a_{nn}\end{vmatrix}}=0 $$

5. 交换行列式某两行/列, 行列式值变号. (定义式中的符号和逆序对有关.)

   $$ {\begin{vmatrix}\vdots &\vdots &\vdots &\vdots \\{\color {blue}{a_{i1}}}&{\color {blue}{a_{i2}}}&\dots &{\color {blue}{a_{in}}}\\{\color {green}{a_{j1}}}&{\color {green}{a_{j2}}}&\dots &{\color {green}{a_{jn}}}\\\vdots &\vdots &\vdots &\vdots \\\end{vmatrix}}=-{\begin{vmatrix}\vdots &\vdots &\vdots &\vdots \\{\color {green}{a_{j1}}}&{\color {green}{a_{j2}}}&\dots &{\color {green}{a_{jn}}}\\{\color {blue}{a_{i1}}}&{\color {blue}{a_{i2}}}&\dots &{\color {blue}{a_{in}}}\\\vdots &\vdots &\vdots &\vdots \\\end{vmatrix}} $$

6. 在行列式中, 某一行/列的每个元素是两数之和, 则此行列式可拆分为两个相加的行列式. (拆定义式, 把被更改的那一行中加起来的两个数拆开分配到两个和式中.)

   $$ {\begin{vmatrix}a_{11}&a_{12}&\dots &a_{1n}\\\vdots &\vdots &\dots &\vdots \\{\color {blue}{a_{i1}}}+{\color {green}{b_{i1}}}&{\color {blue}{a_{i2}}}+{\color {green}{b_{i2}}}&\dots &{\color {blue}{a_{in}}}+{\color {green}{b_{in}}}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\dots &a_{nn}\end{vmatrix}}={\begin{vmatrix}a_{11}&a_{12}&\dots &a_{1n}\\\vdots &\vdots &\dots &\vdots \\{\color {blue}{a_{i1}}}&{\color {blue}{a_{i2}}}&\dots &{\color {blue}{a_{in}}}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\dots &a_{nn}\end{vmatrix}}+{\begin{vmatrix}a_{11}&a_{12}&\dots &a_{1n}\\\vdots &\vdots &\dots &\vdots \\{\color {green}{b_{i1}}}&{\color {green}{b_{i2}}}&\dots &{\color {green}{b_{in}}}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\dots &a_{nn}\end{vmatrix}} $$

7. 结合性质 4/6 的推论: 某一行/列对位加上另一行/列的 $k$ 倍, 行列式值不变. (先用性质 6 拆成两个行列式, 然后第二个行列式显然不满秩所以值为 0.)

   $$ {\begin{vmatrix}\vdots &\vdots &\vdots &\vdots \\a_{i1}&a_{i2}&\dots &a_{in}\\a_{j1}&a_{j2}&\dots &a_{jn}\\\vdots &\vdots &\vdots &\vdots \\\end{vmatrix}}={\begin{vmatrix}\vdots &\vdots &\vdots &\vdots \\a_{i1}&a_{i2}&\dots &a_{in}\\a_{j1}{\color {blue}{+ka_{i1}}}&a_{j2}{\color {blue}{+ka_{i2}}}&\dots &a_{jn}{\color {blue}{+ka_{in}}}\\\vdots &\vdots &\vdots &\vdots \\\end{vmatrix}} $$

8. 上下三角矩阵/对角矩阵的行列式为对角线上元素之积. (显然除了对角线上的情况其他的排列 $p$ 都会造成 $A_{i,p_i}$ 命中至少一个0.)

   $$ {\begin{vmatrix}{\color {blue}{a_{11}}}&0&\dots &0\\0&{\color {blue}{a_{22}}}&\dots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\dots &\color {blue}{a_{nn}}\end{vmatrix}}=\prod_{k=1}^n\color {blue}{a_{kk}} $$

计算

按照定义算需要 $O(n\times n!)$ 次乘法. 没有应用价值. 考虑行列式的性质.

利用上面性质 5/7 即可计算对行列式应用初等行变换后对原行列式值产生的影响.

再加上性质 8, 我们只要用初等行变换把行列式消成三角阵就可以算了. 使用高斯消元即可解决. 时间复杂度 $O(n^3)$.

矩阵树定理

又称 Kirchhoff’s Theorem.

FAQ: 为啥搜索 Kirchhoff 只能找到一个物理学家?

A: 没错这个定理就是物理学家 Gustav R. Kirchhhoff 研究电路的时候顺手证的.

内容

一个 $n$ 个点的无向图 $G$ 的生成树个数即为它的 Laplacian 矩阵的任一余子式的行列式值.

其中 Laplacian 矩阵在 $A_{i,i}$ 处为点 $i$ 的度数, $A_{i,j}$ 处若点 $i$ 和 $j$ 邻接则值为 $-1$, 否则为 $0$.

或者说 Laplacian 矩阵等于度数矩阵减去邻接矩阵.

这个定理也适用于多重图(非简单图), 只要把所有自环都丢掉然后把 $-1$ 改为 $i$ 和 $j$ 之间边的个数的相反数就好了.

于是直接用就完了qaq…