行列式、矩阵求逆、矩阵树定理 学习笔记

· · 个人记录

可能有些东西不需要，有些东西漏了，先记录了再说。

这是剩余部分内容

行列式的定义：

一个 n 阶的行列式 ：D=\det(A)=|A|=\left|\begin{array}{cccc}a_{11} & a_{12} &… &a_{1n} \\ a_{21} &a_{22} & … &a_{2n} & \\ … &… &… &… &\\ a_{n1} &a_{n2} &… & a_{nn} & \end{array}\right|

有 |A|=\sum_{\sigma}(-1)^{\text{sgn}(\sigma)}\prod_i a_{i\sigma_i} 。\sigma 是一个排列，\text{sgn}(\sigma) 表示 \sigma 中的逆序对数量。理解：把在行列式中按照行从小到大每一行都取一个数，把他们乘起来的值按照取的位置的逆序对数确定的符号加起来。所以硬算大概要算 n! 项。

其中主对角线：a_{11},a_{22},…,a_{nn}，次对角线： a_{n1},a_{(n-1)2},…,a_{1n}。

--- 性质： 1. $\det(A)=\det(A^T)$ ，可以理解为行列式中，行和列地位是对等的。（性质中对行适用的对列同样适用，以下可简叙述为行）。 2. 交换 $A$ 中的两行，得到 $B$ 有 $\det(B)=-\det(A)$。在序列中交换两数，该序列的逆序对数奇偶性转变，所以当交换行列式中的两行时，$(-1)^{sgn(\sigma)}$ 的符号将会改变，即整体变成负的。 3. 若 $A$ 中有 $A_i=A_j$ 两行相等，则 $\det(A)=0$。交换 $i,j$ 根据性质二可知 $\det(A)=-\det(A)\to\det(A)=0$。 4. 行列式中某一行的元素都 $\times k$ ，行列式的值变为原来的 $k$ 倍。（根据定义容知）。 5. 行列式中两行对应成比例，则 $\det(A)=0$。根据性质 $3,4$ 可简单推得。特别的，若有一行全部为 $0$ 那么 $\det(A)=0$。 6. 一个行列式可以拆成两个行列式之和。这两个行列式与原行列式只有一行不同，且两个行列式那行上对应位置的和为原行列式对应的位置。这个性质的表述有些复杂，举例说明： $\left|\begin{array}{cccc}a_{11} & a_{12} &… &a_{1n} \\ a_{21} &a_{22} & … &a_{2n} & \\ … &… &… &… &\\ a_{i1}&a_{i2} &… &a_{in} &\\ … &… &… &… &\\ a_{n1} &a_{n2} &… & a_{nn} & \end{array}\right| = \left|\begin{array}{cccc}a_{11} & a_{12} &… &a_{1n} \\ a_{21} &a_{22} & … &a_{2n} & \\ … &… &… &… &\\ b_{i1}&b_{i2} &… &b_{in} &\\ … &… &… &… &\\ a_{n1} &a_{n2} &… & a_{nn} & \end{array}\right| + \left|\begin{array}{cccc}a_{11} & a_{12} &… &a_{1n} \\ a_{21} &a_{22} & … &a_{2n} & \\ … &… &… &… &\\ c_{i1}&c_{i2} &… &c_{in} &\\ … &… &… &… &\\ a_{n1} &a_{n2} &… & a_{nn} & \end{array}\right|$ ，其中 $a_{ij}=b_{ij}+c_{ij}$。 7. 行列式某一行乘以一个数然后加到另一行上， 行列式的值不变。根据性质 7 可以得到行列式计算的简便方法：把行列式转换成上三角行列式或这下三角行列式（注：这里的上三角和下三角都是包含主对角线的，否则算行列式的时候要加上符号）。 这个过程和高斯消元解方程组类似，$O(n^3)$ 得到行列式的值。 --- 行列式按行展开： $D=\sum_j a_{ij} \times A_{ij} $ 。即行列式的值为某一行元素值和该元素代数余子式的乘积的和。(这里的 $A$ 好像重名了，不管了，反正代数余子式就是应该叫 $A_{ij}$)。 在 $n$ 阶行列式中，把所在的第 $i$ 行与第 $j$ 列划去后，所留下来的 $n-1$ 阶行列式叫元的余子式。记作 $M_{ij}$。 记 $A_{ij}$ 为元素 $a_{ij}$ 的代数余子式。 则 $A_{ij}=M_{ij} \times (-1) ^{i+j}$ 。（如果换成 $k$ 阶子式的代数余子式，那么同样成立，称为拉普拉斯定理）。 相似的 ： $0=\sum_ka_{ik}\times A_{jk}$ 其中 $(i\not=j)$ ，就是 某行的元素与别的行的代数余子式相乘 得 $0$。可以根据按行展开和性质 3 证明。 --- 乘法: 对于两个 $n\times n$ 的矩阵 $A,B$ ，有 $\det(A\times B)=\det(A)\times \det(B)$。 --- 范德蒙德行列式 ：有 $a_{i,j}=x_i^{j-1}$ ，则有 $\det(A)=\prod_{1\leq j< i \leq n }(x_i-x_j)$。(直接消元变成更小的行列式即可归纳得)。 奇数阶反对称行列式等于 $0$. --- $\text{Cramer}$ 法则：将行列式和多元线性方程组相对应，复杂度高的离谱。 --- ~~矩阵基础部分总没有人不会吧。~~ 逆矩阵：$A,B$ 均为 $n$ 阶矩阵，若 $A\times B=B\times A=E$ 则称 $B$ 为 $A$ 的逆矩阵 $B=A^{-1}$。其中 $E$ 为 $n$ 阶单位矩阵。 由行列式的乘法可知 $\det(A)\times \det(B)=\det(A\times B)=\det(E)=1$ 若 $\det(A)=0$ 则矩阵 $A$ 显然不存在逆矩阵。并且 $\det(A)=0$ 和 $A$ 可逆互为充要条件。 逆矩阵的性质： 1. 若 $A,B$ 均可逆，则 $A\times B$ 可逆，且 $(A\times B)^{-1}=B^{-1}\times A^{-1}$ 。(根据性质拆开即可)。 1. 若 $A$ 可逆，则 $A^T$ 可逆，且 $(A^T)^{-1}=(A^{-1})^T$，若 $k \not = 0$，则有 $(kA)^{-1}=\frac{1}{k} A^{-1}$。 求法 1 ：伴随矩阵法。 伴随矩阵：只有方阵才有伴随矩阵。且所有方阵的伴随矩阵都存在。 将原矩阵所有的元素的代数余子式值放入一个新的矩阵中，然后对其求转置，即为原矩阵的伴随矩阵。 $A^*=\left[\begin{array}{cccc}A_{11} & A_{21} &… &A_{n1} \\ A_{12} &A_{22} & … &A_{n2} & \\ … &… &… &… &\\ A_{1n} &A_{2n} &… &A_{nn} & \end{array}\right]$ ，（ $A_{ij}$ 表示的是代数余子式）。 定理： $A\times A^*=A^*\times A=\det(A)E$。根据矩阵乘法的定义和行列式按行展开即可。并且 $\det(A^*)=\det(A)^{n-1}$ （两边同时取 $\det$ 即可推出）。 然后根据伴随矩阵的定理，有 $A\times (\frac{1}{\det(A)}A^*)=E ,(\det(A)\not = 0)$ ，复杂度 $O(n^5)$。 求法 2 ：待定系数法。 直接设 $n^2$ 个未知数 ，时间复杂度 $O(n^6)$ 。 求法 3：初等变换。 三种初等变换：（行的操作列也彳亍） 1. 交换两行。 1. 用 $k(k\not=0)$ 乘某一行。 1. 某一行的 $l $ 倍加到某一行上。 定理 1 ：任何矩阵通过初等变换都可以变成标准型。 标准型：矩阵只在左上角有一串连续的 $1$。经过初等变换后的标准型中的连续的 $1$ 的个数也可以称为矩阵的秩。$A$ 可逆 $\Leftrightarrow$ $A$ 的标准型为 $E$ 。 若 $A$ 只经过初等变换变成矩阵 $B $ ，则称这两个矩阵是等价的。写作 $A \cong B$。 我们记对 $E $ 做一次初等变换得到的方阵为初等方阵。 1. 初等方阵的逆和转置也是初等方阵。 1. 初等方阵左乘一个矩阵等于对这个矩阵做一次同种的初等行变换。 1. 初等方阵右乘一个矩阵等于对这个矩阵做一次同种的初等列变换。 定理 2： 矩阵 $A$ 可逆 $\Leftrightarrow$ $A=\prod_i Q_i $ 其中 $Q_i$ 为初等矩阵。 最后我们根据两个式子 ：（这里只看了初等行变换） $$ Q_1 Q_2 …Q_t \ A=E \ \ \ \ $$ $$Q_1 Q_2 …Q_t \ E=A^{-1}$$ 用初等变换将 $A$ 转换为 标准型，同时对 $E$ 也做相同的变换，那么当 $A$ 变成标准型时， $E$ 最后将变成 $A^{-1}$。（前提是可逆）。这个玩意可以用高斯消元实现，升至不用变形，复杂度 $O(n^3)$。 --- 矩阵树定理： 对于一个无向图 $G = (V, E)$，其中 $|V| = n$（点数）， $|E| = m$（边数）： 给 $G$ 的每条边任意分配一个方向，则它的关联矩阵（大小为 $m \times n$ ） $B$： $b_{i, j} = \begin{cases} 1 & \text{点}\ j\ \text{是边}\ i\ \text{的起点} \\ -1 & \text{点}\ j\ \text{是边}\ i\ \text{的终点} \\ 0 & \text{其他}\end{cases} $l_{i, j} = \begin{cases} d_i & i = j \\ -e_{i, j} & i \neq j\end{cases}

（其中 d_i 表示 i 号点的出度， e_{i, j} 连接点 i, j 的边的数量，也可简单的看做度数矩阵减去邻接矩阵）。

性质：如果把矩阵树定理当做已知，那么 2,3,4 定理就比较一眼

  3. 若不连通 则 \forall i,M_{i,j}=0 （可以把每个连通块交换到一起，然后每一个部分可以搞出一个全零行，若只划掉一行则仍然剩下若干全零行）。

  4. 若 G 是树 则 \forall i,M_{i,j}=1。

定理：神x义x写的组合解释

对于无向图 G=(V,E)，有 \forall i ,M_{i,i} 的值等于图的生成树个数。（什么？你问我要证明？你没发现前面的一些性质/定理也是没有证明的吗？）