代数余子式

给定 $n$ 阶方阵 $A=(a_{ij})$, 定义 $a_{ij}$ 的余子式 $M_{ij}$ 为 $A$ 划去第 $i$ 行第 $j$ 列后的行列式，$a_{ij}$ 的代数余子式 $A_{ij}=(-1)^{i+j}M_{ij}$.

代数余子式可以用于行列式的求值，比如按第 $r$ 行展开：

$$egin{equation}det A=sum_{c=1}^na_{rc}A_{rc}end{equation}$$

按第 $c$ 列展开是同理的。

伴随矩阵

定义

在 $(1)$ 式中，如果把 $a_{rc}$ 中的 $r$ 替换成 $i
e r$, 则该乘积对应了将 $A$ 的第 $i$ 行替换成第 $r$ 行后的行列式——该行列式有两行相等，所以它等于 $0$.

所以我们有 $sum_{c=1}^na_{ic}A_{jc}=det A cdot [i=j]$, 把它写成矩阵乘法就是：

$$A(A_{ij})^{mathrm T}=det A cdot I_n$$

我们定义 $A^*=(A_{ij})^{mathrm T}$ 是 $A$ 的伴随矩阵。

同样的结论对列也成立，所以 $AA^*=A^*A=det A cdot I_n$.

计算

如果 $mathrm r(A)=n$, 用高斯消元法分别求出 $det A$ 和 $A^{-1}$, $A^*=det A cdot A^{-1}$. 

如果 $mathrm r(A) le n-2$, $A$ 的任意 $n-1$ 阶子式都为 $0$, 所以 $A^*=O$.

如果 $mathrm r(A)=n-1$:

20200628更新：更正了一些细节，感谢Rose_Max指出错误。

假设 $A$ 的列向量组为 $vec c_1, vec c_2, ldots, vec c_n$.

由它们线性相关，可知存在不全为 $0$ 的实数 $q_1, q_2, ldots, q_n$ 满足 $sum_{i=1}^nq_ivec c_i=vec 0$. 不妨设 $q_c
e 0$.

考虑同行两余子式 $M_{ri}$ 和 $M_{rc}$ 的关系，不妨讨论 $i<c$ 的情况，$i>c$ 类似。不难发现，如果我们将 $M_{ri}$ 的第 $i$ 至 $c-2$ 列向右推移，而第 $c-1$ 列移动到第 $i$ 列，唯一的不同点是 $M_{ri}$ 的第 $i$ 列为 $vec c_c$ 删去第 $r$ 行， $M_{rc}$ 的第 $i$ 列为 $vec c_i$ 删去第 $r$ 行。

联系上述线性相关式，可设 $M’$ 表示在 $M_{ri}$ 进行推移的基础上，把第 $i$ 列乘以 $q_c$, 并与 $M_{rc}$ 的第 $i$ 列的 $q_i$ 倍相加，所得到的 $n-1$ 阶行列式。

那么 $M’=q_c(-1)^{c-i}M_{ri}+q_iM_{rc}$.

最后，将 $M’$ 的第 $i$ 列依次加上其对应“原行列式的第 $j
otin{i, c}$ 列”的列的 $q_j$ 倍。

这样，$M’$ 的值不变，而第 $i$ 列全为 $0$. 这说明了 $q_c(-1)^{c-i}M_{ri}+q_iM_{rc}=M’=0$.

上述过程比较抽象，举一例说明。

例如，原矩阵为

$$egin{pmatrix}1&5&5\-3&3&6\0&6&7end{pmatrix}$$

其列向量组为

$$vec c_1=egin{pmatrix}1\-3\0end{pmatrix}, vec c_2=egin{pmatrix}5\3\6end{pmatrix}, vec c_3=egin{pmatrix}5\6\7end{pmatrix}$$

它们满足关系式 $5vec c_1-7vec c_2+6vec c_3=vec 0$.

考虑其余子式 $M_{11}$ 与 $M_{12}$:

$$M_{11}=egin{vmatrix}3&6\6&7end{vmatrix}, M_{12}=egin{vmatrix}-3&6\0&7end{vmatrix}$$

把 $M_{11}$ 的第 $1$ 列翻 $-7$ 倍，与 $M_{12}$ 的第 $1$ 列的 $5$ 倍相加：

$$-7M_{11}=egin{vmatrix}-21&6\-42&7end{vmatrix}$$

$$5M_{12}=egin{vmatrix}-15&6\0&7end{vmatrix}$$

$$-7M_{11}+5M_{12}=M’=egin{vmatrix}-36&6\-42&7end{vmatrix}$$

把 $M’$ 的第 $2$ 列翻 $6$ 倍加到第 $1$ 列得：

$$M’=egin{vmatrix}0&6\0&7end{vmatrix}=0$$

所以

$$q_cA_{ri}-q_iA_{rc}=(-1)^{r+c}left(q_c(-1)^{c-i}M_{ri}-q_iM_{rc}ight)=0$$

即

$$A_{ri}=frac{q_i}{q_c}A_{rc}$$

同样的结论对列也成立。

于是对于列向量 $vec p=(p_1p_2 cdots p_n)^{mathrm T}$ 和行向量 $vec q=(q_1q_2 cdots q_n)$ 使得 $Avec p=vec 0$, $vec qA=vec 0$, 不妨设 $p_r, q_c
e 0$, 就有 $A_{ij}=frac{p_iq_j}{p_rq_c}A_{rc}$.

$vec p$ 与 $vec q$ 都可以通过高斯消元法解方程组解出，而代数余子式 $A_{rc}$ 也可以通过高斯消元法求出。

综上所述，求一个矩阵的伴随矩阵，时间复杂度为 $O(n^3)$.

应用

通过伴随矩阵，可以求出矩阵所有元素的余子式。

例 给定有向图，求每条边各含于多少棵以 $R$ 为根的所有生成内向树。

解 生成树计数的方法见这篇文章。

计算含有 $left<u, vight>$ 的生成内向树个数，相当于把 $u$ 的出边除了 $left<u, vight>$ 外全部删去后的生成内向树计数。

这就是把拉普拉斯矩阵的第 $u$ 行替换成仅有第 $u$ 项为 $1$, 第 $v$ 项为 $-1$ 的行，然后划去第 $R$ 行第 $R$ 列求余子式。

这等价于，拉普拉斯矩阵去掉第 $u, R$ 行、第 $u, R$ 列的余子式，减去去掉第 $u, R$ 行、第 $v, R$ 列的余子式。

将拉普拉斯矩阵去掉第 $R$ 行、第 $R$ 列作为矩阵 $A$, 那么就转化为求 $A$ 的所有余子式。

这里不用讨论那么多情况，因为 $mathrm r(A)<n$ 意味着不存在生成内向树。