Lecture 2: Elimination with Matrices

目录 · ← l1 · l3 →

Lecture 2: Elimination with Matrices

概述

上一讲我们把 $A\mathbf{x}=\mathbf{b}$ 看成”求 $A$ 的各列的线性组合，使其等于 $\mathbf{b}$”。本讲要把它变成一个可靠、可机械执行、永不失败的算法——高斯消元（Gaussian elimination）。核心问题只有一个：既然消元只是对增广矩阵 $[A\mid\mathbf{b}]$ 反复做”某行减去另一行的倍数”，凭什么说解集没变？答案是把每一步都写成一个矩阵 $E$，而 $E$ 恒可逆，于是 $\mathbf{x}$ 被保住。这一讲还会顺手讲清矩阵乘法为什么可以从四个角度看（Strang 称之为”矩阵乘法是课程中最重要的运算”），并第一次显露 $A=LU$ 的影子。

核心概念的几何直觉

消元（Elimination）：为什么它不改变解集

• 定义与目的：消元是把方程组一步步化成上三角（upper triangular）形状的过程。化到上三角后，最后一个方程只含一个未知数，可以直接解出；再往回一代（back substitution），全部未知数依次得到。它的目的是：把”解一个耦合在一起的方程组”换成”解 $n$ 个互不干扰的简单方程”。
• 几何直觉（它在空间中是什么样子？）：先看行图景（row picture）。一个方程 $a_{i1}x_1+\cdots+a_{in}x_n=b_i$ 是 $\mathbb{R}^n$ 中的一张超平面（$n=2$ 时是一条直线）。解 $\mathbf{x}$ 是所有超平面的公共交点。消元做的操作是”用第一张超平面去剪切第二张超平面”——把第二张平面绕着它与第一张的交线旋转，直到它变得”更竖直”。两张平面的交线在整个旋转过程中一动不动，因为新平面就是”旧平面 + 第一张平面的倍数”，凡是同时落在旧平面和第一张平面上的点，在新平面上的取值也不变。所以公共交点（更一般地：公共交集）自始至终不变。这就是”同解变形”的几何本质。 再看列图景（column picture）：消元同时改动 $A$ 的行与 $\mathbf{b}$ 的分量（施加的是同一批行变换）。看起来组合问题被换掉了，但要知道：我们对等式 $A\mathbf{x}=\mathbf{b}$ 两边同时左乘了同一个可逆矩阵 $E$，即 $EA\mathbf{x}=E\mathbf{b}$。这就是为什么我们可以只对 $[A\mid\mathbf{b}]$ 操作而不必操心 $\mathbf{x}$——$\mathbf{x}$ 自始至终是同一个未知向量，只是它要组合的那组”原料列”从 $A$ 的列换成了 $EA$ 的列，而”目标”从 $\mathbf{b}$ 换成了 $E\mathbf{b}$。原料和目标一起换，配方 $\mathbf{x}$ 不变。

• 具体示例：方程组 \(x+2y=3,\qquad 3x+8y=11\) 两条直线交于 $(1,1)$（验证：$1+2\cdot1=3$ ✓，$3\cdot1+8\cdot1=11$ ✓）。用第一式消去第二式的 $x$：第二式减去第一式的 $3$ 倍，得 $0x+2y=2$，即 $y=1$。两条新直线 $x+2y=3$ 与 $y=1$ 的交点仍是 $(1,1)$——第一张直线没动，第二张绕交点转了。 写成矩阵语言：$\mathbf{b}=\begin{bmatrix}3\\11\end{bmatrix}$， \(E_{21}=\begin{bmatrix}1&0\\-3&1\end{bmatrix},\qquad E_{21}A=\begin{bmatrix}1&0\\-3&1\end{bmatrix}\begin{bmatrix}1&2\\3&8\end{bmatrix}=\begin{bmatrix}1&2\\0&2\end{bmatrix},\qquad E_{21}\mathbf{b}=\begin{bmatrix}1&0\\-3&1\end{bmatrix}\begin{bmatrix}3\\11\end{bmatrix}=\begin{bmatrix}3\\2\end{bmatrix}\) 于是新方程组是 $x+2y=3$ 与 $2y=2$——解仍是 $x=1,y=1$。解集 $\{(1,1)\}$ 完全没变。

  把这件事画成图（行图景，$n=2$）：

  消元前的两张直线                消元后的两张直线
                                          y
     y                                    |    x + 2y = 3
     |  x+2y=3                            |   /
     | /                                  |  /
     |/  *  <- 交点 (1,1)                1|--*  <- 交点仍是 (1,1)
   --+-------- x                      ----+-------- x
     |    \                             y=1
     |     \  3x+8y=11
     |      \                            第一张直线一动不动；
                                           第二张绕交点旋转成水平线。
   两张直线的交点 = 方程组的解            交点从未移动 => 解集不变。

注意第二张直线绕交点旋转——它上面除了交点以外的每一点都在动，但交点本身是旋转轴上的不动点。这就是”消元不改变解集”的完整几何图像。

消元矩阵（Elementary Matrix）$E$：从单位阵”改一格”

• 定义与目的：$E_{21}$ 表示”把第 2 行减去 $l_{21}$ 倍的第 1 行“这个行变换。它的构造规则只有一句：取单位阵 $I$，把 $(2,1)$ 位置的那个 $0$ 改成 $-l_{21}$。 其余位置一律照抄。它存在的意义是：把”一个算法步骤”变成一个”可以乘法验证的数学对象”，于是消元过程可以被整体追踪、可以求逆、可以打包成一个矩阵。
• 几何直觉（它在空间中是什么样子？）：$E$ 是一个剪切（shear）。它不动第 1 行所在的那张平面（所有第 1 个坐标相同的点），只把空间沿第 1 个坐标方向整体斜切。想象一副扑克牌，第一张牌按住不动，下面每一张沿 $x_1$ 方向滑一段距离——体积不变、不翻转、不塌陷。所以 $E$ 一定可逆（把牌滑回来即可），且 $\det E = 1$。

