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 高斯消元與最簡行階梯形 之後閱讀，然後再把行化簡大量用於張成、線性無關、秩與逆矩陣計算。