2.5 行阶梯形的存在性

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

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

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

要证明什么

定理

REF 的存在性

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

定理

RREF 的存在性

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

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

证明属于可选内容，但它有价值，因为它展示行化简不是单纯食谱，而是一个有限 而有结构的论证。

对行数作归纳

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

定义

归纳命题

令 $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$ 列已经是最后一列，就没有右下方分块需要处理： 其余各行此时全为零，直接完成这一步，不必对不存在的列再使用归纳假设。

定理

REF 证明的结论

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

这个证明的重点不是背诵分块记号，而是看见递归结构：先放置一个主元，清掉其 下方项，再把剩下的小矩阵交给同一个定理处理。

例题

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

考虑

$$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

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

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

定理

由 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 存在性；唯一性仍须另行证明。

例题

在不移动主元列的情况下清理 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 时主元列保持不变

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

定理

REF 到 RREF 保持主元列

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

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

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

把可选 appendix 证明整理成 proof-as-algorithm 图：找最左主元、清下方、对较小分块递归，最后把 REF 清成 RREF 并保持主元列。

1. 目标保证

   每个矩阵都可到达行等价的 REF，然后到达行等价的 RREF。行等价是整个证明中的不变量。

2. 第一个主元

   若矩阵不是零矩阵，先找最左非零列，并把该列最上方的非零项移到第一行。

3. 较小分块

   用第一行清掉主元下方项。剩下的分块 V 行数较少，所以可在那里使用归纳假设。

4. 提升归纳步骤

   把 V 化成 V# 的行变换提升回整个矩阵时，只作用于下方行，所以第一个主元保持固定。

5. 由 REF 到 RREF

   对秩为 r 的 REF，秩归纳先处理较早主元列，再把最后主元化成 1 并清掉其上方项。

6. 主元列保持

   清理会改变数值，但不改变主元列位置。这是有用的保持性结论；RREF 唯一性是另一个更强定理。

存在性证明是构造性的：先放一个主元，再用归纳化简较小分块，最后把 REF 清理成 RREF 而不移动主元列。它证明目标可到达，并不是证明 RREF 唯一。

例题

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。

另有一个更强的重要定理会在秩被视为良定不变量时使用：一个矩阵的 RREF 是唯 一的。唯一性比存在性更强。存在性说目标可以到达；唯一性说所有合法化简路径 都会到达同一个最简目标。

普通计算时，主要记住以下后果：

1. 消元总能整理成 REF；
2. REF 总能再清理成 RREF；
3. 在 REF 中读到的主元列，会与对应 RREF 中的主元列相同；
4. 行等价会保留增广方程组的解集。

这个定理之后怎样使用

存在性定理本身很低调，但它支撑了后面很多计算。解方程组时，我们通常不会每 次都重新证明行化简会到达可读的形式，而是直接化简增广矩阵，然后从结果读出 主元变量、自由变量与相容性。本节补上的保证是：行变换总可以被安排到某个 REF，而这个 REF 又总可以继续清理成 RREF。

还要分清两种信息。REF 已经足以指出主元列，也足以判断哪些变量是基本变量、 哪些是自由变量。RREF 则更适合写最终公式，因为每个主元列都已标准化并清理 干净。证明说明这两种用途并不冲突：REF 到 RREF 的清理会改善主元列的形状， 但不会改变主元列位置。

因此，后面笔记在计算与理论之间切换时，不是在依赖某个幸运例子。例如，用主 元列讨论秩时，存在性保证阶梯形可到达，而主元列保持性保证在 REF 中读出的 列仍是清理到 RREF 时的相关列。之后的唯一性定理会再说明最后 RREF 与行变换 路径无关；本节刻意只先处理存在性与主元列保持。

一个实用记法是：存在性是在开始计算前保证方法有目标；唯一性则是在之后保证 最后的最简答案与化简路径无关。当你还停在 REF 阶段时，可以信任主元形状， 但不要把整个矩阵当成已经到达最终标准形式。 这个区分能让计算程序有理据，同时不夸大可选证明真正建立了什么。

常见错误

常见错误

把归纳证明当成计算技巧

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

常见错误

混淆存在性与唯一性

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 高斯消元与最简行阶梯形 之后阅读，然后再把行化简大量用于张成、线性无关、秩与逆矩阵计算。