• 具体示例：$I$ 改一格 → \(E_{21}=\begin{bmatrix}1&0&0\\-3&1&0\\0&0&1\end{bmatrix}\) 用它乘 $A=\begin{bmatrix}1&2&1\\3&8&1\\0&4&1\end{bmatrix}$： \(E_{21}A=\begin{bmatrix}1&2&1\\0&2&-2\\0&4&1\end{bmatrix}\) 第 2 行变成了 $(3,8,1)-3\cdot(1,2,1)=(0,2,-2)$。注意第 1、3 行原封不动——因为 $E_{21}$ 的第 1、3 行就是 $I$ 的第 1、3 行。

  把”剪切”画出来（$3\times3$ 例子里的 $2\times2$ 核心 $E=\begin{bmatrix}1&0\\-3&1\end{bmatrix}$， 它的两列是 $(1,-3)$ 与 $(0,1)$，故 $\mathbf{e}_2$ 不动、$\mathbf{e}_1$ 被压低）：

   E 是一个剪切: 保持沿 e2 方向的直线不动, 把 e1 往下"拉" 3 个单位

       x2                          x2
        ^                           ^
        |     (1,1)                 |     (1,1)
        |      *                    |      *
        |     /|                    |     /|
        |    / |                    |    / |
   -----+---/--+----> x1       -----+---/--+----> x1
        |  /   |                    |  /   |
        | /    |                 (1,-3)   |
      (1,0)  e2 不动                 *    e2=(0,1) 仍不动
        |                             |
   第2列 = (0,1) 不变            第1列 = (1,-3): e1 被拉到下方

   单位方格 (面积 1) 被剪成平行四边形, 面积仍为 1
   => det E = 1*1 - 0*(-3) = 1, 且 E 一定可逆 (反向推回去即可)

这正是”消元不改变体积、也不改变可逆性”的微观图像：每一步 $E$ 都是一次纯粹的剪切——一个方向按住不动，另一个方向整体滑动。平行四边形的底与高都没变，所以面积恒为 $1$，$\det E=1$。

左乘 = 行变换，右乘 = 列变换

• 定义与目的：区分”$E$ 在左边”和”$E$ 在右边”是所有初学者最容易混淆的地方。一句话记住：左乘 $E$（$EA$）动的是 $A$ 的行；右乘 $E$（$AE$）动的是 $A$ 的列。
• 几何直觉（它在空间中是什么样子？）：可以把矩阵乘法读成”对 $A$ 的每一行做同一件事”和”对 $A$ 的每一列做同一件事”两种。左乘时，$E$ 的第 $i$ 行规定”结果第 $i$ 行是原来哪些行的组合”；右乘时，$E$ 的第 $j$ 列规定”结果第 $j$ 列是原来哪些列的组合”。
• 具体示例：取 $M=\begin{bmatrix}1&2\\3&4\end{bmatrix}$，$E=\begin{bmatrix}1&0\\3&1\end{bmatrix}$。 \(EM=\begin{bmatrix}1&2\\6&10\end{bmatrix}\quad(\text{第 2 行} = \text{原第 2 行} + 3\times\text{原第 1 行})\) \(ME=\begin{bmatrix}7&2\\15&4\end{bmatrix}\quad(\text{第 1 列} = \text{原第 1 列} + 3\times\text{原第 2 列})\) 两者完全不同。消元只使用左乘。

主元（Pivot）与零主元、行交换（Permutation）$P$

• 定义与目的：第 $k$ 步消元时用来消去下面各行第 $k$ 列系数的那个数，叫做第 $k$ 个主元。它绝对不能是 $0$——因为乘数 $l_{ik}=a_{ik}/a_{kk}$ 要用它作分母。如果主元是 $0$，就必须交换行，把下面某一列非零的行换上来。
• 几何直觉（它在空间中是什么样子？）：主元是”当前还没被清理掉的那个方向上的斜率”。主元为 $0$ 意味着当前这张平面在这个方向上已经平躺，无法再去剪切别人，只能换一张来当”基准面”。交换两张平面不改变它们的交集——所以换行同样不改变解集。
• 具体示例：$Z=\begin{bmatrix}0&2&1\\1&3&2\\2&1&1\end{bmatrix}$ 的第一个主元是 $0$，无法开工。交换第 1、2 行： \(P=\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix},\qquad PZ=\begin{bmatrix}1&3&2\\0&2&1\\2&1&1\end{bmatrix}\) 这下第一个主元是 $1$，可以继续。（$P$ 就是”把 $I$ 的第 1、2 行交换”得到的矩阵。）

置换矩阵（Permutation Matrix）$P$

• 定义与目的：每一行、每一列都恰好有一个 $1$，其余全为 $0$ 的方阵。$n$ 阶置换矩阵一共有 $n!$ 个。左乘它 = 按某种方式重排行。
• 几何直觉（它在空间中是什么样子？）：$P$ 是空间中的刚性重排——把坐标轴整体搬来搬去，不拉伸、不剪切、不塌陷。所以 $\det P=\pm1$，而且 $P$ 永远是正交矩阵（orthogonal），这保证了 $P$ 一定可逆。
• 具体示例： \(P_{13}=\begin{bmatrix}0&0&1\\0&1&0\\1&0&0\end{bmatrix},\qquad P_{13}\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}=\begin{bmatrix}7&8&9\\4&5&6\\1&2&3\end{bmatrix}\) 行序被完全颠倒。$2\times2$ 的 $\begin{bmatrix}0&1\\1&0\end{bmatrix}$ 满足 $P^2=I$，因此 $P^{-1}=P$；事实上对任何置换矩阵都有 $P^{-1}=P^{\mathsf{T}}$（因为 $P$ 正交）。

矩阵乘法的四种视角

这是 Strang 反复强调的”一鱼四吃”。设 $A$ 是 $m\times n$，$B$ 是 $n\times p$，则 $C=AB$ 是 $m\times p$。

