第二讲：矩阵消元

这个方法最早由高斯提出，我们以前解方程组的时候都会使用，现在来看如何使用矩阵实现消元法。

消元法

有三元方程组$\{\begin{array}{llll}x& +2y& +z& =2\\ 3x& +8y& +z& =12\\ & 4y& +z& =2\end{array}$，对应的矩阵形式$Ax=b$为$\left[\begin{array}{ccc}1& 2& 1\\ 3& 8& 1\\ 0& 4& 1\end{array}\right]\left[\begin{array}{c}x\\ y\\ z\end{array}\right]=\left[\begin{array}{c}2\\ 12\\ 2\end{array}\right]$。

按照我们以前做消元法的思路：

• 第一步，我们希望在第二个方程中消去$x$项，来操作系数矩阵$A=\left[\begin{array}{ccc}\underset{―}{1}& 2& 1\\ 3& 8& 1\\ 0& 4& 1\end{array}\right]$，下划线的元素为第一步的主元（pivot）：$\left[\begin{array}{ccc}\underset{―}{1}& 2& 1\\ 3& 8& 1\\ 0& 4& 1\end{array}\right]\stackrel{ro{w}_2-3ro{w}_1}{\to }\left[\begin{array}{ccc}\underset{―}{1}& 2& 1\\ 0& 2& -2\\ 0& 4& 1\end{array}\right]$

  这里我们先不管$b$向量，等做完$A$的消元可以再做$b$的消元。（这是MATLAB等工具经常使用的算法。）

• 第二步，我们希望在第三个方程中消去$y$项，现在第二行第一个非零元素成为了第二个主元：$\left[\begin{array}{ccc}\underset{―}{1}& 2& 1\\ 0& \underset{―}{2}& -2\\ 0& 4& 1\end{array}\right]\stackrel{ro{w}_3-2ro{w}_2}{\to }\left[\begin{array}{ccc}\underset{―}{1}& 2& 1\\ 0& \underset{―}{2}& -2\\ 0& 0& \underset{―}{5}\end{array}\right]$

  注意到第三行消元过后仅剩一个非零元素，所以它就成为第三个主元。做到这里就算消元完成了。

再来讨论一下消元失效的情形：首先，主元不能为零；其次，如果在消元时遇到主元位置为零，则需要交换行，使主元不为零；最后提一下，如果我们把第三个方程$z$前的系数改成$-4$，会导致第二步消元时最后一行全部为零，则第三个主元就不存在了，至此消元不能继续进行了，这就是下一讲中涉及的不可逆情况。

• 接下来就该回代（back substitution）了，这时我们在$A$矩阵后面加上$b$向量写成增广矩阵（augmented matrix）的形式：$\left[\begin{array}{cc}A& b\end{array}\right]=\left[\begin{array}{cccc}1& 2& 1& 2\\ 3& 8& 1& 12\\ 0& 4& 1& 2\end{array}\right]\to \left[\begin{array}{cccc}1& 2& 1& 2\\ 0& 2& -2& 6\\ 0& 4& 1& 2\end{array}\right]\to \left[\begin{array}{cccc}1& 2& 1& 2\\ 0& 2& -2& 6\\ 0& 0& 5& -10\end{array}\right]$

  不难看出，$z$的解已经出现了，此时方程组变为$\{\begin{array}{llll}x& +2y& +z& =2\\ & 2y& -2z& =6\\ & & 5z& =-10\end{array}$，从第三个方程求出$z=-2$，代入第二个方程求出$y=1$，再代入第一个方程求出$x=2$。

消元矩阵

上一讲我们学习了矩阵乘以向量的方法，有三个列向量的矩阵乘以另一个向量，按列的线性组合可以写作$[v_1{v}_2{v}_3]\left[\begin{array}{c}3\\ 4\\ 5\end{array}\right]=3v_1+4v_2+5v_3$。

但现在我们希望用矩阵乘法表示行操作，则有$\left[\begin{array}{ccc}1& 2& 7\end{array}\right]\left[\begin{array}{ccc}& ro{w}_1& \\ & ro{w}_2& \\ & ro{w}_3& \end{array}\right]=1ro{w}_1+2ro{w}_2+7ro{w}_3$。易看出这里是一个行向量从左边乘以矩阵，这个行向量按行操作矩阵的行向量，并将其合成为一个矩阵行向量的线性组合。

介绍到这里，我们就可以将消元法所做的行操作写成向量乘以矩阵的形式了。

• 消元法第一步操作为将第二行改成$ro{w}_2-3ro{w}_1$，其余两行不变，则有$\left[\begin{array}{ccc}1& 0& 0\\ -3& 1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}1& 2& 1\\ 3& 8& 1\\ 0& 4& 1\end{array}\right]=\left[\begin{array}{ccc}1& 2& 1\\ 0& 2& -2\\ 0& 4& 1\end{array}\right]$（另外，如果三行都不变，消元矩阵就是单位矩阵$I=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$，$I$之于矩阵运算相当于$1$之于四则运算。）这个消元矩阵我们记作$E_{21}$，即将第二行第一个元素变为零。

• 接下来就是求$E_{32}$消元矩阵了，即将第三行第二个元素变为零，则$\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& -2& 1\end{array}\right]\left[\begin{array}{ccc}1& 2& 1\\ 0& 2& -2\\ 0& 4& 1\end{array}\right]=\left[\begin{array}{ccc}1& 2& 1\\ 0& 2& -2\\ 0& 0& 5\end{array}\right]$。这就是消元所用的两个初等矩阵（elementary matrix）。

• 最后，我们将这两步综合起来，即$E_{32}(E_{21}A)=U$，也就是说如果我们想从$A$矩阵直接得到$U$矩阵的话，只需要$(E_{32}{E}_{21})A$即可。注意，矩阵乘法虽然不能随意变动相乘次序，但是可以变动括号位置，也就是满足结合律（associative law），而结合律在矩阵运算中非常重要，很多定理的证明都需要巧妙的使用结合律。

既然提到了消元用的初等矩阵，那我们再介绍一种用于置换两行的矩阵：置换矩阵（permutation matrix）：例如$\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]$。

我们现在能够将$A$通过行变换写成$U$，那么如何从$U$再变回$A$，也就是求消元的逆运算。对某些“坏”矩阵，并没有逆，而本讲的例子都是“好”矩阵。

逆

现在，我们以$E_{21}$为例，$[?]\left[\begin{array}{ccc}1& 0& 0\\ -3& 1& 0\\ 0& 0& 1\end{array}\right]=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$，什么矩阵可以取消这次行变换？这次变换是从第二行中减去三倍的第一行，那么其逆变换就是给第二行加上三倍的第一行，所以逆矩阵就是$\left[\begin{array}{ccc}1& 0& 0\\ 3& 1& 0\\ 0& 0& 1\end{array}\right]$。

我们把矩阵$E$的逆记作$E^{-1}$，所以有$E^{-1}E=I$。