この記事には参考文献や外部リンクの一覧が含まれていますが、
脚注 による参照が不十分であるため、情報源が依然不明確です。
適切な位置に脚注を追加して、記事の信頼性向上にご協力ください。（2022年7月 ）
ガウスの消去法 （ガウスのしょうきょほう、英 : Gaussian elimination ）あるいは掃き出し法 （はきだしほう、英 : row reduction ）とは、連立一次方程式 を解くための多項式時間 アルゴリズム であり、通常は問題となる連立一次方程式の係数からなる拡大係数行列 に対して行われる一連の変形操作を意味する。
同様のアルゴリズムは歴史的には前漢 に九章算術 で初めて記述された。連立一次方程式の解法以外にも
などに使われる。このアルゴリズムは、大きな方程式系を系統的な方法で小さな系へ分解する方法を与えるものと理解することができ[4] 前進消去 (forward elimination) と後退代入 (backward substitution) という2つのステップから成る。
行列に対して掃き出し法を行う為には、行に関する基本変形 を行列に可能な限り繰り返し行って行列の左下部分の成分を全て 0 にする。行に関する基本変形には、
二つの行を入れ替えるもの
ある行を0でない定数倍するもの
ある行に他のある行の定数倍を加えるもの の3種類の操作があり、必ず行列を上三角型に変形することができる。実際には、ゼロでない成分を持つ行が、ゼロしか成分に持たない行よりも上に位置し、主成分（行内の 0 でない成分のうち最も左にあるもの）が、その行の上にある行の主成分よりも、真に右側に位置する行階段形 に変形される。
特に全ての主成分が 1 になり、主成分を含む列にある主成分以外の成分が 0 であるとき、この行列は行簡約階段形 であると呼ばれる。この最終形は一意的であり、どのような行基本変形が行われたかには依存しない。例えば、次の様な行基本変形の繰り返し（各ステップで複数の基本変形を行っている）で、3番目と4番目は共に行階段形であるが、最後の4番目が一意に定まる行簡約階段形である。
[
1
3
1
9
1
1
−
1
1
3
11
5
35
]
→
[
1
3
1
9
0
−
2
−
2
−
8
0
2
2
8
]
→
[
1
3
1
9
0
−
2
−
2
−
8
0
0
0
0
]
→
[
1
0
−
2
−
3
0
1
1
4
0
0
0
0
]
{\displaystyle \left[{\begin{array}{rrr|r}1&3&1&9\\1&1&-1&1\\3&11&5&35\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&3&1&9\\0&-2&-2&-8\\0&2&2&8\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&0&-2&-3\\0&1&1&4\\0&0&0&0\end{array}}\right]}
行基本変形を用いて行列を行階段形に変形することをガウス・ジョルダンの消去法 （ガウス・ジョルダンのしょうきょほう、英 : Gauss–Jordan elimination ）という。ガウスの消去法という用語を上三角形または（簡約とは限らない）行階段形へ変換する手法を指すこともある。連立一次方程式の解を求める際に行基本変形を完全に簡約化する前に止めてしまう方が、計算上の理由から良いとされる場合もある。
基本的な考え方 次の n 元m 連立一次方程式を考察する。右側にある行列がその拡大係数行列である。
a
11
x
1
+
a
12
x
2
+
⋯
+
a
1
n
x
n
=
b
1
a
21
x
1
+
a
22
x
2
+
⋯
+
a
2
n
x
n
=
b
2
⋮
a
m
1
x
1
+
a
m
2
x
2
+
⋯
+
a
m
n
x
n
=
b
m
[
a
11
a
12
⋯
a
1
n
b
1
a
21
a
22
⋯
a
2
n
b
2
⋮
⋮
⋱
⋮
⋮
a
m
1
a
m
2
⋯
a
m
n
b
m
]
{\displaystyle {\begin{aligned}&a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}=b_{1}\\&a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}=b_{2}\\&\qquad \vdots \\&a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}=b_{m}\end{aligned}}\qquad \left[{\begin{array}{cccc|c}a_{11}&a_{12}&\cdots &a_{1n}&b_{1}\\a_{21}&a_{22}&\cdots &a_{2n}&b_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}&b_{m}\end{array}}\right]}
この方程式が
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}
1
x
1
+
0
x
2
+
⋯
+
0
x
r
−
d
11
x
r
+
1
−
⋯
−
d
1
s
x
n
=
c
1
0
x
1
+
1
x
2
+
⋯
+
0
x
r
−
d
21
x
r
+
1
−
⋯
−
d
2
s
x
n
=
c
2
⋮
0
x
1
+
0
x
2
+
⋯
+
1
x
r
−
d
r
1
x
r
+
1
−
⋯
−
d
r
s
x
n
=
c
r
0
x
1
+
0
x
2
+
⋯
+
0
x
r
+
0
x
r
+
1
+
⋯
+
0
x
n
=
0
⋮
0
x
1
+
0
x
2
+
⋯
+
0
x
r
+
0
x
r
+
1
+
⋯
+
0
x
n
=
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
0
⋮
⋮
⋮
⋮
⋱
⋮
⋮
0
0
⋯
0
0
⋯
0
0
]
{\displaystyle {\begin{aligned}&1x_{1}+0x_{2}+\cdots +0x_{r}-d_{11}x_{r+1}-\cdots -d_{1s}x_{n}=c_{1}\\&0x_{1}+1x_{2}+\cdots +0x_{r}-d_{21}x_{r+1}-\cdots -d_{2s}x_{n}=c_{2}\\&\qquad \vdots \\&0x_{1}+0x_{2}+\cdots +1x_{r}-d_{r1}x_{r+1}-\cdots -d_{rs}x_{n}=c_{r}\\&0x_{1}+0x_{2}+\cdots +0x_{r}+0x_{r+1}+\cdots +0x_{n}=0\\&\qquad \vdots \\&0x_{1}+0x_{2}+\cdots +0x_{r}+0x_{r+1}+\cdots +0x_{n}=0\end{aligned}}\qquad \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&0\\\vdots &\vdots &&\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&\cdots &0&0&\cdots &0&0\end{array}}\right]}
始めの拡大係数行列から上の拡大係数行列の形に変形する為には、対角成分に注目して行基本変形を行って行簡約階段形に変形する。ただし簡単のため、変数の番号を付け替えることなしに主成分がすべて対角線にあるものと仮定する。しかし一般的には、このような仮定の下で作業を行っても次の形の行簡約階段形にしか変形できない。（最も右の列の r + 2
[
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]}
この時点で、与えられた連立一次方程式が解を持つ必要条件が
c
r
+
1
=
0
{\displaystyle c_{r+1}=0}
c
r
+
1
=
0
{\displaystyle c_{r+1}=0}
k 個定まった時点で残り k + 1 個の未知数を含む式が解けるため、
x
1
{\displaystyle x_{1}}
x
r
{\displaystyle x_{r}}
[
1
m
12
⋯
m
1
r
−
d
11
′
⋯
−
d
1
s
′
c
1
′
0
1
⋯
m
2
r
−
d
21
′
⋯
−
d
2
s
′
c
2
′
⋮
⋮
⋱
⋮
⋮
⋮
⋮
0
0
⋯
1
−
d
r
1
′
⋯
−
d
r
s
′
c
r
′
0
0
⋯
0
0
⋯
0
0
⋮
⋮
⋮
⋮
⋱
⋮
⋮
0
0
⋯
0
0
⋯
0
0
]
1
x
1
+
m
12
x
2
+
⋯
+
m
1
r
x
r
−
d
11
′
x
r
+
1
−
⋯
−
d
1
s
′
x
n
=
c
1
′
0
x
1
+
1
x
2
+
⋯
+
m
2
r
x
r
−
d
21
′
x
r
+
1
−
⋯
−
d
2
s
′
x
n
=
c
2
′
⋮
0
x
1
+
0
x
2
+
⋯
+
1
x
r
−
d
r
1
′
x
r
+
1
−
⋯
−
d
r
s
′
x
n
=
c
r
′
0
x
1
+
0
x
2
+
⋯
+
0
x
r
+
0
x
r
+
1
+
⋯
+
0
x
n
=
0
⋮
0
x
1
+
0
x
2
+
⋯
+
0
x
r
+
0
x
r
+
1
+
⋯
+
0
x
n
=
0
{\displaystyle \left[{\begin{array}{ccccccc|c}1&m_{12}&\cdots &m_{1r}&-d'_{11}&\cdots &-d'_{1s}&c'_{1}\\0&1&\cdots &m_{2r}&-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&0\\\vdots &\vdots &&\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&\cdots &0&0&\cdots &0&0\end{array}}\right]\qquad {\begin{aligned}&1x_{1}+m_{12}x_{2}+\cdots +m_{1r}x_{r}-d'_{11}x_{r+1}-\cdots -d'_{1s}x_{n}=c'_{1}\\&0x_{1}+1x_{2}+\cdots +m_{2r}x_{r}-d'_{21}x_{r+1}-\cdots -d'_{2s}x_{n}=c'_{2}\\&\qquad \vdots \\&0x_{1}+0x_{2}+\cdots +1x_{r}-d'_{r1}x_{r+1}-\cdots -d'_{rs}x_{n}=c'_{r}\\&0x_{1}+0x_{2}+\cdots +0x_{r}+0x_{r+1}+\cdots +0x_{n}=0\\&\qquad \vdots \\&0x_{1}+0x_{2}+\cdots +0x_{r}+0x_{r+1}+\cdots +0x_{n}=0\end{aligned}}}
従って、任意定数
λ
1
,
…
,
λ
s
{\displaystyle \lambda _{1},\ldots ,\lambda _{s}}
>r+1 s 個の変数を
x
r
+
1
=
λ
1
,
x
r
+
2
=
λ
2
,
.
.
.
,
x
n
=
λ
s
{\displaystyle x_{r+1}=\lambda _{1},x_{r+2}=\lambda _{2},...,x_{n}=\lambda _{s}}
例 次の連立一次方程式の解を拡大係数行列を用いずにガウスの消去法のアルゴリズムで求めてみる。
式の本数が固定されていること、式の入れ替えもまた一つの操作であることに注意すべきである。
2
x
1
+
4
x
2
+
2
x
3
+
2
x
4
=
8
4
x
1
+
10
x
2
+
3
x
3
+
3
x
4
=
17
2
x
1
+
6
x
2
+
x
3
+
x
4
=
9
3
x
1
+
7
x
2
+
x
3
+
4
x
4
=
11
{\displaystyle {\begin{aligned}&2x_{1}&+&4x_{2}&+&2x_{3}&+&2x_{4}&&=8\\&4x_{1}&+&10x_{2}&+&3x_{3}&+&3x_{4}&&=17\\&2x_{1}&+&6x_{2}&+&x_{3}&+&x_{4}&&=9\\&3x_{1}&+&7x_{2}&+&x_{3}&+&4x_{4}&&=11\end{aligned}}}
まず前進消去 をする。
1 番目の方程式を 1 / 2
x
1
+
2
x
2
+
x
3
+
x
4
=
4
4
x
1
+
10
x
2
+
3
x
3
+
3
x
4
=
17
2
x
1
+
6
x
2
+
x
3
+
x
4
=
9
3
x
1
+
7
x
2
+
x
3
+
4
x
4
=
11
{\displaystyle {\begin{aligned}&x_{1}&+&2x_{2}&+&x_{3}&+&x_{4}&&=4\\&4x_{1}&+&10x_{2}&+&3x_{3}&+&3x_{4}&&=17\\&2x_{1}&+&6x_{2}&+&x_{3}&+&x_{4}&&=9\\&3x_{1}&+&7x_{2}&+&x_{3}&+&4x_{4}&&=11\end{aligned}}}
2 番目の方程式に 1 番目の方程式の −4 倍を足す。3 番目の方程式に 1 番目の方程式の −2 倍を足す。4 番目の方程式に 1 番目の方程式の −3 倍を足す。
x
1
+
2
x
2
+
x
3
+
x
4
=
4
2
x
2
−
x
3
−
x
4
=
1
2
x
2
−
x
3
−
x
4
=
1
x
2
−
2
x
3
+
x
4
=
−
1
{\displaystyle {\begin{aligned}&x_{1}&+&2x_{2}&+&x_{3}&+&x_{4}&&=4\\&&&2x_{2}&-&x_{3}&-&x_{4}&&=1\\&&&2x_{2}&-&x_{3}&-&x_{4}&&=1\\&&&x_{2}&-&2x_{3}&+&x_{4}&&=-1\end{aligned}}}
2 番目の方程式を 1/2 倍する。
x
1
+
2
x
2
+
x
3
+
x
4
=
4
x
2
−
1
2
x
3
−
1
2
x
4
=
1
2
2
x
2
−
x
3
−
x
4
=
1
x
2
−
2
x
3
+
x
4
=
−
1
{\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}}\\&&&2x_{2}&-&x_{3}&-&x_{4}&&=1\\&&&x_{2}&-&2x_{3}&+&x_{4}&&=-1\end{aligned}}}
3 番目の方程式に 2 番目の方程式の -2 倍を足す。4 番目の方程式に 2 番目の方程式の -1 倍を足す。
x
1
+
2
x
2
+
x
3
+
x
4
=
4
x
2
−
1
2
x
3
−
1
2
x
4
=
1
2
0
=
0
−
3
2
x
3
+
3
2
x
4
=
−
3
2
{\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}}\\&&&&&&&0&&=0\\&&&&-&{\frac {3}{2}}x_{3}&+&{\frac {3}{2}}x_{4}&&=-{\frac {3}{2}}\end{aligned}}}
3 番目の方程式と 4 番目の方程式を入れ替える。
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}}
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}}
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}
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)を見よ。
注意 対角成分 が 0 になる場合には、枢軸選択（ピボット選択）という式の交換を行う必要がある。
対角成分が 0 になる場合以外でも、対角成分が絶対値が最大の係数になるように枢軸選択を行ったほうが、解の丸め誤差 が少なくなる。ただし、これは行列要素の絶対値が同程度の大きさの場合のみ成り立ち、スケーリング（=前処理 として方程式に適当な正則対角行列を掛け等価な方程式へ変換すること）を行わずに枢軸選択を行うとむしろ精度が悪化する場合もあるため、注意が必要である
枢軸選択には部分選択法と完全選択法がある。絶対値が最大の係数を探索する範囲が、部分選択法は掃出し列（下方向）のみであるのに対し、完全選択法ではすべての項目（右および下方向）である。完全選択の方が計算精度は高いが計算速度およびアルゴリズムの複雑化の面で不利であるため、完全選択法の採用は現実には少ない。 疎行列 に対してガウスの消去法のステップを行うと疎性を損なう（フィルイン fill-in）。前進消去の段階において対角化 を目指して、後退代入を行わずに x を直接計算する方法はガウス・ジョルダンの消去法 （Gauss-Jordan elimination ）と呼ぶ。アルゴリズムは単純になるが、計算量 は多くなる（変数が多い場合、ほぼ 1.5 倍になる）。
計算量（乗算の回数）は、変数の個数を n とすると、ほぼ 1 / 3 n 3 になる。大部分は前進消去にかかっており、後退代入にはそれより少ない 1 / 2 n 2 程度である[4]
O
(
n
3
)
{\displaystyle O(n^{3})}
脚注
^ a b Joel H. Ferziger; Milovan Perić 著、小林敏雄、谷口伸行、坪倉誠 訳『コンピュータによる流体力学』シュプリンガー・フェアラーク東京、2003年、88頁。ISBN 4-431-70842-1 。
参考文献 関連項目 外部リンク 
![{\displaystyle \left[{\begin{array}{rrr|r}1&3&1&9\\1&1&-1&1\\3&11&5&35\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&3&1&9\\0&-2&-2&-8\\0&2&2&8\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{array}}\right]\to \left[{\begin{array}{rrr|r}1&0&-2&-3\\0&1&1&4\\0&0&0&0\end{array}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65d92f997de9f7ad787b95d08fcd25dca828dd93)
![{\displaystyle {\begin{aligned}&a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}=b_{1}\\&a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}=b_{2}\\&\qquad \vdots \\&a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}=b_{m}\end{aligned}}\qquad \left[{\begin{array}{cccc|c}a_{11}&a_{12}&\cdots &a_{1n}&b_{1}\\a_{21}&a_{22}&\cdots &a_{2n}&b_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}&b_{m}\end{array}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50f4e120b74634124b4cfa295dd62a93249a4530)
![{\displaystyle {\begin{aligned}&1x_{1}+0x_{2}+\cdots +0x_{r}-d_{11}x_{r+1}-\cdots -d_{1s}x_{n}=c_{1}\\&0x_{1}+1x_{2}+\cdots +0x_{r}-d_{21}x_{r+1}-\cdots -d_{2s}x_{n}=c_{2}\\&\qquad \vdots \\&0x_{1}+0x_{2}+\cdots +1x_{r}-d_{r1}x_{r+1}-\cdots -d_{rs}x_{n}=c_{r}\\&0x_{1}+0x_{2}+\cdots +0x_{r}+0x_{r+1}+\cdots +0x_{n}=0\\&\qquad \vdots \\&0x_{1}+0x_{2}+\cdots +0x_{r}+0x_{r+1}+\cdots +0x_{n}=0\end{aligned}}\qquad \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&0\\\vdots &\vdots &&\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&\cdots &0&0&\cdots &0&0\end{array}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9456d0a5ac4564370907734e4955ac9d595d5015)
![{\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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df049fa0c491834fd0bf9eaeefaf3b6014f7febb)
![{\displaystyle \left[{\begin{array}{ccccccc|c}1&m_{12}&\cdots &m_{1r}&-d'_{11}&\cdots &-d'_{1s}&c'_{1}\\0&1&\cdots &m_{2r}&-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&0\\\vdots &\vdots &&\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&\cdots &0&0&\cdots &0&0\end{array}}\right]\qquad {\begin{aligned}&1x_{1}+m_{12}x_{2}+\cdots +m_{1r}x_{r}-d'_{11}x_{r+1}-\cdots -d'_{1s}x_{n}=c'_{1}\\&0x_{1}+1x_{2}+\cdots +m_{2r}x_{r}-d'_{21}x_{r+1}-\cdots -d'_{2s}x_{n}=c'_{2}\\&\qquad \vdots \\&0x_{1}+0x_{2}+\cdots +1x_{r}-d'_{r1}x_{r+1}-\cdots -d'_{rs}x_{n}=c'_{r}\\&0x_{1}+0x_{2}+\cdots +0x_{r}+0x_{r+1}+\cdots +0x_{n}=0\\&\qquad \vdots \\&0x_{1}+0x_{2}+\cdots +0x_{r}+0x_{r+1}+\cdots +0x_{n}=0\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/390419815c963da5d6532b081541b45f64493440)