• 定义与目的：四种视角不是四种算法（结果完全相同），而是四种理解通道。做题用视角①，论证明性质用②③，看到”低秩”“秩一分解”用④。
• 几何直觉（它在空间中是什么样子？）：
  • 视角① 行 $\times$ 列（点积）：$c_{ij}=(\text{第 }i\text{行})\cdot(\text{第 }j\text{列})$。最机械，最可靠，$O(n)$ 次乘法算一个元素。
  • 视角② 整列的组合：$AB$ 的第 $j$ 列 $=A\cdot(B\text{ 的第 }j\text{ 列})$。也就是说：$B$ 的每一列是配方，$A$ 的列是原料，$AB$ 的列就是配出来的成品。 这直接给出列空间的关系 $C(AB)\subseteq C(A)$。
  • 视角③ 整行的组合：$AB$ 的第 $i$ 行 $= (A\text{ 的第 }i\text{ 行})\cdot B$。也就是$A$ 的每一行对 $B$ 的各行做线性组合。这给出行空间的关系 $C((AB)^{\mathsf{T}})\subseteq C(B^{\mathsf{T}})$。
  • 视角④ 外积之和：$AB=\sum_{k=1}^{n}(\text{$A$ 的第 }k\text{ 列})\,(\text{$B$ 的第 }k\text{ 行})$，即 $n$ 个 $m\times p$ 的秩一矩阵相加。这是四个视角中信息量最大的一个：它说明 $AB$ 的秩等于”真正需要的项数”，也说明任何矩阵都是秩一矩阵的和，这正是后面 SVD 的思想雏形。
• 具体示例：取 \(A=\begin{bmatrix}1&2\\3&4\end{bmatrix},\qquad B=\begin{bmatrix}5&6\\7&8\end{bmatrix}\) 视角①（点积）：$c_{11}=1\cdot5+2\cdot7=19$，$c_{12}=1\cdot6+2\cdot8=22$，$c_{21}=3\cdot5+4\cdot7=43$，$c_{22}=3\cdot6+4\cdot8=50$，故 \(AB=\begin{bmatrix}19&22\\43&50\end{bmatrix}\) 视角②（列的组合）：$AB$ 的第 1 列 $=A\begin{bmatrix}5\\7\end{bmatrix}=5\begin{bmatrix}1\\3\end{bmatrix}+7\begin{bmatrix}2\\4\end{bmatrix}=\begin{bmatrix}19\\43\end{bmatrix}$；第 2 列 $=A\begin{bmatrix}6\\8\end{bmatrix}=\begin{bmatrix}22\\50\end{bmatrix}$。✓ 视角③（行的组合）：$AB$ 的第 1 行 $=\begin{bmatrix}1&2\end{bmatrix}B=1\cdot(5,6)+2\cdot(7,8)=(19,22)$；第 2 行 $=\begin{bmatrix}3&4\end{bmatrix}B=(43,50)$。✓ 视角④（外积之和）： \(\begin{bmatrix}1\\3\end{bmatrix}\begin{bmatrix}5&6\end{bmatrix}+\begin{bmatrix}2\\4\end{bmatrix}\begin{bmatrix}7&8\end{bmatrix}=\begin{bmatrix}5&6\\15&18\end{bmatrix}+\begin{bmatrix}14&16\\28&32\end{bmatrix}=\begin{bmatrix}19&22\\43&50\end{bmatrix}\ \checkmark\)

计算步骤与手算演示

示例 1（主讲）：用增广矩阵完整消元 $A\mathbf{x}=\mathbf{b}$

取 Strang 书上的标准例子 \(A=\begin{bmatrix}1&2&1\\3&8&1\\0&4&1\end{bmatrix},\qquad \mathbf{b}=\begin{bmatrix}2\\12\\2\end{bmatrix}\)

先写出增广矩阵（augmented matrix）$[A\mid\mathbf{b}]$。把 $\mathbf{b}$ 并排挂在 $A$ 右边当成第 4 列，好处是从此以后每一次行变换都”顺手”作用在 $\mathbf{b}$ 上，不用另外记账：

[A | b] =
  [  1   2   1 |   2 ]        <- row 1
  [  3   8   1 |  12 ]        <- row 2
  [  0   4   1 |   2 ]        <- row 3

步骤 1：构造 $E_{21}$，消去第 2 行的第一个元素。

第 1 列的主元是 $a_{11}=1$。要消掉 $a_{21}=3$，乘数是 $l_{21}=a_{21}/a_{11}=3/1=3$，操作是 $R_2\leftarrow R_2-3R_1$。

对应的消元矩阵就是把 $I_3$ 的 $(2,1)$ 位置从 $0$ 改成 $-3$： \(E_{21}=\begin{bmatrix}1&0&0\\-3&1&0\\0&0&1\end{bmatrix}\)

逐行验算 $E_{21}\cdot[A\mid\mathbf{b}]$：

• 第 1 行 $=1\times$ 原第 1 行 $=(1,2,1,2)$
• 第 2 行 $=-3\times$ 原第 1 行 $+1\times$ 原第 2 行 $=(3,8,1,12)-3(1,2,1,2)=(0,2,-2,6)$
• 第 3 行 $=1\times$ 原第 3 行 $=(0,4,1,2)$

after E21:  [  1   2   1 |   2 ]
            [  0   2  -2 |   6 ]     <- row2 - 3*row1
            [  0   4   1 |   2 ]

E21*b = ( 2, 6, 2 )^T

步骤 2：构造 $E_{31}$，消去第 3 行的第一个元素。

$A$ 的 $a_{31}=0$ 本来就是 $0$，乘数 $l_{31}=0/1=0$。于是 \(E_{31}=\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}=I\) 这一步是”空操作”。不要因为它是 $I$ 就觉得这一步多余——把它写出来，才能让 $L$ 的对角线以下三个位置 $(2,1),(3,1),(3,2)$ 有统一的记账格式，第 4 讲 $A=LU$ 时你会感谢这个习惯。

after E31:  [  1   2   1 |   2 ]      (unchanged)
            [  0   2  -2 |   6 ]
            [  0   4   1 |   2 ]

步骤 3：构造 $E_{32}$，消去第 3 行的第二个元素。

