从伴随矩阵到克莱姆法则

From Cofactor Matrix To Cramer's Rule

Posted by J Leaves on December 27, 2018

伴随矩阵法求逆

余子式与伴随矩阵

A是一个实系数的 n×n 矩阵。

\[\begin{equation} A = \left[ \begin{matrix} A_{11} & A_{12} & \cdots & A_{1n} \\ A_{21} & A_{22} & \cdots & A_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ A_{n1} & A_{n2} & \cdots & A_{nn} \end{matrix} \right] \end{equation}\]

A关于第i行第j列的余子式(记作\(M_{ij}\))是去掉A的第i行第j列之后得到的(n − 1)×(n − 1)矩阵的 行列式。
比如:A关于第1行第1列的余子式是

\[M_{11} = \left| \begin{matrix} A_{22} & A_{23} & \cdots & A_{2n} \\ A_{31} & A_{32} & \cdots & A_{3n} \\ \vdots & \vdots & \ddots & \vdots \\ A_{n1} & A_{n2} & \cdots & A_{nn} \end{matrix} \right|\]

A关于第i行第j列的代数余子式(记作\(C_{ij}\))是

\[C_{ij} = (-1)^{i+j}M_{ij}\]

A余子矩阵是一个n×n的矩阵C,使得其第i行第j列的元素是A关于第i行第j列的 代数余子式。

\[C = \left[ \begin{matrix} C_{11} & C_{12} & \cdots & C_{1n} \\ C_{21} & C_{22} & \cdots & C_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ C_{n1} & C_{n2} & \cdots & C_{nn} \end{matrix} \right]\]

A伴随矩阵(记作\(adj(A)\))是A的余子矩阵的 转置矩阵。

\[adj(A) = C^T = \left[ \begin{matrix} C_{11} & C_{21} & \cdots & C_{n1} \\ C_{12} & C_{22} & \cdots & C_{n2} \\ \vdots & \vdots & \ddots & \vdots \\ C_{1n} & C_{2n} & \cdots & C_{nn} \end{matrix} \right]\]

伴随矩阵求逆

一个等式的证明

首先,证明等式

\[\begin{equation} AC^T = det(A)I \end{equation} \tag{1}\]

证明:

\[\begin{equation} AC^T = \left[ \begin{matrix} A_{11} & A_{12} & \cdots & A_{1n} \\ A_{21} & A_{22} & \cdots & A_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ A_{n1} & A_{n2} & \cdots & A_{nn} \end{matrix} \right] \left[ \begin{matrix} C_{11} & C_{21} & \cdots & C_{n1} \\ C_{12} & C_{22} & \cdots & C_{n2} \\ \vdots & \vdots & \ddots & \vdots \\ C_{1n} & C_{2n} & \cdots & C_{nn} \end{matrix} \right] \end{equation}\]

(1)对角元素

根据行列式的展开,\(AC^T\)的第一行第一列元素为

\[\begin{equation} \sum_{k=1}^nA_{1k}C_{1k} = det(A) \end{equation}\]

类似等式对\(AC^T\)的对角元素均成立。

(2)非对角元素

\(AC^T\)的第一行最末列元素为

\[\begin{equation} \sum_{k=1}^nA_{1k}C_{nk} \end{equation}\]

相当于第一行与最末行元素完全相同的矩阵按照其最末行展开以计算行列式。
而有两行完全相同的矩阵(非满秩矩阵奇异矩阵),其行列式为0,故

\[\begin{equation} \sum_{k=1}^nA_{1k}C_{nk} = 0 \end{equation}\]

类似地,对\(AC^T\)的非对角元素,均可证明其等于0。

因此,等式 \(\begin{equation} A\ adj(A) = AC^T = det(A)\ I \end{equation}\) 成立。

\[\tag*{Q.E.D.}\]
伴随矩阵法求逆

很容易得到,若A可逆矩阵(又称满秩矩阵非奇异矩阵,即 \(det(A) \neq 0\) 的方阵),则A的逆矩阵为

\[\begin{equation} A^{-1} = \frac{1}{det(A)}\ adj(A) \end{equation} \tag{2}\]

此即为用伴随矩阵法求矩阵逆的公式。

 

克莱姆法则

克莱姆法则的推导

对于线性方程组 \(Ax = b\),若A为可逆矩阵,则 \(x=A^{-1}b\)。

代入等式(2),得到

\[\begin{equation} x = \frac{1}{det(A)}\ C^T b \end{equation} \tag{3}\]

逐一分析 x 的元素:

因为 \(C^T b\) 的第i个元素是 A 的余子式以 b 为系数的线性组合,所以其是某矩阵 \(B_j\) 的行列式,
其中,\(B_j\) 是用向量 b 替换矩阵 A 的第 j 列所得的矩阵。

比如对于 \(\begin{equation} B_1 = \left[ \begin{matrix} b_1 & A_{12} & A_{13} & \cdots & A_{1n} \\ b_2 & A_{22} & A_{23} & \cdots & A_{2n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ b_n & A_{n2} & A_{n3} & \cdots & A_{nn} \end{matrix} \right] \end{equation}\)

恰有

\[{(C^T b)}_1 = \sum_{k=1}^n b_k C_{k1} = det(B_1)\]

因此,对于线性方程组 \(Ax = b\),若A为可逆矩阵,则其解 \(x\) 满足

\[\begin{equation} x_j = \frac{det(B_j)}{det(A)} \end{equation} \tag{4}\]

这就是克莱姆法则。

克莱姆法则的说明

克莱姆法则需要计算大量的行列式值,效率比高斯消元法低。因此,在实际中求解线性方程组时一般不会使用克莱姆法则。

克莱姆法则多用于理论研究和证明中。

克莱姆法则的应用

克莱姆法则可以证明整数规划问题的一个重要理论

约束矩阵 A 为单模矩阵(Unimodular matrix),右侧向量 b 为整数向量的整数规划问题(Integer programming),其基本解是整数解。

References

  1. Cramer’s rule - Wikipedia
  2. Minor (linear algebra) - Wikipedia
  3. Lecture 20: Cramer’s rule, inverse matrix, and volume - MIT