解线性方程组
消元的几何意义，以及它为什么会通向 LU 分解
本文译自英文原文 Solving Linear Equations，如有出入，以英文版为准。
在上一篇里，我从向量和线性变换的角度看矩阵。这一次换一个角度：线性方程组。我最感兴趣的，是解方程组背后的几何意义，以及高斯消元如何自然地引出 LU 分解。
1 直线、平面和它们的法向量
考虑两个未知数的两个方程：
\[ \begin{cases} x-2y=1,\\ 3x+2y=11. \end{cases} \]
每个方程描述平面上的一条直线，方程组的解就是两条直线的交点 \((x,y)=(3,1)\)（图 1）。写成矩阵形式，就是
\[ \underbrace{\begin{bmatrix}1&-2\\3&2\end{bmatrix}}_{A} \underbrace{\begin{bmatrix}x\\y\end{bmatrix}}_{\vec{x}} = \underbrace{\begin{bmatrix}1\\11\end{bmatrix}}_{\vec{b}} \]
三个未知数的三个方程，每个方程描述空间中的一个平面，解就是三个平面的公共点。例如
\[ \begin{cases} x+y+z=4,\\ x-y+z=2,\\ 2x-z=0 \end{cases} \]
的解是 \((x,y,z)=(1,1,2)\)（图 2）。几何对象从直线变成了平面，代数形式仍然是 \(A\vec{x}=\vec{b}\)。
直线或平面是否交于一点，取决于它们的倾斜方向，而平面的倾斜方向由它的法向量描述，这是我在高中几何里学过的。平面 \(ax+by+cz=d\) 的法向量是 \(\vec{n}=(a,b,c)\)，前提是 \((a,b,c)\ne(0,0,0)\)。为什么？在平面上任取两点 \(P_1=(x_1,y_1,z_1)\) 和 \(P_2=(x_2,y_2,z_2)\)。它们都满足平面方程，两式相减，用点积的语言写出来就是
\[ (a,b,c)\cdot(x_1-x_2,\ y_1-y_2,\ z_1-z_2)=0 \]
第二个向量沿着平面的方向。既然对平面上任意两点都成立，\((a,b,c)\) 就垂直于平面内的每一个方向，这正是法向量的含义。同样，直线 \(ax+by=c\) 的法向量是 \((a,b)\)。
法向量告诉我们什么时候有唯一解。在二维中，法向量线性无关，两条直线就不平行，交于一点；法向量线性相关，两条直线就平行或重合，要么无解，要么有无穷多解。在三维中，三个法向量线性无关，三个平面就恰好交于一点。如果法向量张成的方向少于三个，就不可能有唯一解，方程组要么无解，要么有无穷多解，取决于这些方程是否相容。用矩阵的语言说，独立法向量的个数就是 \(A\) 的秩。
2 消元在几何上做了什么
解方程组时，我们通常不断消去变量，直到方程组变成上三角形式。我觉得更有意思的是去问：每一步在几何上意味着什么？
回到那两条直线，把第二个方程替换为第二个方程减去第一个方程的三倍：
\[ (3x+2y)-3(x-2y)=11-3 \quad\Longrightarrow\quad 8y=8 \]
新的直线 \(y=1\) 和原来的第二条直线不同，但它仍然经过 \((3,1)\)。解没有变，是因为这一步可以撤销：把第一个方程的三倍加回去，就得到原来的第二个方程。
法向量也按同样的方式变化：
\[ \vec{n}_2'=\vec{n}_2-3\vec{n}_1=(3,2)-3(1,-2)=(0,8) \]
所以，从一个方程中减去另一个方程的倍数，就是让第二条直线绕着固定的交点旋转（图 3）。消元选的倍数，恰好让 \(\vec{n}_2'\) 竖直向上：直线变成水平的，\(x\) 从方程里消失，可以直接读出 \(y=1\)。
在三维中也是一样。把一个平面的方程换成两个方程的组合，这个平面变了，但两个平面的交线保持不变。消元不断这样转动平面（图 4），直到方程组变成上三角形式：最后一个平面是水平的，它上面那个平面的方程里没有 \(x\)，于是可以依次读出 \(z\)、\(y\)、\(x\)。
3 把消元记录下来：\(PA=LU\)
高斯消元把 \(A\) 变成上三角矩阵 \(U\)。与其把它当作一次性的计算，我们可以把得到 \(U\) 的那些操作记录下来。在两条直线的例子里，从第二行减去第一行的三倍，这个操作本身就是一个矩阵：
\[ E=\begin{bmatrix}1&0\\-3&1\end{bmatrix}, \qquad EA=\begin{bmatrix}1&-2\\0&8\end{bmatrix}=U \]
撤销这一步，得到 \(A=E^{-1}U\)：
\[ A= \underbrace{\begin{bmatrix}1&0\\3&1\end{bmatrix}}_{L} \underbrace{\begin{bmatrix}1&-2\\0&8\end{bmatrix}}_{U} \]
这就是 LU 分解。\(U\) 是消元的结果，下三角矩阵 \(L\) 以能还原出 \(A\) 的形式保存了乘数 \(3\)。
步骤不止一步时，需要知道逆矩阵的一个性质。对于方阵 \(A\)，如果它的逆 \(A^{-1}\) 存在，就满足 \(A^{-1}A=AA^{-1}=I\)，而乘积的逆要把顺序反过来：
\[ (AB)^{-1}=B^{-1}A^{-1} \]
如果把矩阵看作依次进行的变换，这就说得通了：\(AB\) 先做 \(B\) 再做 \(A\)，所以要撤销它，就要先撤销 \(A\)，再撤销 \(B\)。
上面三个平面的例子需要三步：从第 2 行减去第 1 行的 \(1\) 倍（\(E_{21}\)），从第 3 行减去第 1 行的 \(2\) 倍（\(E_{31}\)），再从第 3 行减去新的第 2 行的 \(1\) 倍（\(E_{32}\)）：
\[ E_{32}E_{31}E_{21}A=U=\begin{bmatrix}1&1&1\\0&-2&0\\0&0&-3\end{bmatrix} \]
按相反的顺序撤销这三步，
\[ A=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U= \underbrace{\begin{bmatrix}1&0&0\\1&1&0\\2&1&1\end{bmatrix}}_{L}U \]
\(L\) 存着三个乘数 \(1\)、\(2\) 和 \(1\)，每一个都在它所消去的那个元素的位置上。正是相反的顺序让它们保持干净。正向的乘积 \(E_{32}E_{31}E_{21}\) 左下角是 \(-1\)，而不是 \(-2\)：它用第 2 行去改第 3 行时，第 2 行已经被改过了，所以乘数混在了一起。而按相反顺序相乘，这些逆矩阵只是把每个乘数放到各自的位置上。
为什么要保留 \(L\)？假设 \(A\) 不变，而我们要对很多个右端 \(\vec{b}\) 求解 \(A\vec{x}=\vec{b}\)。有了 \(A=LU\)，每个新的 \(\vec{b}\) 只需要解两个三角方程组，
\[ L\vec{y}=\vec{b},\qquad U\vec{x}=\vec{y} \]
用前代和回代即可。我们也可以保存行变换本身，再对每个新的 \(\vec{b}\) 重放一遍。LU 正是做这件事的一种有结构的方式。 节省是很可观的：对 \(n\times n\) 矩阵消元大约需要 \(n^3/3\) 次乘法，而两个三角方程组只需要大约 \(n^2\) 次。
还剩一个麻烦：并不是每个可逆矩阵都能在不交换行的情况下这样分解。例如，
\[ A=\begin{bmatrix}0&1\\1&0\end{bmatrix} \]
是可逆的，但它的第一个主元是零，必须先交换两行。置换矩阵 \(P\) 记录这些行交换，于是得到一般的形式
\[ PA=LU \]
用它求解 \(A\vec{x}=\vec{b}\) 时，右端也要做同样的置换：\(LU\vec{x}=P\vec{b}\)。
对我来说，最主要的想法是：LU 并不是独立于高斯消元的另一个技巧。它就是消元已经做过的工作，被记录下来，以便重复使用。
4 转置，暂且如此
转置 \(A^T\) 交换 \(A\) 的行和列；我把它想象成矩阵的元素沿主对角线翻折过去。满足 \(A=A^T\) 的矩阵叫对称矩阵。和逆矩阵一样，乘积的转置也要把顺序反过来，\((AB)^T=B^TA^T\)。我可以从定义验证这一点，但转置、点积和正交之间的联系，等以后再看会更有意思，所以这里先不展开。
现在，我想从这一篇里留下的两个想法是：消元的几何意义，以及 LU 如何把它记录下来。