线性代数02-矩阵消元

Linear Algebra-矩阵消元-02

概要

在上一篇文章中，我们提到了需要一种”系统化”的方法来求解线性方程组，这一节我们就来深入聊聊矩阵消元法。通过矩阵的消元运算，我们可以非常有条理地求解复杂的线性方程组。

本文会从基础的消元步骤讲起，然后介绍消元矩阵——也就是把消元运算用矩阵乘法的形式表示出来，最后从消元矩阵引入，简单介绍逆矩阵的基本概念。准备好了吗？让我们开始吧。

消元法求解方程

消元法介绍

对于”好”的系数矩阵（也就是可逆矩阵）$A$，我们可以使用消元法来求解方程 $Ax=b$。我们还是从一个具体的例子开始，一步步理解这个过程。

假设我们需要解这样一个方程组：

$$x+2y+z=2$$ $$3x+8y+z=12$$ $$4y+z=2$$

按照我们上一节讲的，把它写成矩阵形式 $Ax=b$：

$$\begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix}\begin{bmatrix} x \\ y \\ z \end{bmatrix}=\begin{bmatrix} 2 \\ 12 \\ 2 \end{bmatrix}$$

其实矩阵消元法和我们中学学的二元一次方程组消元法本质上是一回事——都是通过把不同行的方程相加消去未知数，逐步化简方程组。只不过现在我们把系数单独抽出来进行运算，寻找一种矩阵层面的通用方法。

我们现在只看系数矩阵 $A$：

$$A = \begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix}$$

消元从左上角的第一个元素开始，这个元素非常关键，我们称之为主元（pivot）。接下来我们要用初等行变换——“把一行乘倍数加到另一行”——将第一列中除主元外的所有元素都变成 $0$。

第一步，我们要把第二行第一列的 $3$ 消成 $0$。具体操作是：第二行减去第一行乘以 $3$。写作：

$$\begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix} \xrightarrow{\text{行2} = \text{行2} - 3 \times \text{行1}} \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix}$$

第一步完成了！第一列现在只有主元位置有值，其他位置都是 $0$。现在我们可以把第一行和第一列看作已经”处理完毕”，接下来处理去掉第一行第一列后右下角的子矩阵 $\begin{bmatrix}2 & -2 \ 4 & 1\end{bmatrix}$。

同样，我们把这个子矩阵左上角的 $2$ 作为新的主元，继续消元，把第二列中主元下方的元素变为 $0$：

$$\begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix} \xrightarrow{\text{行3} = \text{行3} - 2 \times \text{行2}} \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 5 \end{bmatrix}$$

这时候第三行只剩下最后一个元素 $5$，直接把它作为主元就好了。整个消元过程可以串起来写：

$$\begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix} \xrightarrow{\text{行2} = \text{行2} - 3 \times \text{行1}} \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix} \xrightarrow{\text{行3} = \text{行3} - 2 \times \text{行2}} \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 5 \end{bmatrix}$$

因为原矩阵 $A$ 是可逆的，所以经过消元后我们得到一个上三角矩阵，记作 $U$：

$$U = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 5 \end{bmatrix}$$

这个矩阵正好有三个主元（对角线元素都非零），消元过程到此结束。

注意事项：
并不是所有矩阵都能完成完整的消元过程。如果在消元过程中，主元位置正好是 $0$，说明这个位置不能做主元，需要进行行交换——看看下面几行对应位置是不是非零，如果有，就交换两行，把非零元素换到主元位置继续。如果找遍了下面所有行都找不到非零元素，说明这个矩阵不可逆，方程组的解不唯一。

举几个无法完成完整消元的例子：

$$\begin{bmatrix} 0 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 5 \end{bmatrix}, \quad \begin{bmatrix} 1 & 2 & 1 \\ 0 & 0 & -2 \\ 0 & 0 & 5 \end{bmatrix}, \quad \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 0 \end{bmatrix}$$

