矩阵消元

一、消元法求解方程

1.1 消元法介绍

消元法是计算机软件求解线形方程组所用的最常见的方法。任何情况下，只要是矩阵 $\boldsymbol{A}$ 可逆，均可以通过消元法求得 $\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}$ 的解。

此处给出的线性方程组为

$\boldsymbol{A}=\left[{\begin{array}{cc}1&2&1\\3&8&1\\0&4&1\end{array}}\right],\boldsymbol{b}=\left[{\begin{array}{cc}2\\{12}\\2\end{array}}\right]$

高斯消元法（Gauss elimination）就是通过对方程组中的某两个方程进行适当的数乘和加 / 减法，以达到将某一未知数系数变为零，从而削减未知数个数的目的。

我们将矩阵左上角的 $1$ 称之为 “主元 1”（the first pivot），第一步要通过消元将第一列中除了主元之外的数字均变为 $0$。操作方法就是用之后的每一行减去第一行的适当倍数，此例中 第二行应减去第一行的 $3$ 倍。之后应对第三行做类似操作，本例中三行第一列数字已经为 $0$，故不用进行操作。此时处在第二行第二列的 “主元 2” 为 $2$，因此用 第三行减去第二行的两倍 进行消元，得到第三个主元为 $5$。

矩阵 $\boldsymbol{A}$ 为可逆矩阵，消元结束后得到上三角阵 $\boldsymbol{U}$（Uppertriangular matrix），其左侧下半部分的元素均为 $0$，而主元 $1,2,5$ 分列在 $\boldsymbol{U}$ 的对角线上。主元之积即行列式的值。

需要说明的是，主元不能为 $0$，如果恰好消元至某行，$0$ 出现在了主元的位置上，应当通过与下方一行进行 “行交换” 使得非零数字出现在主元位置上。如果 $0$ 出现在了主元位置上，并且下方没有对等位置为非 $0$ 数字的行，则消元终止，并证明矩阵 $\boldsymbol{A}$ 为不可逆矩阵，且线性方程组没有唯一解。

1.2 回代求解

做方程的高斯消元时，需要对等式右侧的 $\boldsymbol{b}$ 做同样的乘法和加 / 减法。手工计算时比较有效率的方法是应用 “增广矩阵”，将 $\boldsymbol{b}$ 插入矩阵 $A$ 之后形成最后一列，在消元过程中带着 $\boldsymbol{b}$ 一起操作（Matlab 是算完系数矩阵再处理 $\boldsymbol{b}$ 的）。

$\left[{\begin{array}{cc}1&2&1&2\\3&8&1&{12}\\0&4&1&2\end{array}}\right]\to\left[{\begin{array}{cc}1&2&1&2\\0&2&{-2}&6\\0&4&1&2\end{array}}\right]\to\left[{\begin{array}{cc}1&2&1&2\\0&2&{-2}&6\\0&0&5&{-10}\end{array}}\right]$

此时我们将原方程 $\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}$ 转化为了新的方程 $\boldsymbol{U}\boldsymbol{x}=\boldsymbol{c}$，其中 $\boldsymbol{c}=\left[{\begin{array}{cc}2\\6\\{-10}\end{array}}\right]$ 。

从最后一行得到 $z=-2$，依次向上回代可以得到 $y=1,x=2$。

二、消元矩阵

上面的消元法是从简单的变换角度介绍了消元的具体操作，接下来我们需要 用矩阵来表示变换 的方法，这也十分有必要，因为这是一种 “系统的” 变换矩阵的方法。

矩阵运算的核心内容就是 对 “行” 或者 “列” 进行独立操作。

1. 矩阵右乘列向量，相当于对矩阵的列向量进行线性组合。
2. 矩阵左乘行向量，相当于对矩阵的行向量进行线性组合。

说明

通俗理解，“列操作” 就像是把向量开进矩阵，而 “行操作” 就像把向量倒车进入矩阵。

矩阵消元的第一步是通过左乘矩阵 $\boldsymbol{E}_{21}$ 来实现原矩阵 $\boldsymbol{A}$ 的第二行减去第一行的 $3$ 倍这一过程。$\boldsymbol{E}_{21}$ 的第二行使矩阵 $\boldsymbol{A}$ 的行向量进行前述的线性组合，而其它两行为了保持与原矩阵相同，采用同阶单位阵 $\boldsymbol{I}$ 的行向量。

第一行：$\left[{\begin{array}{cc}1&0&0\end{array}}\right]\left[{\begin{array}{cc}1&2&1\\3&8&1\\0&4&1\end{array}}\right]=\left[{\begin{array}{cc}1&2&1\end{array}}\right]$

第三行：$\left[{\begin{array}{cc}0&0&1\end{array}}\right]\left[{\begin{array}{cc}1&2&1\\3&8&1\\0&4&1\end{array}}\right]=\left[{\begin{array}{cc}0&4&1\end{array}}\right]$

第二行（关键）：$\left[{\begin{array}{cc}{-3}&1&0\end{array}}\right]\left[{\begin{array}{cc}1&2&1\\3&8&1\\0&4&1\end{array}}\right]=\begin{array}{cc}{-3}&{[1}&2&{1]}\\{\begin{array}{cc}{+1}\end{array}}&{[3}&8&{1]}\\{\begin{array}{cc}{+0}\end{array}}&{[0}&4&{1]}\end{array}=\left[{\begin{array}{cc}0&2&{-2}\end{array}}\right]$

