ガウスの消去法
しかし一般的には、このような仮定の下で作業を行っても次の形の行簡約階段形にしか変形できない。(最も右の列の r + 2 番目の成分以下はすべて '0')
[ 1 0 ⋯ 0 − d 11 ⋯ − d 1 s c 1 0 1 ⋯ 0 − d 21 ⋯ − d 2 s c 2 ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ 0 0 ⋯ 1 − d r 1 ⋯ − d r s c r 0 0 ⋯ 0 0 ⋯ 0 c r + 1 ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ 0 0 ⋯ 0 0 ⋯ 0 0 ] {\displaystyle \left[{\begin{array}{ccccccc|c}1&0&\cdots &0&-d_{11}&\cdots &-d_{1s}&c_{1}\\0&1&\cdots &0&-d_{21}&\cdots &-d_{2s}&c_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots &&\vdots &\vdots \\0&0&\cdots &1&-d_{r1}&\cdots &-d_{rs}&c_{r}\\0&0&\cdots &0&0&\cdots &0&c_{r+1}\\\vdots &\vdots &&\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&\cdots &0&0&\cdots &0&0\end{array}}\right]}
x 1 + 2 x 2 + x 3 + x 4 = 4 x 2 − 1 2 x 3 − 1 2 x 4 = 1 2 − 3 2 x 3 + 3 2 x 4 = − 3 2 0 = 0 {\displaystyle {\begin{aligned}&x_{1}&+&2x_{2}&+&x_{3}&+&x_{4}&&=4\\&&&x_{2}&-&{\frac {1}{2}}x_{3}&-&{\frac {1}{2}}x_{4}&&={\frac {1}{2}}\\&&&&-&{\frac {3}{2}}x_{3}&+&{\frac {3}{2}}x_{4}&&=-{\frac {3}{2}}\\&&&&&&&0&&=0\end{aligned}}}
次に後退代入をする。 3 番目の方程式を − 2 3 {\displaystyle -{\frac {2}{3}}} 倍する x 1 + 2 x 2 + x 3 + x 4 = 4 x 2 − 1 2 x 3 − 1 2 x 4 = 1 2 x 3 − x 4 = 1 0 = 0 {\displaystyle {\begin{aligned}&x_{1}&+&2x_{2}&+&x_{3}&+&x_{4}&=4\\&&&x_{2}&-&{\frac {1}{2}}x_{3}&-&{\frac {1}{2}}x_{4}&={\frac {1}{2}}\\&&&&&x_{3}&-&x_{4}&=1\\&&&&&&&0&=0\end{aligned}}} x 3 = 1 + x 4 {\displaystyle x_{3}=1+x_{4}} を 2 番目の方程式に代入する。
x 1 + 2 x 2 + x 3 + x 4 = 4 x 2 − x 4 = 1 x 3 − x 4 = 1 0 = 0 {\displaystyle {\begin{aligned}&x_{1}&+&2x_{2}&+&x_{3}&+&x_{4}&=4\\&&&x_{2}&&&-&x_{4}&=1\\&&&&&x_{3}&-&x_{4}&=1\\&&&&&&&0&=0\end{aligned}}} x 3 = 1 + x 4 {\displaystyle x_{3}=1+x_{4}} と x 2 = 1 + x 4 {\displaystyle x_{2}=1+x_{4}} を 1 番目の方程式に代入する。 x 1 + 4 x 4 = 1 x 2 − x 4 = 1 x 3 − x 4 = 1 0 = 0 {\displaystyle {\begin{aligned}x_{1}+4x_{4}&=1\\x_{2}-x_{4}&=1\\x_{3}-x_{4}&=1\\0&=0\end{aligned}}}
そこで、 x 4 = c {\displaystyle x_{4}=c} ("c" は任意定数)とおくと、
x 1 = − 4 c + 1 x 2 = c + 1 x 3 = c + 1 x 4 = c {\displaystyle {\begin{aligned}x_{1}&=-4c+1\\x_{2}&=c+1\\x_{3}&=c+1\\x_{4}&=c\end{aligned}}}
これで解が全て求まった。
一般的なアルゴリズムについては、たとえば(コルテ & フィーゲン 2009, p. 96)を見よ。
この方程式が x 1 = c 1 + d 11 λ 1 + ⋯ + d 1 s λ s , x 2 = c 2 + d 21 λ 1 + ⋯ + d 2 s λ s , ⋯ , x r = c r + d r 1 λ 1 + ⋯ + d r s λ s , x r + 1 = λ 1 , ... , x n = λ s {\displaystyle x_{1}=c_{1}+d_{11}\lambda _{1}+\cdots +d_{1s}\lambda _{s},x_{2}=c_{2}+d_{21}\lambda _{1}+\cdots +d_{2s}\lambda _{s},\cdots ,x_{r}=c_{r}+d_{r1}\lambda _{1}+\cdots +d_{rs}\lambda _{s},x_{r+1}=\lambda _{1},\ldots ,x_{n}=\lambda _{s}} ( n = r + s {\displaystyle n=r{+}s} かつ λ 1 , . . . , λ s {\displaystyle \lambda _{1},...,\lambda _{s}} は任意の定数)という解を持つとすると、これらの式は次の連立一次方程式を略記したものであると見なせる。ただし、下段に並んでいる、左辺の全ての係数が 0 である式は m − r {\displaystyle m{-}r} 本ある。 同様に右側にある行列がその拡大係数行列である。
始めの拡大係数行列から上の拡大係数行列の形に変形する為には、対角成分に注目して行基本変形を行って行簡約階段形に変形する。ただし簡単のため、変数の番号を付け替えることなしに主成分がすべて対角線にあるものと仮定する。