回带求解

讲完了消元，接下来就是回带求解。虽然在实际算法中，消元和回带经常是一起进行的，但为了便于理解，我们这里分开讨论。

首先介绍一个重要概念：增广矩阵。还是用刚才的例子，我们把系数矩阵 $A$ 和右侧的常数向量 $b$ 拼在一起，就得到了增广矩阵：

$$\left[\begin{array}{ccc|c} 1 & 2 & 1 & 2\\ 3 & 8 & 1 & 12\\ 0 & 4 & 1 & 2 \end{array}\right]$$

消元的过程和之前完全一样，只不过这次要带着最右边的 $b$ 列一起变换：

$$\left[\begin{array}{ccc|c} 1 & 2 & 1 & 2\\ 3 & 8 & 1 & 12\\ 0 & 4 & 1 & 2 \end{array}\right] \xrightarrow{\text{行2} = \text{行2} - 3 \times \text{行1}} \left[\begin{array}{ccc|c} 1 & 2 & 1 & 2\\ 0 & 2 & -2 & 6\\ 0 & 4 & 1 & 2 \end{array}\right] \xrightarrow{\text{行3} = \text{行3} - 2 \times \text{行2}} \left[\begin{array}{ccc|c} 1 & 2 & 1 & 2 \\ 0 & 2 & -2 & 6\\ 0 & 0 & 5 & -10 \end{array}\right]$$

现在我们再把这个增广矩阵变回方程组形式，就得到了：

$$x+2y+z=2 \\ 2y-2z=6 \\ 5z=-10$$

接下来从下往上依次求解，非常简单：

• 由最后一个方程得 $z=-2$
• 代入第二个方程得 $2y-2(-2)=6 \Rightarrow y=1$
• 代入第一个方程得 $x+2(1)+(-2)=2 \Rightarrow x=2$

这样就得到了原方程组的解：$x=2, y=1, z=-2$。这个从下往上求解的过程就叫”回带”。

整个消元法的过程可以用一张图总结一下：

消元矩阵

刚才我们是从直观变换的角度介绍了消元操作，现在我们要更进一步——用矩阵乘法来表示每一步消元过程。这非常重要，因为它让我们从”操作”层面上升到”代数”层面，真正理解消元的数学本质。

行向量与矩阵的乘法

上一节我们讲过，矩阵乘以列向量，结果是矩阵列向量的线性组合：

$$\begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3}\\ a_{2,1} & a_{2,2} & a_{2,3}\\ a_{3,1} & a_{3,2} & a_{3,3} \end{bmatrix}\begin{bmatrix} m\\ n\\ k \end{bmatrix}=m\begin{bmatrix} a_{1,1}\\ a_{2,1}\\ a_{3,1} \end{bmatrix}+n\begin{bmatrix} a_{1,2}\\ a_{2,2}\\ a_{3,2} \end{bmatrix}+k\begin{bmatrix} a_{1,3}\\ a_{2,3}\\ a_{3,3} \end{bmatrix}$$

但消元法中我们做的是行变换，所以我们需要反过来思考：行向量乘以矩阵又是什么呢？

$$\begin{bmatrix} m & n & k \end{bmatrix}\begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3}\\ a_{2,1} & a_{2,2} & a_{2,3}\\ a_{3,1} & a_{3,2} & a_{3,3} \end{bmatrix}=m\begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} \end{bmatrix}+n\begin{bmatrix} a_{2,1} & a_{2,2} & a_{2,3} \end{bmatrix}+k\begin{bmatrix} a_{3,1} & a_{3,2} & a_{3,3} \end{bmatrix}$$

结论很清晰：行向量乘以矩阵，结果是矩阵行向量的线性组合。

至于行向量为什么要放在矩阵左边，这完全是由矩阵乘法的维数匹配规则决定的——上面的例子中，行向量是 $1 \times 3$，矩阵是 $3 \times 3$，相乘得到 $1 \times 3$ 的结果，维数是匹配的。如果反过来放，就没法相乘了。

