高斯-喬登消去法（Gauss-Jordan Elimination）

假設你有五個方程含有五個未知數。你可以試著猜，也可以應用一個系統化的程序，保證要麼找到唯一解，要麼描述所有無限多個解，要麼告訴你無解。**高斯-喬登消去法（Gauss-Jordan elimination）**就是這個程序，它對任意數量的方程和未知數都適用。

基本列運算

關鍵的洞察是，對矩陣的列進行某些操作不會改變對應線性方程組的解集。這三種**基本列運算（elementary row operations）**是：

列交換（row swap）：交換兩列，記作 $R_i \leftrightarrow R_j$ 。
列縮放（row scaling）：以非零純量 $c \ne 0$ 乘以一列的每個元素，記作 $R_i \leftarrow c \cdot R_i$ 。
列置換（row replacement）：將一列的純量倍加到另一列，記作 $R_i \leftarrow R_i + c \cdot R_j$ 。

每種運算都是可逆的（其逆運算是同類型的另一個基本列運算），所以應用任意序列的這些運算都會產生一個等價的方程組——解集完全相同。

列梯形式

應用一系列基本列運算後，你的目標是達到一種特定的形狀。矩陣處於列梯形式（row echelon form，REF），如果：

所有零列（全為零的列）在底部。
在每個非零列中，第一個非零元素——稱為主元（pivot）（或前導元素）——嚴格位於上方列的主元的右側。

沿從左上到右下追蹤主元，矩陣呈現階梯狀形狀。

簡化列梯形式

矩陣處於簡化列梯形式（reduced row echelon form，RREF），如果它滿足所有 REF 條件，並且額外地：

每個主元恰好等於 $1$ 。
主元所在行（column）中的所有其他元素均為 $0$ （不只是主元下方的元素，上方的也是）。

RREF 是「最簡潔」的形式：你可以直接從中讀出線性方程組的解，無需進一步計算。

一個基本定理指出：每個矩陣有唯一的 RREF。無論你選擇哪個列運算序列（只要遵循算法），你總會到達相同的簡化列梯形式。

消去算法

算法分兩個掃描進行。

前向掃描（消去每個主元下方的元素）：

找到當前未處理列中任意位置有非零元素的最左側行（column）。
若需要，交換列使非零元素位於該行的頂部（在未處理的列中）。
縮放當前列使其前導元素變為 $1$ 。
將這一列的適當倍數加到它下方的每一列，使主元下方的所有元素等於 $0$ 。
移到下一列並從步驟 1 重複。

後向掃描（消去每個主元上方的元素）： 6. 從最底部的主元向上，將每個主元列的倍數加到它上方的每一列，使主元上方的所有元素等於 $0$ 。

兩個掃描後，每個主元為 $1$ 且每個主元行中的所有其他元素為 $0$ ——你已到達 RREF。

一個計算例子

解方程組：

\begin{cases} x_1 + 2x_2 - x_3 = 1 \\ 2x_1 + 3x_2 + x_3 = 4 \\ -x_1 + x_2 + 2x_3 = 3 \end{cases}

寫出增廣矩陣 $[A \mid b]$ 並進行化簡：

\begin{pmatrix} 1 & 2 & -1 & 1 \\ 2 & 3 & 1 & 4 \\ -1 & 1 & 2 & 3 \end{pmatrix}

$R_2 \leftarrow R_2 - 2R_1$ ，然後 $R_3 \leftarrow R_3 + R_1$ ：

\begin{pmatrix} 1 & 2 & -1 & 1 \\ 0 & -1 & 3 & 2 \\ 0 & 3 & 1 & 4 \end{pmatrix}

$R_2 \leftarrow -1 \cdot R_2$ （縮放使主元為 $1$ ）：

\begin{pmatrix} 1 & 2 & -1 & 1 \\ 0 & 1 & -3 & -2 \\ 0 & 3 & 1 & 4 \end{pmatrix}

$R_3 \leftarrow R_3 - 3R_2$ ：

\begin{pmatrix} 1 & 2 & -1 & 1 \\ 0 & 1 & -3 & -2 \\ 0 & 0 & 10 & 10 \end{pmatrix}

$R_3 \leftarrow \tfrac{1}{10} R_3$ ：

\begin{pmatrix} 1 & 2 & -1 & 1 \\ 0 & 1 & -3 & -2 \\ 0 & 0 & 1 & 1 \end{pmatrix}

現在進行後向掃描。 $R_2 \leftarrow R_2 + 3R_3$ ，然後 $R_1 \leftarrow R_1 + R_3$ ：

\begin{pmatrix} 1 & 2 & 0 & 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix}

$R_1 \leftarrow R_1 - 2R_2$ ：

\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix}

這是 RREF。讀出結果： $x_1 = 0$ ， $x_2 = 1$ ， $x_3 = 1$ 。方程組有唯一解。

樞軸行與自由變數

在矩陣 $A$ 的 RREF 中，包含主元的行（column）稱為樞軸行（pivot column）； $A$ 的所有其他行稱為自由行（free column）。對應自由行的變數稱為自由變數（free variables）——它們可以取 $F$ 中的任意值，每個選擇都給出一個有效的解。對應樞軸行的變數則由回代確定。

當沒有自由變數時，解（若存在）是唯一的。當至少有一個自由變數時，有無限多個解。這種分類在線性方程組中進一步探討。

摘要

基本列運算（交換、縮放、置換）保持線性方程組的解集不變。
**列梯形式（REF）**有一個階梯狀的主元；**簡化列梯形式（RREF）**另外將每個主元規範化為 $1$ 並清除主元行中的所有其他元素。
每個矩陣有唯一的 RREF，無論使用什麼列運算序列。
算法由前向掃描（消去主元下方的元素）和後向掃描（消去主元上方的元素）組成。
樞軸行對應確定的變數；自由行對應參數化解集的自由變數。