基本変形と掃き出し法（ガウスの消去法）

連立一次方程式を解くとき、未知数を順番に消去していく方法がある。この操作を行列に対して体系的に行う手法が掃き出し法（ガウスの消去法）であり、行列の基本変形がその基礎となる。

行列の基本変形

行列に対して行う操作のうち、以下の3種類を行基本変形と呼ぶ。

ある行を

c

倍する（

c \neq = 0

）

2つの行を入れ替える

ある行に別の行の

c

倍を加える

これらの操作はいずれも逆操作が存在する。たとえば「第 $i$ 行を $c$ 倍する」の逆操作は「第 $i$ 行を $1/ c$ 倍する」である。列に対しても同様の操作を定義でき、それを列基本変形と呼ぶ。

基本変形の重要な性質は、連立方程式の解を変えないことである。係数行列と拡大係数行列に基本変形を施しても、もとの方程式と同値な方程式が得られる。

掃き出し法では、拡大係数行列に行基本変形を繰り返して、行階段形または被約行階段形に変形する。

3元連立方程式の拡大係数行列を考える。

$123215 1 - 1 2 ∣ ∣ ∣ 419$

まず第1列の対角成分より下を 0 にする。第2行から第1行の2倍を引き、第3行から第1行の3倍を引く。

$100 2 - 3 - 1 1 - 3 - 1 ∣ ∣ ∣ 4 - 7 - 3$

次に第2列について同様の操作を行い、最終的に上三角形または対角形に近づける。被約行階段形まで変形すれば、解を直接読み取れる。

行階段形とは、各行の最初の非零成分（ピボット）が、上の行のピボットより右にある形である。さらに、各ピボットが 1 で、ピボットの上下がすべて 0 である形を被約行階段形（行簡約階段形）と呼ぶ。

被約行階段形の例を示す。

$100010001 ∣ ∣ ∣ 2 - 1 3$

この形になれば、 $x_{1} = 2$ , $x_{2} = - 1$ , $x_{3} = 3$ と解が直ちに得られる。

掃き出し法は連立方程式を解くだけでなく、逆行列の計算にも使える。 $n$ 次正方行列 $A$ の逆行列を求めるには、 $A$ と単位行列 $I$ を並べた行列 $(A ∣ I)$ に基本変形を施し、左側を $I$ に変形する。このとき右側に現れる行列が $A^{- 1}$ である。

また、行階段形に変形する過程でピボットの個数を数えれば、それが行列のランクとなる。掃き出し法は線形代数における基本的かつ実用的なアルゴリズムである。