行向量左乘 → 行的线性组合，列向量右乘 → 列的线性组合，这个结论非常重要，请务必记住，后面会反复用到。

消元矩阵介绍

这部分是本节的重点。理解了行向量和矩阵的乘法，我们就可以把每一步行操作表示成矩阵乘法了。所谓消元矩阵，其实就是把消元过程转化为矩阵相乘的形式。

我们先看一个简单的规律，对于单位矩阵来说：

$$\begin{bmatrix} 1 & 0 & 0 \end{bmatrix}\begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3}\\ a_{2,1} & a_{2,2} & a_{2,3}\\ a_{3,1} & a_{3,2} & a_{3,3} \end{bmatrix} = \begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} \end{bmatrix}$$ $$\begin{bmatrix} 0 & 1 & 0 \end{bmatrix}\begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3}\\ a_{2,1} & a_{2,2} & a_{2,3}\\ a_{3,1} & a_{3,2} & a_{3,3} \end{bmatrix} = \begin{bmatrix} a_{2,1} & a_{2,2} & a_{2,3} \end{bmatrix}$$ $$\begin{bmatrix} 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3}\\ a_{2,1} & a_{2,2} & a_{2,3}\\ a_{3,1} & a_{3,2} & a_{3,3} \end{bmatrix} = \begin{bmatrix} a_{3,1} & a_{3,2} & a_{3,3} \end{bmatrix}$$

把这三个行向量叠起来，就得到了我们熟悉的单位矩阵：

$$I = \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}$$

单位矩阵和任何矩阵相乘都不改变原矩阵，这是显然的。而消元矩阵其实就是单位矩阵经过一次行变换得到的。我们还是用刚才的例子来说明：

我们想要找到一个矩阵，满足：

$$\begin{bmatrix} ? & ? & ?\\ ? & ? & ?\\ ? & ? & ? \end{bmatrix}\begin{bmatrix} 1 & 2 & 1\\ 3 & 8 & 1\\ 0 & 4 & 1 \end{bmatrix}=\begin{bmatrix} 1 & 2 & 1\\ 0 & 2 & -2\\ 0 & 4 & 1 \end{bmatrix}$$

我们知道单位矩阵乘上去结果不变：

$$\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} 1 & 2 & 1\\ 3 & 8 & 1\\ 0 & 4 & 1 \end{bmatrix}=\begin{bmatrix} 1 & 2 & 1\\ 3 & 8 & 1\\ 0 & 4 & 1 \end{bmatrix}$$

我们的第一步操作是：第二行 = 第二行 + (-3) × 第一行。既然这是对第二行的修改，那我们就直接修改单位矩阵的第二行：

$$\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} \xrightarrow{\text{行2} = \text{行2} - 3 \times \text{行1}} \begin{bmatrix} 1 & 0 & 0\\ -3 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}$$

我们来验证一下对不对。根据之前的结论，结果矩阵的第二行就是消元矩阵第二行乘原矩阵：

$$\begin{bmatrix} -3 & 1 & 0 \end{bmatrix}\begin{bmatrix} 1 & 2 & 1\\ 3 & 8 & 1\\ 0 & 4 & 1 \end{bmatrix}=-3\begin{bmatrix} 1 & 2 & 1 \end{bmatrix}+1\begin{bmatrix} 3 & 8 & 1 \end{bmatrix}=\begin{bmatrix} 0 & 2 & -2 \end{bmatrix}$$

完美！正好得到我们想要的结果。所以这一步的消元矩阵就是：

$$E_{21} = \begin{bmatrix} 1 & 0 & 0\\ -3 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}$$

下标 $E_{21}$ 表示它的作用是把矩阵中 $(2,1)$ 位置消成 $0$。

