2.5 行阶梯形的存在性

前面的笔记说明如何做高斯消元，以及如何读取化简后的结果。本节问一个更理论化的问题：

为什么每个矩阵都可以期望有一个行阶梯形，甚至有一个最简行阶梯形？

这个问题很重要，因为行化简会在整个课程中反复出现：解方程组、找自由变量、测试张成、测试线性无关、求逆、求秩、建立基，都要用到它。若行阶梯形只是一堆例子，后面的理论便没有稳固基础。下面的定理说明：算法确实有保证能到达的目标。

要证明什么

定理 2.5.1

（REF 的存在性）

对每个矩阵 $C$，都存在某个与 $C$ 行等价的行阶梯形 $C^\#$。

定理 2.5.2

（RREF 的存在性）

对每个矩阵 $C$，都存在某个与 $C$ 行等价的最简行阶梯形 $C'$。

第一个定理说高斯消元总能到达阶梯形；第二个定理说，到达阶梯形后，进一步清理主元列总能到达最简形式。

对行数作归纳

REF 存在性的证明使用行数归纳。

定义 2.5.3

（归纳命题）

令 $P(m)$ 表示以下命题：若 $A$ 是一个有 $m$ 行的矩阵，则 $A$ 与某个同样有 $m$ 行的行阶梯形 $A^\#$ 行等价。

基本情况很直接。一行矩阵本身已经是行阶梯形：它要么是零行，要么唯一非零行的第一个非零项就是首项。

归纳步骤中，假设 $P(k)$ 成立，并令 $A$ 是一个有 $k+1$ 行的矩阵。

若 $A$ 是零矩阵，没有事情要证。否则，找出 $A$ 中最左边的非零列。在该列中，找出最上方的非零项；如有需要，将该行交换到第一行。把新的第一个主元值记为 $\beta$。

接着，用第一行把同一列中 $\beta$ 下方所有项清成零。矩阵便有分块形状

$$\begin{bmatrix} O_{1\times(j-1)} & \beta & u \\ O_{k\times(j-1)} & 0_k & V \end{bmatrix},$$

其中 $V$ 是一个有 $k$ 行的矩阵。

现在可对 $V$ 使用归纳假设。它可被行化简成某个行阶梯形 $V'$。把相应行变换作用在整个矩阵的下方 $k$ 行，得到

$$\begin{bmatrix} O_{1\times(j-1)} & \beta & u \\ O_{k\times(j-1)} & 0_k & V' \end{bmatrix}.$$

这个矩阵是行阶梯形：第一个主元在第 $j$ 列，其下方全为零；下方分块则由归纳假设已具备阶梯结构。

清理步骤合法，是因为 $\beta\ne0$：若其下方第 $i$ 行的项为 $\alpha_i$，就作 $R_i\leftarrow R_i-(\alpha_i/\beta)R_1$。第 $j$ 列之前仍然全为零。把 $V$ 的行变换移回整个矩阵时，每个行指标都加一；第一行保持不动，下方各行的零前缀也保持为零。若第 $j$ 列已经是最后一列，就没有右下方分块需要处理：其余各行此时全为零，直接完成这一步，不必对不存在的列再使用归纳假设。

定理 2.5.4

（REF 证明的结论）

由数学归纳法，每个正行数矩阵都与某个行阶梯形行等价。

例题 2.5.5

（在具体矩阵中看见较小分块）

考虑

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

最左非零列是第 $2$ 列。该列最上方项已经非零，所以可以把第一行中的 $\beta=2$ 当作第一个主元。清掉其下方项，得到

$$R_2\leftarrow R_2-2R_1,\qquad \begin{bmatrix} 0 & 2 & 1\\ 0 & 0 & 1\\ 0 & 0 & 5 \end{bmatrix}.$$

第一个主元右下方剩下的较小分块是

$$V= \begin{bmatrix} 1\\ 5 \end{bmatrix}.$$

这正是归纳证明的重点：整个矩阵不必一次处理完。第一个主元固定后，剩下的任务就是把一个行数较少的矩阵整理成行阶梯形。在这个例子中，再做一步 $R_3\leftarrow R_3-5R_2$，便得到

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

这已经是 REF。例子很小，但它展示了普遍证明中同一个“问题变小”的结构。

由 REF 到 RREF