现在的第 2 个主元是 $a_{22}=2$（它是上一轮更新后的值，不是原来的 $8$）。要消掉 $a_{32}=4$，乘数 $l_{32}=4/2=2$，操作是 $R_3\leftarrow R_3-2R_2$。 \(E_{32}=\begin{bmatrix}1&0&0\\0&1&0\\0&-2&1\end{bmatrix}\)

逐行验算：

• 第 1 行不变：$(1,2,1,2)$
• 第 2 行不变：$(0,2,-2,6)$
• 第 3 行 $=-2\times$ 第 2 行 $+1\times$ 原第 3 行 $=(0,4,1,2)-2(0,2,-2,6)=(0,0,5,-10)$

[U | c] =   [  1   2   1 |   2 ]
            [  0   2  -2 |   6 ]
            [  0   0   5 | -10 ]     <- row3 - 2*row2

到此得到上三角的 $U$ 与变换后的右端 $\mathbf{c}$： \(U=\begin{bmatrix}1&2&1\\0&2&-2\\0&0&5\end{bmatrix},\qquad \mathbf{c}=\begin{bmatrix}2\\6\\-10\end{bmatrix}\)

完整 ASCII 图景：消元如何一步步”清扫”左下角

  start              after E21          after E31          after E32
  ┌         ┐        ┌         ┐        ┌         ┐        ┌         ┐
  │ 1  2  1 │        │ 1  2  1 │        │ 1  2  1 │        │ 1  2  1 │  <- pivot 1
  │ 3  8  1 │  --->  │ 0  2 -2 │  --->  │ 0  2 -2 │  --->  │ 0  2 -2 │  <- pivot 2
  │ 0  4  1 │        │ 0  4  1 │        │ 0  4  1 │        │ 0  0  5 │  <- pivot 5
  └         ┘        └         ┘        └         ┘        └         ┘
   x  x  x            .  x  x            .  x  x            .  x  x
   x  x  x            .  x  x            .  x  x            .  x  x
   .  x  x            .  x  x            .  x  x            .  .  x
   (x = 待处理)        (x = 待处理)        第3行首元素本就是0     上三角完成

三个主元依次是 $1,\ 2,\ 5$。三个主元全部非零 $\iff$ $A$ 可逆 $\iff$ 消元无需换行就能走完。

步骤 4：回代（back substitution）。

从最后一行往上解：

• 第 3 行：$5x_3=-10\Rightarrow \boxed{x_3=-2}$
• 第 2 行：$2x_2-2x_3=6\Rightarrow 2x_2-2(-2)=6\Rightarrow 2x_2=2\Rightarrow \boxed{x_2=1}$
• 第 1 行：$x_1+2x_2+x_3=2\Rightarrow x_1+2(1)+(-2)=2\Rightarrow \boxed{x_1=2}$

于是 \(\mathbf{x}=\begin{bmatrix}2\\1\\-2\end{bmatrix}\)

回代验算：$A\mathbf{x}=\begin{bmatrix}1&2&1\\3&8&1\\0&4&1\end{bmatrix}\begin{bmatrix}2\\1\\-2\end{bmatrix}=\begin{bmatrix}2+2-2\\6+8-2\\0+4-2\end{bmatrix}=\begin{bmatrix}2\\12\\2\end{bmatrix}=\mathbf{b}$ ✓

【计算机制解说】：为什么”左乘一串 $E$”就等于整个消元过程？ 三个 $E$ 是按顺序作用的：先 $E_{21}$，再 $E_{31}$，最后 $E_{32}$。写成公式就是 \(E_{32}\big(E_{31}(E_{21}A)\big)=U\) 由矩阵乘法的结合律（下一讲会证明，本讲先用），括号可以重新打： \((E_{32}E_{31}E_{21})A=U\) 也就是说，整个消元过程可以压缩成一个矩阵 $E=E_{32}E_{31}E_{21}$ 左乘 $A$。验算一下： \(E_{32}E_{21}=\begin{bmatrix}1&0&0\\0&1&0\\0&-2&1\end{bmatrix}\begin{bmatrix}1&0&0\\-3&1&0\\0&0&1\end{bmatrix}=\begin{bmatrix}1&0&0\\-3&1&0\\6&-2&1\end{bmatrix}\) （第 3 行 $=-2\times(-3,1,0)+(0,0,1)=(6,-2,1)$。注意 $E_{31}=I$ 不产生影响。） 于是 \(E=E_{32}E_{31}E_{21}=\begin{bmatrix}1&0&0\\-3&1&0\\6&-2&1\end{bmatrix},\qquad EA=\begin{bmatrix}1&2&1\\0&2&-2\\0&0&5\end{bmatrix}=U\ \checkmark\) 而 $E\mathbf{b}=(2,6,-10)^{\mathsf{T}}=\mathbf{c}$ ✓。

为什么”解集不变”在这里看得最清楚：每个 $E$ 都可逆（把 $(2,1)$ 的 $-3$ 改回 $+3$ 就是它的逆），所以 $A\mathbf{x}=\mathbf{b}\iff EA\mathbf{x}=E\mathbf{b}\iff U\mathbf{x}=\mathbf{c}$。可逆矩阵左乘不丢失任何信息，这就是”同解变形”的代数证明。

示例 2：主元为 $0$ —— 必须换行

取 \(Z=\begin{bmatrix}0&2&1\\1&3&2\\2&1&1\end{bmatrix},\qquad \mathbf{b}=\begin{bmatrix}1\\2\\3\end{bmatrix}\)

第一个主元 $z_{11}=0$，没法作分母。先交换第 1、2 行： \(P=\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix},\qquad PZ=\begin{bmatrix}1&3&2\\0&2&1\\2&1&1\end{bmatrix},\qquad P\mathbf{b}=\begin{bmatrix}2\\1\\3\end{bmatrix}\)

[PZ | Pb] =
  [  1   3   2 |   2 ]        l21 = 0   (第2行首元素已是0)
  [  0   2   1 |   1 ]
  [  2   1   1 |   3 ]        l31 = 2/1 = 2