同理，我们来找第二步消元的消元矩阵——这一步我们是把第三行第二列的 $4$ 消成 $0$，操作是：第三行 = 第三行 - $2 \times$ 第二行。同样，从单位矩阵出发，修改第三行：

$$\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} \xrightarrow{\text{行3} = \text{行3} - 2 \times \text{行2}} \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & -2 & 1 \end{bmatrix}$$

记这个消元矩阵为 $E_{32}$，那么整个消元过程就可以写成非常简洁的矩阵形式：

$$E_{32}E_{21}A = U$$

其中 $U$ 就是我们最后得到的上三角矩阵。根据矩阵乘法的结合律，我们可以先算 $E = E{32}E{21}$，那么 $E$ 就是整个消元过程对应的总消元矩阵。

这里总结一下求消元矩阵的核心方法：从单位矩阵 $I$ 出发，每一步消元操作对 $I$ 做同样的行变换，得到的就是这一步的初等消元矩阵，最后把所有初等消元矩阵乘起来就是总的消元矩阵。这个方法简单好用，记下来！

行交换矩阵与逆矩阵

行变换与列变换

有了上面消元矩阵的概念，我们很容易推广得到行交换矩阵。比如，交换一个 $2 \times 2$ 矩阵的两行，交换矩阵就是：

$$\begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} a & b\\ c & d \end{bmatrix}=\begin{bmatrix} c & d\\ a & b \end{bmatrix}$$

而如果我们把这个交换矩阵放在右边，就是交换两列：

$$\begin{bmatrix} a & b\\ c & d \end{bmatrix}\begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix}=\begin{bmatrix} b & a\\ d & c \end{bmatrix}$$

所以我们得到一个非常重要的结论：左乘矩阵对应行变换，右乘矩阵对应列变换。这个结论在矩阵运算中经常用到，一定要牢记。

逆矩阵初探

现在我们会用消元矩阵把 $A$ 变成 $U$ 了，那反过来，如果我们想把 $U$ 变回 $A$，应该怎么做呢？答案就是乘上逆矩阵。

还是用刚才的 $E_{21}$ 举例：

$$E_{21}=\begin{bmatrix} 1 & 0 & 0\\ -3 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}$$

它的作用是”第二行减去 $3$ 倍第一行”。那反过来，如果我们想要撤销这个操作，只需要”第二行加上 $3$ 倍第一行”就可以复原了。所以对应的逆操作矩阵是：

$$\begin{bmatrix} 1 & 0 & 0\\ 3 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}$$

我们来乘一下验证：

$$\begin{bmatrix} 1 & 0 & 0\\ 3 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} 1 & 0 & 0\\ -3 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}=\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}=I$$

结果正好是单位矩阵。我们把这个矩阵称为 $E{21}$ 的逆矩阵，记作 $E{21}^{-1}$，满足：

$$E_{21}^{-1}E_{21} = I$$

逆矩阵的概念我们后面会深入讲解，这里先建立一个直观认识就好。

笔者感悟

这一节从解线性方程组的实际问题出发，一步步引出矩阵消元，再把消元过程抽象为矩阵乘法，最后得到消元矩阵和逆矩阵的概念，这个递进过程其实非常巧妙。

笔者作为一名IC设计者，在日常工作中也经常感受到，消元法不仅仅是书本上的数学工具——在EDA工具中，大规模线性方程组的求解就是靠消元法及其变种实现的。理解了消元的矩阵本质，才能真正看懂稀疏矩阵求解算法的优化思路。

最重要的收获其实是思维方式的转变：从”对矩阵做行操作”，到”行操作等于左乘一个消元矩阵”，这其实是从”操作”到”代数”的升华。当你把一切都用矩阵乘法表示出来后，很多复杂的变换就变得可以计算、可以推导了。

总而言之，矩阵消元是线性代数入门的第一道门槛，跨过这道坎，你才能真正开始用矩阵的思维思考问题。