行階段形 — ガウスの消去法の解説

行階段形（REF）

行列が行階段形であるとは：

1. すべてのゼロ行が一番下にある
2. 各行の最初の非ゼロエントリ（ピボット）が上の行のピボットより右にある
3. ピボットの下のすべてのエントリがゼロ

ガウスの消去法アルゴリズム

REFを達成するには、以下の基本行操作を実行します：

1. 2つの行を交換
2. 行に非ゼロスカラーを掛ける
3. ある行の倍数を別の行に加える

例

開始:  | 2  1  -1 |  3 |
       | 4  3   1 |  7 |
       | 2  1   3 |  5 |

R2 = R2 - 2*R1:
       | 2  1  -1 |  3 |
       | 0  1   3 |  1 |
       | 2  1   3 |  5 |

R3 = R3 - R1:
       | 2  1  -1 |  3 |
       | 0  1   3 |  1 |
       | 0  0   4 |  2 |

これでREFになりました。ランク（3）を読み取り、後退代入で解けます。

簡約行階段形（RREF）

RREFはさらに進みます：各ピボットが1で、各ピボットの上下のすべてのエントリがゼロ。RREFは与えられた行列に対して一意ですが、REFは一意ではありません。

計算量

ガウスの消去法はn x n行列に対して O(n^3) の時間で実行されるため、中程度のサイズの行列に対して実用的です。行列式の計算では余因子展開（余因子に対してO(n!)）よりも効率的です。