步骤 1：$R_3\leftarrow R_3-2R_1$，乘数 $l_{31}=2$。 第 3 行 $=(2,1,1,3)-2(1,3,2,2)=(0,-5,-3,-1)$。

  [  1   3   2 |   2 ]
  [  0   2   1 |   1 ]        l32 = -5/2 = -2.5
  [  0  -5  -3 |  -1 ]

步骤 2：第 2 个主元是 $2$，要消掉 $a_{32}=-5$，乘数 $l_{32}=-5/2$，操作 $R_3\leftarrow R_3-(-5/2)R_2$，即 $R_3\leftarrow R_3+\frac52 R_2$。 第 3 行 $=(0,-5,-3,-1)+\frac52(0,2,1,1)=(0,0,-\frac12,\frac32)$。

[U | c] =
  [  1   3     2 |   2   ]
  [  0   2     1 |   1   ]
  [  0   0  -1/2 |  3/2  ]

回代：

• $-\frac12 x_3=\frac32\Rightarrow \boxed{x_3=-3}$
• $2x_2+x_3=1\Rightarrow 2x_2-3=1\Rightarrow \boxed{x_2=2}$
• $x_1+3x_2+2x_3=2\Rightarrow x_1+6-6=2\Rightarrow \boxed{x_1=2}$

\(\mathbf{x}=\begin{bmatrix}2\\2\\-3\end{bmatrix}\) 回代验算：$Z\mathbf{x}=(0\cdot2+2\cdot2+1\cdot(-3),\ 1\cdot2+3\cdot2+2\cdot(-3),\ 2\cdot2+1\cdot2+1\cdot(-3))=(1,2,3)^{\mathsf{T}}=\mathbf{b}$ ✓

【计算机制解说】：为什么”换行”不改变解集，而且为什么 $P^{-1}=P^{\mathsf{T}}$？ 第一问：交换两张平面（两个方程）的书写顺序，方程组本身一字未变——只是第一行和第二行调了个位置，联立方程组的解当然是同一个。 第二问：$P$ 是把 $I$ 的某些行互换得到的。互换操作做两次就回到原样（$\text{swap}^2=\mathrm{id}$），所以 $PP=I$，即 $P^{-1}=P$。又因为 $P$ 的每一行每一列恰好一个 $1$，转置只是把那些 $1$ 沿对角线翻过去，位置集合不变，所以 $P^{\mathsf{T}}=P$。两者合起来得 $P^{-1}=P^{\mathsf{T}}$。几何上：$P$ 是刚性的坐标重排，保持长度与夹角，所以它是正交矩阵（orthogonal），而”正交 $\Rightarrow$ 逆 = 转置”。

顺带记账：这个例子的 $L$ 与 $U$ 为 \(L=\begin{bmatrix}1&0&0\\0&1&0\\2&-\frac52&1\end{bmatrix},\qquad U=\begin{bmatrix}1&3&2\\0&2&1\\0&0&-\frac12\end{bmatrix},\qquad LU=PZ=\begin{bmatrix}1&3&2\\0&2&1\\2&1&1\end{bmatrix}\ \checkmark\) （注意 $L$ 的 $(2,1)$ 位置是 $0$，因为换行后第 2 行首元素已是 $0$，没有消元动作。$L$ 的对角线全是 $1$，这是”不缩放主元行”记账法的固定格式。）

示例 3：消元代价——为什么大约是 $n^3/3$ 次乘法

设 $A$ 是 $n\times n$。第 $k$ 步消元（$k=1,2,\dots,n-1$）要处理主元下面的 $n-k$ 行，每一行需要：

• $1$ 次除法算乘数 $l_{ik}=a_{ik}/a_{kk}$；
• $(n-k+1)$ 次乘法，用于更新第 $k$ 列到第 $n$ 列再加上右端 $\mathbf{b}$ 那一列。

所以每步的乘法数是 $(n-k)(n-k+1)$，总计 \(\text{ops}(n)=\sum_{k=1}^{n-1}(n-k)(n-k+1)=\sum_{j=1}^{n-1}j(j+1)=\sum_{j=1}^{n-1}j^2+\sum_{j=1}^{n-1}j=\frac{(n-1)n(2n-1)}{6}+\frac{(n-1)n}{2}=\frac{n^3-n}{3}\)

具体数字：

  n     实际乘法次数 (n^3-n)/3      n^3/3        相对误差
  3          8                     9.0          11%
  4         20                    21.3           6%
  5         40                    41.7           4%
 10        330                   333.3           1%
100     333300                333333.3          0.01%

n=3 的手工分解（可直接核对）：

  step k=1: 主元下方 2 行, 每行更新 3 个数 -> 2*3 = 6 次乘法
  step k=2: 主元下方 1 行, 每行更新 2 个数 -> 1*2 = 2 次乘法
  step k=3: 主元下方 0 行               -> 0
  ------------------------------------------------
  合计 = 8 次乘法  (n=3 时 8 vs n^3/3=9)

【计算机制解说】：为什么主项是 $n^3/3$ 而不是 $n^3$？ 因为”工作量按列递减”。第 1 步要更新大约 $(n-1)\times n\approx n^2$ 个元素，第 2 步约 $(n-2)\times n$ 个，第 $k$ 步约 $(n-k)\times(n-k+1)\approx(n-k)^2$ 个。把它们加起来就是 $\sum_{j=1}^{n}j^2\approx\int_0^n j^2\,dj=n^3/3$。 一个更直观的说法：矩阵里约有 $n^2$ 个元素，而平均每个元素在整个消元过程中被”从后往前”更新了约 $n/3$ 次（第 1 行只被用来消元、自己不更新；越靠下的行被更新得越少），于是总量 $n^2\cdot n/3=n^3/3$。 为什么实际值 $8$ 比 $n^3/3=9$ 小？ 因为精确公式是 $\frac{n^3-n}{3}$——多出来的 $-\frac n3$ 是 $\sum j$ 这一低阶项带来的修正。$n=3$ 时修正量恰好是 $1$（$9-1=8$ 与表格吻合）；$n=100$ 时修正量约 $33$，相对于 $333333$ 已完全可忽略。所以 $n^3/3$ 是”渐近主项”，不是精确计数。 这个 $n^3/3$ 是线性代数的”计价单位”：它说明解 $n$ 个未知数的 $n$ 个方程，代价是 $n$ 的三次方量级。当 $n=1000$ 时约 $3.3\times10^8$ 次运算——现代电脑零点几秒；当 $n=10^6$ 时约 $3.3\times10^{17}$ 次——就需要特殊结构（稀疏、带状、迭代法）了。对比一下：回代只要 $n^2/2$（$n$ 个未知数，第 $k$ 个只与前 $k$ 个有关），所以”消元”而非”回代”才是整个求解过程的成本瓶颈。这也解释了为什么第 4 讲的 $LU$ 分解值得：分解一次花 $n^3/3$，之后每个新 $\mathbf{b}$ 只要 $n^2$。