第二部分从一个已经是行阶梯形的矩阵出发，目标是证明它可以在保持行等价的情况下变成最简行阶梯形。

此时归纳的参数是秩，也就是行阶梯形中的非零行数。

定理 2.5.6

（由 REF 到 RREF 的引理）

若 $A$ 是秩为 $r$ 的行阶梯形，则存在秩仍为 $r$、与 $A$ 行等价的最简行阶梯形 $A'$。

基本情况 $r=0$ 立即成立：秩为 $0$ 的行阶梯形是零矩阵，而零矩阵已经是 RREF。

证明

（为什么最后一个主元不会被归纳步骤破坏）

目标与加强的归纳假设。 我们证明比“存在”稍强的命题：有 $r$ 个非零行的 REF，可以只使用这些非零行化为 RREF，并保持原来的主元列。加强命题并非多余，它把下一步需要的信息保留下来。这里的 $r$ 只是 REF 中看得见的非零行数，并没有预先使用“秩与化简路径无关”的后续定理。$r=0$ 时不需要任何变换。

关键步骤。 假设加强命题对 $r=k$ 成立，现令 $A$ 有 $k+1$ 个主元，位于第 $d_1,\ldots,d_{k+1}$ 列。把第 $d_{k+1}$ 列之前的所有列记为左分块 $U$。它的前 $k$ 行组成一个有 $k$ 个主元的 REF，其余各行全为零。对这前 $k$ 行使用归纳假设。若 $k=0$，左分块全为零，甚至可能没有列，这一步直接略过。

为什么可以这样做。 在整个 $A$ 中，对相同的行指标执行这些变换。行变换必须作用于整行，不能只改 $U$ 中显示的那一部分。因此右分块也会改变，但第 $k+1$ 行及其下方各行完全不动。前 $k$ 个主元列已成为相应的标准坐标列，而最后的主元值 $\alpha=A_{k+1,d_{k+1}}$ 仍然非零。这里使用的是归纳假设提供的、只涉及前 $k$ 行的变换序列；任意一个能把 $U$ 化简的序列，未必能保证最后的主元行保持原样。

清理步骤与边界条件。 将第 $k+1$ 行除以 $\alpha$。若最后主元上方第 $i$ 行的项为 $c_i$，就依次作 $R_i\leftarrow R_i-c_iR_{k+1}$，其中 $1\leq i\leq k$。由于 $\alpha\ne0$，且源行与目标行不同，这些都是合法初等行变换。第 $k+1$ 行在第 $d_{k+1}$ 列之前全为零，所以加上该行的倍数不会改变已化简的左分块，也不会制造更靠左的首个非零项。更下方的零行同样不变。

完成证明。 原来的每个主元列仍只有一个值为 $1$ 的非零项，最后的主元列现在也如此。所有首个非零项的位置不变，因此所得矩阵是 RREF，并保留原来的 $k+1$ 个主元列。整个过程只使用非零行，故加强命题的全部要求都传到了下一步。再结合 REF 存在性，就得到 RREF 存在性；唯一性仍须另行证明。

例题 2.5.7

（在不移动主元列的情况下清理 REF）

从以下行阶梯形开始：

$$B= \begin{bmatrix} 2 & 1 & 4 & 5\\ 0 & 0 & -3 & 6\\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

它的主元列是第 $1$ 列与第 $3$ 列。要向 RREF 清理，先把第二个主元化成 $1$：

$$R_2\leftarrow -\frac{1}{3}R_2,\qquad \begin{bmatrix} 2 & 1 & 4 & 5\\ 0 & 0 & 1 & -2\\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

然后清掉第二个主元上方的项：

$$R_1\leftarrow R_1-4R_2,\qquad \begin{bmatrix} 2 & 1 & 0 & 13\\ 0 & 0 & 1 & -2\\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

最后把第一个主元化成 $1$：

$$R_1\leftarrow \frac{1}{2}R_1,\qquad \begin{bmatrix} 1 & \frac12 & 0 & \frac{13}{2}\\ 0 & 0 & 1 & -2\\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

第 $2$ 列与第 $4$ 列的数值改变了，但主元列没有改变：它们仍是第 $1$ 列与第 $3$ 列。这就是 REF 到 RREF 证明中“主元列保持”的具体版本。

