前面的笔记说明如何做高斯消元，以及如何读取化简后的结果。本节问一个更理论 化的问题：
为什么每个矩阵都可以期望有一个行阶梯形，甚至有一个最简行阶梯形？
这个问题很重要，因为行化简会在整个课程中反复出现：解方程组、找自由变量、 测试张成、测试线性无关、求逆、求秩、建立基，都要用到它。若行阶梯形只是一 堆例子，后面的理论便没有稳固基础。下面的定理说明：算法确实有保证能到达的 目标。
要证明什么
定理
REF 的存在性
对每个矩阵 ，都存在某个与 行等价的行阶梯形 。
定理
RREF 的存在性
对每个矩阵 ，都存在某个与 行等价的最简行阶梯形 C'。
第一个定理说高斯消元总能到达阶梯形；第二个定理说，到达阶梯形后，进一步清 理主元列总能到达最简形式。
证明属于可选内容，但它有价值，因为它展示行化简不是单纯食谱，而是一个有限 而有结构的论证。
对行数作归纳
REF 存在性的证明使用行数归纳。
定义
归纳命题
令 P(m) 表示以下命题：若 是一个有 m 行的矩阵，则 与某个
同样有 m 行的行阶梯形 行等价。
基本情况很直接。一行矩阵本身已经是行阶梯形：它要么是零行，要么唯一非零行 的第一个非零项就是首项。
归纳步骤中，假设 P(k) 成立，并令 是一个有 行的矩阵。
若 是零矩阵，没有事情要证。否则，找出 中最左边的非零列。在该列 中，找出最上方的非零项；如有需要，将该行交换到第一行。把新的第一个主元值 记为 。
接着，用第一行把同一列中 下方所有项清成零。矩阵便有分块形状
其中 是一个有 k 行的矩阵。
现在可对 使用归纳假设。它可被行化简成某个行阶梯形 V'。把相应行变换
作用在整个矩阵的下方 k 行，得到
这个矩阵是行阶梯形：第一个主元在第 j 列，其下方全为零；下方分块则由归
纳假设已具备阶梯结构。
定理
REF 证明的结论
由数学归纳法，每个正行数矩阵都与某个行阶梯形行等价。
这个证明的重点不是背诵分块记号，而是看见递归结构：先放置一个主元，清掉其 下方项，再把剩下的小矩阵交给同一个定理处理。
例题
在具体矩阵中看见较小分块
考虑
最左非零列是第 2 列。该列最上方项已经非零，所以可以把第一行中的
当作第一个主元。清掉其下方项，得到
第一个主元右下方剩下的较小分块是
这正是归纳证明的重点：整个矩阵不必一次处理完。第一个主元固定后，剩下的任 务就是把一个行数较少的矩阵整理成行阶梯形。在这个例子中，再做一步 ，便得到
这已经是 REF。例子很小，但它展示了普遍证明中同一个“问题变小”的结构。
由 REF 到 RREF
第二部分从一个已经是行阶梯形的矩阵出发，目标是证明它可以在保持行等价的情 况下变成最简行阶梯形。
此时归纳的参数是秩，也就是行阶梯形中的非零行数。
定理
由 REF 到 RREF 的引理
若 是秩为 r 的行阶梯形，则存在秩仍为 r、与 行等价的最简行阶梯
形 A'。
基本情况 立即成立：秩为 0 的行阶梯形是零矩阵，而零矩阵已经是 RREF。
归纳步骤中，假设秩 k 的情况已成立，并令 是秩 的行阶梯形。先
看最后一个主元列左边的所有列。这些列形成一个秩为 k 的较小行阶梯分块，
所以可用归纳假设把左方分块化成最简形式。
然后把最后一个主元化成 1，并清掉它上方的项。由于行阶梯形在相关位置已有
零，这些行变换不会破坏左方已处理好的主元列。
最后所得矩阵的每个主元列都只有一个非零项，而该项等于 1，所以它是 RREF。
例题
在不移动主元列的情况下清理 REF
从以下行阶梯形开始：
它的主元列是第 1 列与第 3 列。要向 RREF 清理，先把第二个主元化成
1：
然后清掉第二个主元上方的项：
最后把第一个主元化成 1：
第 2 列与第 4 列的数值改变了，但主元列没有改变：它们仍是第 1 列与
第 3 列。这就是 REF 到 RREF 证明中“主元列保持”的具体版本。
由 REF 清理到 RREF 时主元列保持不变
上述证明其实给出一个很有用的额外结论。
定理
REF 到 RREF 保持主元列
设 是秩为 r 的行阶梯形，主元列为 。则 与某个最简
行阶梯形行等价，而该最简行阶梯形的主元列仍是 。
因此，一旦矩阵已经在 REF 中，主元列已经可读出。继续由 REF 化成 RREF 只是 清理主元列，不会把主元移到新列。
下面的视频把这个可选证明整理成短的“证明即算法”地图：先放置一个主元，再 用归纳处理较小的下方分块，而由 REF 清理到 RREF 时会保持阶梯中已可见的主 元列。
图解说明
把可选 appendix 证明整理成 proof-as-algorithm 图：找最左主元、清下方、对较小分块递归，最后把 REF 清成 RREF 并保持主元列。
例题
REF 已经告诉你主元列
考虑
这是 REF。主元列是第 1 列与第 3 列。若要继续到 RREF，需要把前两条非
零行缩放，并清掉第二个主元上方的项。自由列中的数值可能改变，但主元列仍然
是第 1 列与第 3 列。
本节没有证明什么
本节证明的是存在性：每个矩阵至少可到达某个 REF，也至少可到达某个 RREF。
另有一个更强的重要定理会在秩被视为良定不变量时使用：一个矩阵的 RREF 是唯 一的。唯一性比存在性更强。存在性说目标可以到达；唯一性说所有合法化简路径 都会到达同一个最简目标。
普通计算时，主要记住以下后果：
- 消元总能整理成 REF；
- REF 总能再清理成 RREF；
- 在 REF 中读到的主元列，会与对应 RREF 中的主元列相同；
- 行等价会保留增广方程组的解集。
这个定理之后怎样使用
存在性定理本身很低调，但它支撑了后面很多计算。解方程组时，我们通常不会每 次都重新证明行化简会到达可读的形式，而是直接化简增广矩阵，然后从结果读出 主元变量、自由变量与相容性。本节补上的保证是：行变换总可以被安排到某个 REF，而这个 REF 又总可以继续清理成 RREF。
还要分清两种信息。REF 已经足以指出主元列，也足以判断哪些变量是基本变量、 哪些是自由变量。RREF 则更适合写最终公式，因为每个主元列都已标准化并清理 干净。证明说明这两种用途并不冲突：REF 到 RREF 的清理会改善主元列的形状， 但不会改变主元列位置。
因此，后面笔记在计算与理论之间切换时，不是在依赖某个幸运例子。例如，用主 元列讨论秩时，存在性保证阶梯形可到达，而主元列保持性保证在 REF 中读出的 列仍是清理到 RREF 时的相关列。之后的唯一性定理会再说明最后 RREF 与行变换 路径无关；本节刻意只先处理存在性与主元列保持。
一个实用记法是：存在性是在开始计算前保证方法有目标；唯一性则是在之后保证 最后的最简答案与化简路径无关。当你还停在 REF 阶段时，可以信任主元形状， 但不要把整个矩阵当成已经到达最终标准形式。 这个区分能让计算程序有理据，同时不夸大可选证明真正建立了什么。
常见错误
常见错误
把归纳证明当成计算技巧
证明不是要求每次化简矩阵都写分块矩阵。归纳证明是在解释为什么算法必定能在 有限步内到达所需形式。
常见错误
混淆存在性与唯一性
RREF 的存在性说某个最简行阶梯形可被到达。单靠存在性本身，还未证明不同化 简路径必定得到同一个 RREF。
常见错误
以为 RREF 会改变 REF 的主元列
由 REF 清理到 RREF 会保持主元列。它会缩放主元行、清掉主元上方项，但不会 把首项移到其他列。
快速检查
快速检查
为什么 REF 证明要对行数作归纳？
想想第一个主元列放好并清掉下方项之后，还剩下什么。
解答
答案
快速检查
矩阵已在 REF 后，清理到 RREF 时主元列会移动吗？
回想由 REF 到 RREF 的引理所附带的额外结论。
解答
答案
练习
练习 1
说明以下矩阵为什么已经是 REF，并指出其主元列：
解答
练习 1 导引解答
练习 2
假设某行阶梯形的主元列是第 1、4、5 列。它进一步化成 RREF 后，主元
列会是什么？
解答
练习 2 导引解答
相关笔记
本附录应在 2.3 高斯消元与最简行阶梯形 之后阅读，然后再把行化简大量用于张成、线性无关、秩与逆矩阵计算。