示例 4：四种乘法视角的 $3\times3$ 完整对照

取 \(A_3=\begin{bmatrix}1&2&3\\4&5&6\\7&8&10\end{bmatrix},\qquad B_3=\begin{bmatrix}1&0&2\\0&1&0\\3&0&1\end{bmatrix}\) 先算积 $A_3B_3$：

  A3 * B3 =
   [ 1*1+2*0+3*3   1*0+2*1+3*0   1*2+2*0+3*1 ]   [ 10   2   5 ]
   [ 4*1+5*0+6*3   4*0+5*1+6*0   4*2+5*0+6*1 ] = [ 22   5  14 ]
   [ 7*1+8*0+10*3  7*0+8*1+10*0  7*2+8*0+10*1]   [ 37   8  24 ]

• 视角①（点积）：$c_{22}=(4,5,6)\cdot(0,1,0)=5$ ✓（这就是上面矩阵中心的那个 $5$）。
• 视角②（列的组合）：$A_3$ 乘 $B_3$ 的每一列：
  • $A_3\begin{bmatrix}1\\0\\3\end{bmatrix}=1\begin{bmatrix}1\\4\\7\end{bmatrix}+3\begin{bmatrix}3\\6\\10\end{bmatrix}=\begin{bmatrix}10\\22\\37\end{bmatrix}$ = 第 1 列 ✓
  • $A_3\begin{bmatrix}0\\1\\0\end{bmatrix}=\begin{bmatrix}2\\5\\8\end{bmatrix}$ = 第 2 列 ✓
  • $A_3\begin{bmatrix}2\\0\\1\end{bmatrix}=2\begin{bmatrix}1\\4\\7\end{bmatrix}+\begin{bmatrix}3\\6\\10\end{bmatrix}=\begin{bmatrix}5\\14\\24\end{bmatrix}$ = 第 3 列 ✓
• 视角③（行的组合）：$A_3$ 的每一行乘 $B_3$：
  • $\begin{bmatrix}1&2&3\end{bmatrix}B_3=(1\cdot(1,0,2)+2\cdot(0,1,0)+3\cdot(3,0,1))=(10,2,5)$ ✓
  • $\begin{bmatrix}4&5&6\end{bmatrix}B_3=(22,5,14)$ ✓
  • $\begin{bmatrix}7&8&10\end{bmatrix}B_3=(37,8,24)$ ✓
• 视角④（列 $\otimes$ 行的外积之和）： \(\begin{bmatrix}1\\4\\7\end{bmatrix}\begin{bmatrix}1&0&2\end{bmatrix}=\begin{bmatrix}1&0&2\\4&0&8\\7&0&14\end{bmatrix},\quad \begin{bmatrix}2\\5\\8\end{bmatrix}\begin{bmatrix}0&1&0\end{bmatrix}=\begin{bmatrix}0&2&0\\0&5&0\\0&8&0\end{bmatrix},\quad \begin{bmatrix}3\\6\\10\end{bmatrix}\begin{bmatrix}3&0&1\end{bmatrix}=\begin{bmatrix}9&0&3\\18&0&6\\30&0&10\end{bmatrix}\) 三块相加：$(1+0+9,\ 0+2+0,\ 2+0+3)=(10,2,5)$，正是第 1 行 ✓；逐块累加得到整个 $A_3B_3$。

【计算机制解说】：外积视角为什么最重要？ 因为每一个外积 $\mathbf{u}\mathbf{v}^{\mathsf{T}}$ 都是秩一矩阵（rank-one）：它的每一列都是 $\mathbf{u}$ 的倍数，每一行都是 $\mathbf{v}^{\mathsf{T}}$ 的倍数，整个矩阵的信息量只有 $m+n$ 个数（而不是 $mn$ 个）。$AB=\sum_k \mathbf{a}_k\mathbf{b}_k^{\mathsf{T}}$ 因此把”矩阵乘法”翻译成”把 $n$ 个秩一矩阵叠加起来”。当 $A$ 或 $B$ 依赖的数据实际上只要少数几个方向时，很多项可以扔掉——这正是第 29 讲 SVD $A=\sigma_1\mathbf{u}_1\mathbf{v}_1^{\mathsf{T}}+\cdots$ 的雏形。另外，视角④立刻给出秩不等式： \(\operatorname{rank}(AB)\le\min(\operatorname{rank}A,\operatorname{rank}B)\) 因为 $AB$ 只用到了 $A$ 的 $n$ 个列和 $B$ 的 $n$ 个行。

示例 5：用视角④立刻看穿一个秩一矩阵

