掃き出し法による連立一次方程式の解法
行列に対する次の操作は
行基本変形と呼ばれる：
-
ある行とある行を入れ替える
-
ある行をスカラー倍する(ただし $0$ 倍は不可)
-
ある行を他の行に加える
この行基本変形を利用して連立一次方程式を解く方法が
掃き出し法である．
連立一次方程式
$A\mathbf{x}=\mathbf{b}$
が与えられたとき，係数行列 $A$ に右辺のベクトル $\mathbf{b}$ を付け加えて得られる行列 $(\,A\,|\,\mathbf{b}\,)$ を
拡大係数行列というが，この拡大係数行列に行基本変形を施して
$(\,A\,|\,\mathbf{b}\,)\to\cdots\to(\,E\,|\,\mathbf{b}'\,)$
という形が得られれば，$\mathbf{x}=\mathbf{b}'$ がこの方程式の解ということになる．
行列の階数を求めるときは行基本変形と列基本変形どちらを行ってもよいが，
掃き出し法により連立一次方程式を解くときは
列基本変形を行ってはならない．
その理由はいくつか具体例を見ればわかるであろう．
-
連立一次方程式
$\left\{\begin{array}{l}x-6y=3\\3x+2y=5\end{array}\right.$
を掃き出し法で解いてみよう．
拡大係数行列は
$\left(\begin{array}{cc|c}1&-6&3\\3&2&5\end{array}\right)$ である．
第 $i$ 行の $k$ 倍を第 $j$ 行に加えることを$[\,\mathrm{r_i\stackrel{\times \mathit{k}}{\to}r_j}\,]$と記すことなどはこれまで通りである．
$\left(\begin{array}{cc|c}1&-6&3\\3&2&5\end{array}\right)
\to
\left(\begin{array}{cc|c}1&-6&3\\0&20&-4\end{array}\right)
\ [\,\mathrm{r_1\stackrel{\times (-3)}{\to}r_2}\,]\\[1mm]
\hspace{70pt}\to
\left(\begin{array}{cc|c}1&-6&3\\0&1&-1/5\end{array}\right)
\ [\,\mathrm{r_2\times \frac{1}{20}}\,]\\[1mm]
\hspace{70pt}\to
\left(\begin{array}{cc|c}1&0&9/5\\0&1&-1/5\end{array}\right)
\ [\,\mathrm{r_2\stackrel{\times 6}{\to}r_1}\,]
$
よって解は $\left(\begin{array}{c}x\\y\end{array}\right)=\dfrac{1}{5}\left(\begin{array}{c}9\\-1\end{array}\right)$ となる．
今行ったことを，元の $x,y$ を含む式の形で辿ってみると
$\left\{\begin{array}{l}x-6y=3\\3x+2y=5\end{array}\right.
\to
\left\{\begin{array}{l}x-6y=3\\20y=-4\end{array}\right.
\quad [\,\mathrm{r_1\stackrel{\times (-3)}{\to}r_2}\,]\\[1mm]
\hspace{65pt}\to
\left\{\begin{array}{l}x-6y=3\\y=-1/5\end{array}\right.
\quad [\,\mathrm{r_2\times \frac{1}{20}}\,]\\[1mm]
\hspace{65pt}\to
\left\{\begin{array}{l}x=9/5\\y=-1/5\end{array}\right.
\quad [\,\mathrm{r_2\stackrel{\times 6}{\to}r_1}\,]
$
ということになる．すなわち，「掃き出し法」とは，連立一次方程式を解く最も基本的な方法である「加減法」と呼ばれているものに他ならない．
この様子を見れば列基本変形を行ってはならない理由がわかるであろう．
これまでに，逆行列を用いる方法やCramerの公式などが登場したが，一般的な連立一次方程式を扱うには，結局はこの「掃き出し法」という素朴な方法が優れているということで広く用いられている．
-
同様の方法で
$\left\{\begin{array}{l}x+y+z=3\\x+3y+5z=1\\3x+5y+8z=5\end{array}\right.$
を掃き出し法で解くと
$\left(\begin{array}{ccc|c}1&1&1&3\\1&3&5&1\\3&5&8&5\end{array}\right)\\\
\hspace{20pt}\to
\left(\begin{array}{ccc|c}1&1&1&3\\0&2&4&-2\\0&2&5&-4\end{array}\right)
\ \begin{array}{l}
[\,\mathrm{r_1\stackrel{\times (-1)}{\to}r_2}\,]\\
[\,\mathrm{r_1\stackrel{\times (-3)}{\to}r_3}\,]
\end{array}
\\[1mm]
\hspace{20pt}\to
\left(\begin{array}{ccc|c}1&1&1&3\\0&1&2&-1\\0&2&5&-4\end{array}\right)
\ \begin{array}{l}
[\,\mathrm{r_2 \times \frac{1}{2}}\,]
\end{array}
\\[1mm]
\hspace{20pt}\to
\left(\begin{array}{ccc|c}1&0&-1&4\\0&1&2&-1\\0&0&1&-2\end{array}\right)
\ \begin{array}{l}
[\,\mathrm{r_2\stackrel{\times (-1)}{\to}r_1}\,]\\
[\,\mathrm{r_2\stackrel{\times (-2)}{\to}r_3}\,]
\end{array}
\\[1mm]
\hspace{20pt}\to
\left(\begin{array}{ccc|c}1&0&0&2\\0&1&0&3\\0&0&1&-2\end{array}\right)
\ \begin{array}{l}
[\,\mathrm{r_3\stackrel{\times 1}{\to}r_1}\,]\\
[\,\mathrm{r_3\stackrel{\times (-2)}{\to}r_2}\,]
\end{array}
$
より解は $\left(\begin{array}{c}x\\y\\z\end{array}\right)=\left(\begin{array}{c}2\\3\\-2\end{array}\right)$ となる．
一般に，連立一次方程式の解は一意とは限らないし，解をもたない場合もある．
従って，拡大係数行列を常に $(\,E\,|\,\mathbf{b}'\,)$ という形に変形できるわけではない．
例えば
$\left\{\begin{array}{l}x+y+z=1\\x+2y+3z=-1\\2x+5y+8z=-4\end{array}\right.$
の場合は
$\left(\begin{array}{ccc|c}1&1&1&1\\1&2&3&-1\\2&5&8&-4\end{array}\right)\\[1mm]
\hspace{20pt}\to
\left(\begin{array}{ccc|c}1&1&1&1\\0&1&2&-2\\0&3&6&-6\end{array}\right)
\ \begin{array}{l}
[\,\mathrm{r_1\stackrel{\times (-1)}{\to}r_2}\,]\\
[\,\mathrm{r_1\stackrel{\times (-2)}{\to}r_3}\,]
\end{array}\\[1mm]
\hspace{20pt}\to
\left(\begin{array}{ccc|c}1&0&-1&3\\0&1&2&-2\\0&0&0&0\end{array}\right)
\ \begin{array}{l}
[\,\mathrm{r_2\stackrel{\times (-1)}{\to}r_1}\,]\\
[\,\mathrm{r_2\stackrel{\times (-3)}{\to}r_3}\,]
\end{array}$
となり，右辺を単位行列の形にするのは不可能である．ここで $x,y,z$ の式に戻すと
$\left\{\begin{array}{l}x-z=3\\y+2z=-2\end{array}\right.$
となっているので，$z=t$ とおいて，解は
$\left(\begin{array}{c}x\\y\\z\end{array}\right)
=\left(\begin{array}{c}3+t\\-2-2t\\t\end{array}\right)
=\left(\begin{array}{c}3\\-2\\0\end{array}\right)
+t\left(\begin{array}{c}1\\-2\\1\end{array}\right)$
と表わされる．この $t\in\mathbf{R}$ は任意定数であって，
自由変数と呼ばれる．
解を表すのに必要な自由変数の数を
解の自由度といい，今の例では解の自由度は $1$ である．また，適切な数の自由変数を用いて表された解をこの方程式の
一般解という．
一般には，ある程度変形を行わないと解の自由度(そもそも解があるかどうか)はわからないが，いずれにしても変形の基本方針は，左辺を単位行列にできるだけ近づける，すなわち今の例の第 $1$ 列，第 $2$ 列のような「一か所が $1$ で他はすべて $0$」という列をできるだけ多く作ることである．
そのような形にできる列の個数が係数行列の階数であり，それ以外の列に対応する未知数(今の例では $z$ )は $t$ など自由変数でおかれることになるので
(係数行列の階数) $+$ (解の自由度) $=$ (未知数の数)
という関係が常に成り立つ．
特に，係数行列が正則ならば解の自由度は $0$，すなわち一意解をもつ．
これらのことについては講を改めて詳しく述べる．
$\left\{\begin{array}{l}x-2y+z+3w=-1\\2x-4y+3z+5w=4\\3x-6y+5z+7w=9\end{array}\right.$
を掃き出し法で解くと
$\left(\begin{array}{cccc|c}1&-2&1&3&-1\\2&-4&3&5&4\\3&-6&5&7&9\end{array}\right)\\[1mm]
\hspace{20pt}\to
\left(\begin{array}{cccc|c}1&-2&1&3&-1\\0&0&1&-1&6\\0&0&2&-2&12\end{array}\right)
\ \begin{array}{l}
[\,\mathrm{r_1\stackrel{\times (-2)}{\to}r_2}\,]\\
[\,\mathrm{r_1\stackrel{\times (-3)}{\to}r_3}\,]
\end{array}
\\[1mm]
\hspace{20pt}\to
\left(\begin{array}{cccc|c}1&-2&0&4&-7\\0&0&1&-1&6\\0&0&0&0&0\end{array}\right)\ \begin{array}{l}
[\,\mathrm{r_2\stackrel{\times (-1)}{\to}r_1}\,]\\
[\,\mathrm{r_2\stackrel{\times (-2)}{\to}r_3}\,]
\end{array}$
より
$\left\{\begin{array}{l}x-2y+4w=-7\\z-w=6\end{array}\right.$
が得られるから，$y=s$，$w=t$ とおいて，解は
$\left(\begin{array}{c}x\\y\\z\\w\end{array}\right)
=\left(\begin{array}{c}-7+2s-4t\\s\\6+t\\t\end{array}\right)\\[1mm]
\hspace{28pt}=\left(\begin{array}{c}-7\\0\\6\\0\end{array}\right)
+s\left(\begin{array}{c}2\\1\\0\\0\end{array}\right)
+t\left(\begin{array}{c}-4\\0\\1\\1\end{array}\right)$
と表わされる．解の自由度は $2$ である．未知数の数は $4$，係数行列の階数が $2$ であることにも注意しておこう．
この例のように自由度をもつ解の表し方は一意ではない．
一般に，連立一次方程式 $A\mathbf{x}=\mathbf{b}$ が自由度 $m$ の解をもつとき，
その一般解は，ベクトル $\mathbf{b}'$ および一次独立なベクトルの組 $\{\,\mathbf{c}_1,\mathbf{c}_2,\ldots,\mathbf{c}_m\,\}$ を用いて
$\mathbf{x}=\mathbf{b}'+t_1\mathbf{c}_1+t_2\mathbf{c}_2+\cdots+t_m\mathbf{c}_m$ $(t_1,t_2,\ldots,t_m\in\mathbf{R})$
と表わされるが，このとき
$A\mathbf{b}'=\mathbf{b}$，$A\mathbf{c}_1=A\mathbf{c}_2=\cdots=A\mathbf{c}_m=\mathbf{0}$
が成り立つ．逆にこれらの条件を満たしていれば一般解を正しく表していると言える．
例えば，以下はすべてこの例の方程式の一般解である．
$\left(\begin{array}{c}x\\y\\z\\w\end{array}\right)
=\left(\begin{array}{c}-5\\1\\6\\0\end{array}\right)
+s\left(\begin{array}{c}2\\1\\0\\0\end{array}\right)
+t\left(\begin{array}{c}-2\\1\\1\\1\end{array}\right)$
$\left(\begin{array}{c}x\\y\\z\\w\end{array}\right)
=\left(\begin{array}{c}1\\0\\4\\-2\end{array}\right)
+s\left(\begin{array}{c}0\\2\\1\\1\end{array}\right)
+t\left(\begin{array}{c}-4\\0\\1\\1\end{array}\right)$
$\left(\begin{array}{c}x\\y\\z\\w\end{array}\right)
=\left(\begin{array}{c}3\\3\\5\\-1\end{array}\right)
+s\left(\begin{array}{c}0\\2\\1\\1\end{array}\right)
+t\left(\begin{array}{c}2\\3\\1\\1\end{array}\right)$
また
$\left\{\begin{array}{l}x+y+z=1\\x+2y+3z=-1\\2x+5y+8z=-2\end{array}\right.$
だと
$\left(\begin{array}{ccc|c}1&1&1&1\\1&2&3&-1\\2&5&8&-2\end{array}\right)$$\to
\cdots
\to
\left(\begin{array}{ccc|c}1&0&-1&3\\0&1&2&-2\\0&0&0&2\end{array}\right)
$
となり，第 $3$ 行は $0=2$ となっているのでこれは不可能である．すなわちこのような場合は解は存在しない．
掃き出し法による逆行列の計算
逆行列を求めることも，いくつかの連立一次方程式を解くことだと考えられる．
例えば，$3\times 3$ の場合は
$\mathbf{e}_1=\left(\begin{array}{c}1\\0\\0\end{array}\right)$，
$\mathbf{e}_2=\left(\begin{array}{c}0\\1\\0\end{array}\right)$，
$\mathbf{e}_3=\left(\begin{array}{c}0\\0\\1\end{array}\right)$
とおけば，与えられた $3\times3$ 行列 $A$ に対して $AX=E$ を満たす行列 $X$ を求めることは，三つの連立一次方程式
$A\mathbf{x}=\mathbf{e}_1$，
$A\mathbf{x}=\mathbf{e}_2$，
$A\mathbf{x}=\mathbf{e}_3$
をそれぞれ解くことと同じである
詳しく!．
例えば
$A=\left(\begin{array}{ccc}1&1&0\\0&1&2\\1&2&3\end{array}\right)$
の逆行列は
$A^{-1}=\left(\begin{array}{ccc}-1&-3&2\\2&3&-2\\-1&-1&1\end{array}\right)$
であって，確かに
$\left(\begin{array}{ccc}1&1&0\\0&1&2\\1&2&3\end{array}\right)
\left(\begin{array}{ccc}-1&-3&2\\2&3&-2\\-1&-1&1\end{array}\right)
=\left(\begin{array}{ccc}1&0&0\\0&1&0\\0&0&1\end{array}\right)$
が成り立っているが，これを
$\left(\begin{array}{ccc}1&1&0\\0&1&2\\1&2&3\end{array}\right)
\left(\begin{array}{c}-1\\2\\-1\end{array}\right)
=\left(\begin{array}{c}1\\0\\0\end{array}\right)$
$\left(\begin{array}{ccc}1&1&0\\0&1&2\\1&2&3\end{array}\right)
\left(\begin{array}{c}-3\\3\\-1\end{array}\right)
=\left(\begin{array}{c}0\\1\\0\end{array}\right)$
$\left(\begin{array}{ccc}1&1&0\\0&1&2\\1&2&3\end{array}\right)
\left(\begin{array}{c}2\\-2\\1\end{array}\right)
=\left(\begin{array}{c}0\\0\\1\end{array}\right)$
と見れば，
$A^{-1}$ の各列ベクトルが三つの連立一次方程式
$A\mathbf{x}=\mathbf{e}_1$，
$A\mathbf{x}=\mathbf{e}_2$，
$A\mathbf{x}=\mathbf{e}_3$
それぞれ
の解となっていることがわかる．
従って，行基本変形により
$(\,A\,|\,\mathbf{e}_1\ \mathbf{e}_2\ \mathbf{e}_3\,)
\to\cdots\to(\,E\,|\,\mathbf{b}_1\ \mathbf{b}_2\ \mathbf{b}_3\,)$
という形が得られれば，$A$ の逆行列が $A^{-1}=(\,\mathbf{b}_1\ \mathbf{b}_2\ \mathbf{b}_3\,)$ と求まったことになる．
-
$A=\left(\begin{array}{ccc}1&1&0\\1&2&2\\2&3&3\end{array}\right)$ とすると
$\left(\begin{array}{ccc|ccc}1&1&0&1&0&0\\1&2&2&0&1&0\\2&3&3&0&0&1\end{array}\right)\\[1mm]
\hspace{10pt}\to\left(\begin{array}{ccc|ccc}1&1&0&1&0&0\\0&1&2&-1&1&0\\0&1&3&-2&0&1\end{array}\right)
\ \begin{array}{l}
[\,\mathrm{r_1\stackrel{\times (-1)}{\to}r_2}\,]\\
[\,\mathrm{r_1\stackrel{\times (-2)}{\to}r_3}\,]
\end{array}\\[1mm]
\hspace{10pt}\to\left(\begin{array}{ccc|ccc}1&0&-2&2&-1&0\\0&1&2&-1&1&0\\0&0&1&-1&-1&1\end{array}\right)
\ \begin{array}{l}
[\,\mathrm{r_2\stackrel{\times (-1)}{\to}r_1}\,]\\
[\,\mathrm{r_2\stackrel{\times (-1)}{\to}r_3}\,]
\end{array}\\[1mm]
\hspace{10pt}\to\left(\begin{array}{ccc|ccc}1&0&0&0&-3&2\\0&1&0&1&3&-2\\0&0&1&-1&-1&1\end{array}\right)
\ \begin{array}{l}
[\,\mathrm{r_3\stackrel{\times 2}{\to}r_1}\,]\\
[\,\mathrm{r_3\stackrel{\times (-2)}{\to}r_2}\,]
\end{array}$
より $A^{-1}=\left(\begin{array}{ccc}0&-3&2\\1&3&-2\\-1&-1&1\end{array}\right)$．
-
$B=\left(\begin{array}{ccc}1&1&0\\1&2&2\\2&5&6\end{array}\right)$ とすると
$\left(\begin{array}{ccc|ccc}1&1&0&1&0&0\\1&2&2&0&1&0\\2&5&6&0&0&1\end{array}\right)\\[1mm]
\hspace{10pt}\to\left(\begin{array}{ccc|ccc}1&1&0&1&0&0\\0&1&2&-1&1&0\\0&3&6&-2&0&1\end{array}\right)
\ \begin{array}{l}
[\,\mathrm{r_1\stackrel{\times (-1)}{\to}r_2}\,]\\
[\,\mathrm{r_1\stackrel{\times (-2)}{\to}r_3}\,]
\end{array}\\[1mm]
\hspace{10pt}\to\left(\begin{array}{ccc|ccc}1&0&-2&2&-1&0\\0&1&2&-1&1&0\\0&0&0&1&-3&1\end{array}\right)
\ \begin{array}{l}
[\,\mathrm{r_2\stackrel{\times (-1)}{\to}r_1}\,]\\
[\,\mathrm{r_2\stackrel{\times (-3)}{\to}r_3}\,]
\end{array}$
この第 $3$ 行のように左辺にすべて $0$ である行が現れた場合は，
方程式の解はない，あるいは $\det{B}=0$ ということを意味するから，$B$ は逆行列をもたない．