行列の簡約化

• 与えられた行列に対し，第 i 行以降に 0 でない成分をもつ列のうちもっとも左にあるものが第 j 列だとする．
• 必要なら第 i 行とそれより下の行を入れ替えて，( i , j ) 成分が 0 でないようにできる．
• 第 i 行をスカラー倍して，( i , j ) 成分を 1 にできる．
• 第 i 行のスカラー倍を他の行に加えて，第 j 列を e _i にできる．
• 以上の手続きにおいて，第 j 列より左は変わらない．

定理 任意の行列は，次の操作

1. 2つの行を入れ替える
2. ある行を何倍か（≠ 0 倍）する
3. ある行に他の行の何倍かを加える

を繰り返すことにより，次の条件をみたす行列に変形される．

• 第 i 行以降に 0 でない成分をもつ列のうちもっとも左にあるものは e _i に一致する