取 $\mathbf{u}=\begin{bmatrix}1\\2\\3\end{bmatrix}$，$\mathbf{v}=\begin{bmatrix}4\\5\end{bmatrix}$，构造 $\mathbf{u}\mathbf{v}^{\mathsf{T}}=\begin{bmatrix}4&5\\8&10\\12&15\end{bmatrix}$。 不需要任何消元就能断言：这个 $3\times2$ 矩阵的秩是 $1$。理由：第 1 列是 $4\mathbf{u}$，第 2 列是 $5\mathbf{u}$——两列都是 $\mathbf{u}$ 的倍数，必然共线。三行之间也成比例（第 2 行 $=2\times$ 第 1 行，第 3 行 $=3\times$ 第 1 行）。 用消元验证：$R_2\leftarrow R_2-2R_1$ 得 $(0,0)$，$R_3\leftarrow R_3-3R_1$ 得 $(0,0)$，只剩一个主元。

  [  4   5 ]                  [  4   5 ]
  [  8  10 ]   --消元-->      [  0   0 ]      只有一个主元 => rank = 1
  [ 12  15 ]                  [  0   0 ]

这个例子的意义：视角④把”秩”从一个需要算出来的量变成了一个可以看出来的结构。矩阵 $\mathbf{u}\mathbf{v}^{\mathsf{T}}$ 的”信息”只有 $3+2=5$ 个数（$\mathbf{u}$ 与 $\mathbf{v}$），而它表面上占据了 $3\times2=6$ 个存储位置——冗余是显而易见的。SVD 做的事，就是把任意矩阵写成这种”稀疏信息”的叠加，并按重要性排序。

矩阵分解的核心思想

本讲是 $A=LU$ 分解的舞台搭建。把上面示例 1 的两边同时左乘 $E^{-1}$： \(EA=U\quad\Longrightarrow\quad A=E^{-1}U=LU,\qquad L=E^{-1}=(E_{32}E_{31}E_{21})^{-1}=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}\)

逐个求逆（消元矩阵的逆只需把那个非对角元素变号）：

  E21 = [ 1  0  0 ]        E21^-1 = [ 1  0  0 ]
        [-3  1  0 ]   -->            [ 3  1  0 ]
        [ 0  0  1 ]                  [ 0  0  1 ]

  E31 = I                  E31^-1 = I

  E32 = [ 1  0  0 ]        E32^-1 = [ 1  0  0 ]
        [ 0  1  0 ]   -->            [ 0  1  0 ]
        [ 0 -2  1 ]                  [ 0  2  1 ]

  L = E21^-1 * E31^-1 * E32^-1 = [ 1  0  0 ]
                                 [ 3  1  0 ]
                                 [ 0  2  1 ]

验证 $LU=A$： \(\begin{bmatrix}1&0&0\\3&1&0\\0&2&1\end{bmatrix}\begin{bmatrix}1&2&1\\0&2&-2\\0&0&5\end{bmatrix}=\begin{bmatrix}1&2&1\\3&8&1\\0&4&1\end{bmatrix}=A\ \checkmark\)

这一步揭示了什么：

1. $L$ 是单位下三角（unit lower triangular，对角线全为 $1$），它的非对角线元素恰好就是消元乘数 $l_{21}=3,\ l_{31}=0,\ l_{32}=2$——甚至符号都不需要改。这就是为什么 Strang 说”$L$ 免费赠送”。
2. 乘数的顺序天然正确：$L=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}$ 中三个逆矩阵的顺序是 $21,31,32$（与消元顺序一致），而它们相乘后在 $(3,1)$ 位置得到的是 $0+0=0$（因为 $l_{31}=0$），在 $(3,2)$ 位置得到 $2$。如果顺序反了，就会出现 $-3\times2$ 之类的交叉项——这是 $LU$ 分解里”$L$ 的乘数居然不需要修正”这一奇迹的来源。
3. 对角线上是主元：$U$ 的对角线 $(1,2,5)$ 就是三个主元。第 18 讲将看到 $\det A=1\times2\times5=10$（本讲用余子式展开验算 $1(8\cdot1-1\cdot4)-2(3\cdot1-1\cdot0)+1(3\cdot4-8\cdot0)=4-6+12=10$ ✓）。
4. 有换行时：示例 2 给出的是 $PZ=LU$，即一般形式 $PA=LU$——这是第 4 讲的正式主题。

为什么这个分解值得单独讲一讲：解 $A\mathbf{x}=\mathbf{b}$ 用 $LU$ 的代价是”一次 $n^3/3$ 消元 + 每次回代 $n^2$”。如果固定 $A$、反复换不同的 $\mathbf{b}$（工程上极常见），$LU$ 一次分解后，每个新 $\mathbf{b}$ 只要 $O(n^2)$——这就是 $LU$ 相对于”每次重新消元”的全部价值。

“无换行”这个前提有多重要：一个小心的例子。本讲的 $A$ 恰好不需要换行（三个主元 $1,2,5$ 全部非零），所以 $A=LU$ 直接成立。如果像示例 2 那样第一个主元是 $0$，那么必须先换行，得到的是 $PA=LU$ 而不是 $A=LU$：

   A = [[0,2],[3,4]]     首个主元 a11 = 0, 无法开工

   P = [[0,1],[1,0]]     P*A = [[3,4],[0,2]] = U

   此时 L = I  (因为换行后 a21 已经是 0, 无需任何消元动作)
   但   A = [[0,2],[3,4]]  !=  L*U = [[3,4],[0,2]]

   => 必须写成  P*A = L*U  (此处 = U)

结论：$A=LU$ 只在”消元全程不必换行”时成立。置换矩阵 $P$ 是这件事的记账工具，它把”换过哪些行”完整记录下来。第 4 讲会把 $PA=LU$ 作为一般定理给出。 另一个必须记住的细节：$P$ 的选取也需要讲究策略。示例 2 里我们只是为了”不为零”而换行；实际数值计算中还要选绝对值最大的主元换上来（partial pivoting），否则浮点误差会被放大。这是第 4 讲的”数值稳定性”话题。

与其他讲次的关联