由 REF 清理到 RREF 时主元列保持不变

上述证明其实给出一个很有用的额外结论。

定理 2.5.8

（REF 到 RREF 保持主元列）

设 $A$ 是秩为 $r$ 的行阶梯形，主元列为 $d_1,\ldots,d_r$。则 $A$ 与某个最简行阶梯形行等价，而该最简行阶梯形的主元列仍是 $d_1,\ldots,d_r$。

因此，一旦矩阵已经在 REF 中，主元列已经可读出。继续由 REF 化成 RREF 只是清理主元列，不会把主元移到新列。

下面的图解逐步整理这个归纳证明：先放置一个主元，再用归纳处理较小的下方分块，而由 REF 清理到 RREF 时会保持阶梯中已可见的主元列。

例题 2.5.9

（REF 已经告诉你主元列）

考虑

$$\begin{bmatrix} 2 & 4 & 1 & 7\\ 0 & 0 & 3 & 5\\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

这是 REF。主元列是第 $1$ 列与第 $3$ 列。若要继续到 RREF，需要把前两条非零行缩放，并清掉第二个主元上方的项。自由列中的数值可能改变，但主元列仍然是第 $1$ 列与第 $3$ 列。

存在性与化简路径的无关性

上面的证明保证每个矩阵都能到达 REF，再到达 RREF；按证明中的方式清理时，主元列位置保持不变。对一致的增广系统，REF 已能辨认主变量与自由变量，RREF 则让对应公式可以直接读出。整个过程中的行等价保证解集不变。

两条完成的化简路径是否必定给出同一个 RREF，是另一个问题，需要独立的 唯一性定理。存在性提供可到达的形式，唯一性则保证最简形式与所选操作无关，并支持后面对秩的定义。这里的归纳只证明存在性及清理时的主元列保持，没有预先使用路径无关性。

常见错误

常见错误

（把归纳证明当成计算技巧）

证明不是要求每次化简矩阵都写分块矩阵。归纳证明是在解释为什么算法必定能在有限步内到达所需形式。

常见错误

（混淆存在性与唯一性）

RREF 的存在性说某个最简行阶梯形可被到达。单靠存在性本身，还未证明不同化简路径必定得到同一个 RREF。

常见错误

（以为 RREF 会改变 REF 的主元列）

由 REF 清理到 RREF 会保持主元列。它会缩放主元行、清掉主元上方项，但不会把首项移到其他列。

快速检查

快速检查

（为什么 REF 证明要对行数作归纳？）

想想第一个主元列放好并清掉下方项之后，还剩下什么。

解答 · 答案

第一个主元列放好并清掉下方项之后，未处理的部分是一个较小矩阵。因此正好适合用行数归纳处理。

快速检查

（矩阵已在 REF 后，清理到 RREF 时主元列会移动吗？）

回想由 REF 到 RREF 的引理所附带的额外结论。

解答 · 答案

不会。由 REF 到 RREF 的清理保持主元列不变。它会缩放主元行并清掉主元上方项，但主元位置仍在同一批列中。

练习

练习 1

说明以下矩阵为什么已经是 REF，并指出其主元列：

$$\begin{bmatrix} 0 & 2 & 1 & 4\\ 0 & 0 & 5 & 6\\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

解答 · 练习 1 导引解答

零行在最底部。第一条非零行的首项在第 $2$ 列，第二条非零行的首项在第 $3$ 列，并且严格在右方。因此矩阵是 REF。其主元列是第 $2$ 列与第 $3$ 列。

练习 2

把练习 1 的矩阵继续化为 RREF。按次序写出行变换，再检查主元列是否改变。

解答 · 练习 2 导引解答

先做 $R_2\leftarrow \frac15R_2$，再做 $R_1\leftarrow R_1-R_2$ 清掉第二个主元上方的元素，最后做 $R_1\leftarrow \frac12R_1$。得到

$$\begin{bmatrix} 0 & 1 & 0 & \frac75\\ 0 & 0 & 1 & \frac65\\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

主元列仍是第 $2$ 列与第 $3$ 列。计算说明：标准化和向上清除会改变元素，却不会移动主元位置。

相关笔记

本笔记应在 2.3 高斯消元与最简行阶梯形 之后阅读，然后再把行化简大量用于张成、线性无关、秩与逆矩阵计算。