左乘的这个矩阵为 “初等矩阵”（Elementary Matrix），因此记做 $\boldsymbol{E}$。因为要消掉的元素在矩阵的第二行第一列，因此将之标注为 $21$。完成操作后矩阵变为 $\boldsymbol{E}_{21}\boldsymbol{A}$。

$\begin{array}{l}\left[{\begin{array}{cc}1&0&0\\{-3}&1&0\\0&0&1\end{array}}\right]\left[{\begin{array}{cc}1&2&1\\3&8&1\\0&4&1\end{array}}\right]=\left[{\begin{array}{cc}1&2&1\\0&2&{-2}\\0&4&1\end{array}}\right]\\\begin{array}{cc}&{}&{}{\boldsymbol{E}_{21}}&{}&{}&{}&{}&\boldsymbol{A}&{}&{}&{}&{}&{}&{\boldsymbol{E}_{21}\boldsymbol{A}}&{}&{}\end{array}\end{array}$

矩阵消元的第二步是完成矩阵 $\boldsymbol{E}_{21}\boldsymbol{A}$ 的第三行减去第二行的 $2$ 倍，通过左乘矩阵 $\boldsymbol{E}_{32}$ 来实现这一过程。

$\begin{array}{l}\left[{\begin{array}{cc}1&0&0\\0&1&0\\0&{-2}&1\end{array}}\right]\left[{\begin{array}{cc}1&2&1\\0&2&{-2}\\0&4&1\end{array}}\right]=\left[{\begin{array}{cc}1&2&1\\0&2&{-2}\\0&0&5\end{array}}\right]\\\begin{array}{cc}{}&{}&{\boldsymbol{E}_{32}}&{}&{}&{}&&{}{\boldsymbol{E}_{21}\boldsymbol{A}}&{}&{}&{}&{\boldsymbol{E}_{32}({\boldsymbol{E}_{21}}\boldsymbol{A})}&{}\end{array}\end{array}$

$3\times{3}$ 矩阵的消元本来应该分三步完成，最终得到 $\boldsymbol{E}_{32}(\boldsymbol{E}_{31}(\boldsymbol{E}_{21}\boldsymbol{A}))$。在本例中 $\boldsymbol{E}_{31}=\boldsymbol{I}$，所以结果变为 $\boldsymbol{E}_{32}(\boldsymbol{E}_{21}\boldsymbol{A})=\boldsymbol{U}$，因为矩阵运算符合结合律，也可写作 $(\boldsymbol{E}_{32}\boldsymbol{E}_{21})\boldsymbol{A}=\boldsymbol{U}$，可以记作 $\boldsymbol{E}\boldsymbol{A}=\boldsymbol{U}$。

方程 $\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}$ 的解也满足方程 $\boldsymbol{U}\boldsymbol{x}=\boldsymbol{E}\boldsymbol{A}\boldsymbol{x}=\boldsymbol{E}\boldsymbol{b}=\boldsymbol{c}$，因此我们将问题转化为 $\boldsymbol{U}\boldsymbol{x}=\boldsymbol{c}$。

三、置换矩阵

左乘置换矩阵可以完成原矩阵的行变换，右乘置换矩阵则为列变换。例如

$\left[{\begin{array}{cc}0&1\\1&0\end{array}}\right]\left[{\begin{array}{cc}a&b\\c&d\end{array}}\right]=\left[{\begin{array}{cc}c&d\\a&b\end{array}}\right]$

$\left[{\begin{array}{cc}a&b\\c&d\end{array}}\right]\left[{\begin{array}{cc}0&1\\1&0\end{array}}\right]=\left[{\begin{array}{cc}b&a\\d&c\end{array}}\right]$

对于三阶矩阵

$\left[{\begin{array}{cc}0&0&1\\0&1&0\\1&0&0\end{array}}\right]\left[{\begin{array}{cc}a&b&c\\d&e&f\\g&h&i\end{array}}\right]=\left[{\begin{array}{cc}g&h&i\\d&e&f\\a&b&c\end{array}}\right]$

置换矩阵是通过 对 $\boldsymbol{I}$ 矩阵进行 “行交换” 来实现的。

四、逆矩阵

这里主要讨论消元矩阵的逆矩阵。消元矩阵之逆矩阵的效果就是抵消原矩阵的消元操作。

消元矩阵实现了对原矩阵 $A$ 的操作，使第二行行向量 $[3,8,1]$ 减掉了第一行 $[1,2,1]$ 的 $3$ 倍变为 $[0,2,-2]$，则逆向操作就应该是把现在的第二行行向量 $[0,2,-2]$ 加上第一行 $[1,2,1]$ 的3倍，从而变回原来的第二行 $[3,8,1]$。

所以对于 ${\boldsymbol{E}_{21}}=\left[{\begin{array}{cc}1&0&0\\{-3}&1&0\\0&0&1\end{array}}\right]$，有 $\boldsymbol{E}_{21}^{-1}=\left[{\begin{array}{cc}1&0&0\\3&1&0\\0&0&1\end{array}}\right]$。

满足 $\boldsymbol{E}_{21}^{-1}{\boldsymbol{E}_{21}}=\boldsymbol{I}$，即

$\left[{\begin{array}{cc}1&0&0\\3&1&0\\0&0&1\end{array}}\right]\left[{\begin{array}{cc}1&0&0\\{-3}&1&0\\0&0&1\end{array}}\right]=\left[{\begin{array}{cc}1&0&0\\0&1&0\\0&0&1\end{array}}\right]$

五、参考资料

• MIT—线性代数笔记 02 矩阵消元 (opens new window)