• 与第 1 讲：第 1 讲把 $A\mathbf{x}$ 解释为”$A$ 的列的组合”，本讲则说明消元不改变这个组合问题本身——它只是换一组更好用的列（$U$ 的列）来做同样的组合。
• 与第 4 讲（$A=LU$ 分解）：本讲已经把 $E$、$L$、$U$ 全部算好，第 4 讲只需把它们正式命名，讲清 $L$ 的乘数含义、$A=LU$ 与 $PA=LU$ 的完整版，以及”一次分解、多次回代”的工程价值。
• 与第 5 讲（转置、置换、向量空间）：置换矩阵 $P$ 的 $P^{-1}=P^{\mathsf{T}}$ 在本讲已出现，第 5 讲会把它放进”正交矩阵”的框架；转置与对称矩阵也在那里展开。
• 与第 6-10 讲（子空间）：消元得到的主元个数 = 秩 $r$；主元所在的列 = 主元列（pivot columns），它们构成 $C(A)$ 的一组基；自由变量对应 $N(A)$ 的基。所以消元是求四个基本子空间的唯一算法入口。
• 与第 18-20 讲（行列式）：$U$ 的对角元乘积 $=$ 主元的乘积 $=\det A$（在无换行时）；一般情形 $\det A=\pm\det P\prod(\text{pivots})$。$E$ 的 $\det$ 恒为 $1$ 正是”行减法不改变体积”。
• 与第 11-12 讲（图与网络）：消元代价 $n^3/3$ 是对稠密矩阵的估计；图的关联矩阵极度稀疏，实际代价远低于此——这就是稀疏消元的动机。
• 与第 14-17 讲（正交与 QR）：$A=LU$ 用下三角/上三角这组”代数上方便的基”；$A=QR$ 用正交矩阵这组”数值上稳定得多的基”。Gram-Schmidt 就是消元的正交版本。

关键要点

1. 消元 = 左乘一串可逆的消元矩阵：$E_{32}E_{31}E_{21}A=U$，因而 $A=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U=LU$。每个 $E$ 可逆 $\Rightarrow$ 解集不变 $\Rightarrow$ 对 $[A\mid\mathbf{b}]$ 直接动手是合法的。
2. $E_{ij}$ 的构造口诀：取 $I$，把 $(i,j)$ 位置的 $0$ 改成 $-l_{ij}$，其中 $l_{ij}=a_{ij}/a_{jj}$（当前主元）。它的逆只需把 $-l_{ij}$ 改回 $+l_{ij}$；$\det E=1$。
3. 左乘动行，右乘动列。消元一律左乘。
4. 主元不能是 $0$；是 $0$ 就必须换行，$P$ 是置换矩阵，满足 $P^{-1}=P^{\mathsf{T}}$，$\det P=\pm1$。一般结论 $PA=LU$。
5. 矩阵乘法四视角：$c_{ij}=(\text{行}_i)\cdot(\text{列}_j)$｜$AB$ 的列 $=A\times(B$ 的列$)$｜$AB$ 的行 $= (A$ 的行$)\times B$｜$AB=\sum_k \mathbf{a}_k\mathbf{b}_k^{\mathsf{T}}$（秩一矩阵之和）。
6. 消元代价 $\approx n^3/3$ 次乘法（精确值 $(n^3-n)/3$），量级上就是”$n^2$ 个元素各被更新约 $n/3$ 次”。

常见误区与注意事项

1. 把 $E_{21}$ 的符号写反。$E_{21}=\begin{bmatrix}1&0\\-3&1\end{bmatrix}$ 对应”$R_2\leftarrow R_2-3R_1$”，$(2,1)$ 位置是 $-3$。学生常写成 $+3$，然后发现 $E_{21}A$ 的第 2 行变成 $(3,8,1)+3(1,2,1)$——越消越大。
2. 用 $A$ 的原始元素当主元，而不是更新后的元素。示例 2 里第 2 个主元是更新后的 $2$，不是原来的 $3$ 或 $8$；乘数 $l_{32}=4/2=2$ 用的是更新后的 $a_{32}=4$ 与更新后的主元 $2$。用原值会得到完全错误的 $L$。
3. 对 $A$ 做行变换却忘记同步处理 $\mathbf{b}$。所以必须一开始就写增广矩阵 $[A\mid\mathbf{b}]$。等价地：先求 $E$，再算 $\mathbf{b}^{\prime}=E\mathbf{b}$——但手算时增广矩阵更不容易出错。
4. 以为”消元”和”行列式”无关，或者以为 $E$ 会改变 $\det A$。所有消元矩阵 $\det E=1$，所以 $\det U=\det A$；换行矩阵 $\det P=-1$，这才是 $PA=LU$ 里唯一需要小心符号的地方。
5. 把外积的次序号搞错。视角④是 $AB=\sum_{k}(\text{$A$ 的第 $k$ 列})(\text{$B$ 的第 $k$ 行})$——列乘行，不是行乘列。写成行乘列得到的每个块尺寸都不对（$1\times1$ 的标量，不是矩阵）。
6. 忘记 $P\mathbf{b}$。换行时 $\mathbf{b}$ 必须跟着换。很多人只换 $A$ 的行，忘了右端那一列，于是解出错误的 $\mathbf{x}$。

思考题（带答案）

Q1.（纯计算）用消元把下列方程组化成上三角、写出 $L$ 与 $U$、并回代求 $\mathbf{x}$： \(A=\begin{bmatrix}1&1&1\\2&3&5\\4&6&8\end{bmatrix},\qquad \mathbf{b}=\begin{bmatrix}2\\8\\14\end{bmatrix}\)

Q2.（概念理解）设 $E=\begin{bmatrix}1&0\\3&1\end{bmatrix}$ 是把 $I_2$ 的 $(2,1)$ 位置从 $0$ 改成 $3$ 得到的矩阵，$M=\begin{bmatrix}1&2\\3&4\end{bmatrix}$。 (a) 解释 $EM$ 和 $ME$ 各自的几何含义； (b) 求 $E^{-1}$，并说明为什么 $\det E=1$； (c) 判断 $EM=ME$ 是否成立。

Q3.（四视角）设 $A=\begin{bmatrix}1&2\\3&4\end{bmatrix}$，$B=\begin{bmatrix}1&0\\2&1\end{bmatrix}$。用四种视角分别计算 $AB$，并指出哪一种视角最能说明 $\operatorname{rank}(AB)\le\operatorname{rank}(A)$。