連立一次方程式と行列
連立一次方程式は行列を用いて表すことができます。
$$
\begin{cases}
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}\\
&&\vdots&&&&\vdots\\
a_{m1}x_1&+a_{m2}x_2&+&\cdots&+a_{mn}x_n&=& b_{m}
\end{cases}
\Longrightarrow
\begin{pmatrix}
a_{11}&a_{12}&\cdots&a_{1n}\\
a_{21}&a_{22}&\cdots&a_{2n}\\
&&\vdots\\
a_{m1}&a_{m2}&\cdots&a_{mn}\\
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2\\
\vdots\\
x_n
\end{pmatrix}
=
\begin{pmatrix}
b_1\\
b_2\\
\vdots\\
b_m
\end{pmatrix}
$$
左の連立一次方程式は右のように行列の等式で表せる。右の行列 \(A=(a_{ij})\) を左の連立一次方程式の係数行列という。また、係数行列 \(A=(a_{ij})\) と右辺のベクトル \(\vec b=(b_i)\) を横に並べたブロック行列 \((A|\vec b)\) を拡大係数行列という。
$$
\begin{aligned}
&\begin{cases}
2x_1&+3x_2&=&1\\
4x_1&+5x_2&=&2
\end{cases}
&\Longrightarrow
&&&\begin{pmatrix}
2&3\\
4&5
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2
\end{pmatrix}
=
\begin{pmatrix}
1\\
2
\end{pmatrix}\\
\\
&\begin{cases}
x_1&+2x_2&+3x_3=&1\\
4x_1&+5x_2&+6x_3=&2
\end{cases}
&\Longrightarrow
&&&\begin{pmatrix}
1&2&3\\
4&5&6
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2\\
x_3
\end{pmatrix}
=
\begin{pmatrix}
1\\
2
\end{pmatrix}\\
\\
&\begin{cases}
x_1&+2x_2&=&1\\
3x_1&+4x_2&=&2\\
5x_1&+6x_2&=&3
\end{cases}
&\Longrightarrow
&&&\begin{pmatrix}
1&2\\
3&4\\
5&6
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2
\end{pmatrix}
=
\begin{pmatrix}
1\\
2\\
3
\end{pmatrix}
\end{aligned}$$
\(2\) 次正方行列 \(A\) は、\(\det A\neq 0\) のときに限り逆行列が存在するのでした。そのため、次のように解の求めることができます。
$$
\begin{pmatrix}
2&3\\
4&5
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2
\end{pmatrix}
=
\begin{pmatrix}
1\\
2
\end{pmatrix}
$$係数行列 \(A=
\begin{pmatrix}
2&3\\
4&5
\end{pmatrix}
\) は、\(\det A=-2 \neq 0\) を満たすので、逆行列が存在する。逆行列は、\(A^{-1}=
\frac{1}{-2}
\begin{pmatrix}
5&-3\\
-4&2
\end{pmatrix}
\) だから、これを方程式の両辺左からかければ、$$
\begin{aligned}
\begin{pmatrix}
x_1\\
x_2
\end{pmatrix}
&=
\frac{1}{-2}
\begin{pmatrix}
5&-3\\
-4&2
\end{pmatrix}
\begin{pmatrix}
1\\
2
\end{pmatrix}\\
\\
&=
\begin{pmatrix}
\frac{1}{2}\\
0
\end{pmatrix}
\end{aligned}$$
もちろん、\(3\) 次、\(4\) 次の正方行列でも逆行列が求められれば、上の問題のようにして解を求めることができます。しかし、例えば \(\det A = 0\) のときや、係数行列が正方行列でない場合はこの方法は使えません。このような場合でも解を求めることができるのが、本記事の主題である「掃き出し法」です。「掃き出し法」は「逆行列を求める方法」よりも、計算量が少ない場合が多いというメリットがあります。
掃き出し法による連立一次方程式の解法（具体例）
解がただ一つ存在する場合
$$
\begin{pmatrix}
1&2\\
3&4
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2
\end{pmatrix}
=
\begin{pmatrix}
1\\
2
\end{pmatrix}
$$
拡大係数行列に、行に関する基本変形をする。$$
\left(
\begin{array}{cc|c}
1&2&1\\
3&4&2
\end{array}
\right)
\rightarrow
\left(
\begin{array}{cc|c}
1&2&1\\
0&-2&-1
\end{array}
\right)
\rightarrow
\left(
\begin{array}{cc|c}
1&0&0\\
0&-2&-1
\end{array}
\right)
\rightarrow
\left(
\begin{array}{cc|c}
1&0&0\\
0&1&\frac{1}{2}
\end{array}
\right)
$$
よって、解くべき方程式は$$
\begin{cases}
x_1&&=0\\
&x_2&=\frac{1}{2}
\end{cases}
$$となるので、解は \(
\begin{pmatrix}x_1\\x_2\end{pmatrix}
=\begin{pmatrix}0\\\frac{1}{2}\end{pmatrix}\)
$$
\begin{pmatrix}
1&2\\
3&4\\
4&6
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2
\end{pmatrix}
=
\begin{pmatrix}
1\\
2\\
3
\end{pmatrix}
$$
拡大係数行列に、行に関する基本変形をする。$$
\left(
\begin{array}{cc|c}
1&2&1\\
3&4&2\\
4&6&3
\end{array}
\right)
\rightarrow
\left(
\begin{array}{cc|c}
1&2&1\\
0&-2&-1\\
0&-2&-1
\end{array}
\right)
\rightarrow
\left(
\begin{array}{cc|c}
1&0&0\\
0&-2&-1\\
0&0&0
\end{array}
\right)
\rightarrow
\left(
\begin{array}{cc|c}
1&0&0\\
0&1&\frac{1}{2}\\
0&0&0
\end{array}
\right)
$$
よって、解くべき方程式は$$
\begin{cases}
x_1&&=0\\
&x_2&=\frac{1}{2}
\end{cases}
$$となるので、解は \(
\begin{pmatrix}x_1\\x_2\end{pmatrix}
=\begin{pmatrix}0\\\frac{1}{2}\end{pmatrix}\)
解が複数存在する場合
$$
\begin{pmatrix}
1&0&2\\
2&1&7\\
1&1&5
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2\\
x_3
\end{pmatrix}
=
\begin{pmatrix}
1\\
4\\
3
\end{pmatrix}
$$
拡大係数行列に、行に関する基本変形をする。$$
\left(
\begin{array}{ccc|c}
1&0&2&1\\
2&1&7&4\\
1&1&5&3
\end{array}
\right)
\rightarrow
\left(
\begin{array}{ccc|c}
1&0&2&1\\
&1&3&2\\
&1&3&2
\end{array}
\right)
\rightarrow
\left(
\begin{array}{ccc|c}
1&0&2&1\\
&1&3&2\\
&&&
\end{array}
\right)
$$
よって、解くべき方程式は$$
\begin{cases}
x_1&&+2x_3&=1\\
&x_2&+3x_3&=2
\end{cases}
$$となるので、解は \(t\) を任意定数として$$
\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}
=\begin{pmatrix}1-2t\\2-3t \\ t \end{pmatrix}
=\begin{pmatrix}1\\2\\0\end{pmatrix}
+t\begin{pmatrix}-2\\-3\\1\end{pmatrix}$$
解が存在しない場合
$$
\begin{pmatrix}
1&0&2\\
2&1&7\\
1&1&5
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2\\
x_3
\end{pmatrix}
=
\begin{pmatrix}
1\\
4\\
2
\end{pmatrix}
$$
拡大係数行列に、行に関する基本変形をする。$$
\left(
\begin{array}{ccc|c}
1&0&2&1\\
2&1&7&4\\
1&1&5&2
\end{array}
\right)
\rightarrow
\left(
\begin{array}{ccc|c}
1&0&2&1\\
&1&3&2\\
&1&3&1
\end{array}
\right)
\rightarrow
\left(
\begin{array}{ccc|c}
1&0&2&1\\
&1&3&2\\
&&&-1
\end{array}
\right)
$$
よって、解くべき方程式は$$
\begin{cases}
x_1&&+2x_3&=1\\
&x_2&+3x_3&=2\\
0=-1
\end{cases}
$$となるので、解は存在しない。（三番目の等式 \(0=-1\) は成り立たないからである。）
掃き出し法による連立一次方程式の解法（原理）
具体例として挙げたものは全て以下の手順に従っています。
- 方程式を拡大係数行列 \((A|\vec b)\) で表す。
- 拡大係数行列を行に関して基本変形する。
- 「簡単」な拡大係数行列 \((A’|\vec {b’})\) になったら、解を求める。
この手順の正しさを保証しているのは、行に関する基本変形によって、方程式の解が変わらないということです。
行に関する基本変形によって、方程式の解が変わらないことを示せ。
（証明）
行に関する基本変形を行うことは、対応する基本行列 \(P\) を左からかけることと同じである。基本行列 \(P\) は正則だから、基本行列をかける式変形は同値変形である。すなわち、$$
A\vec x=\vec b \Longleftrightarrow PA\vec x=P\vec b
$$これは、方程式の解 \(\vec x\) が行の基本変形によって変わらないことを意味する。（証明終）
そして、「簡単な」拡大係数行列とはどのような形かについても述べておきます。
$$\left(
\begin{array}{ccc|c}
1&0&0&d_1\\
0&1&0&d_2\\
0&0&1&d_3
\end{array}
\right)
$$この拡大係数行列が表す連立一次方程式の解は、$$
\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}
=\begin{pmatrix}d_1\\d_2 \\ d_3 \end{pmatrix}
$$
$$\left(
\begin{array}{ccc|c}
1&0&b_1&d_1\\
0&1&b_2&d_2\\
0&0&0&0
\end{array}
\right)
$$この拡大係数行列が表す連立一次方程式の解は、\(t\) を任意定数として$$
\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}
=\begin{pmatrix}d_1-b_1t\\d_2-b_2t \\ t \end{pmatrix}
=\begin{pmatrix}d_1\\d_2\\0\end{pmatrix}+t\begin{pmatrix}-b_1\\-b_2\\1\end{pmatrix}$$
$$\left(
\begin{array}{ccc|c}
1&b&c&d\\
0&0&0&0\\
0&0&0&0
\end{array}
\right)
$$この拡大係数行列が表す連立一次方程式の解は、\(s, t\) を任意定数として$$
\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}
=\begin{pmatrix}d-bs-ct\\s \\ t \end{pmatrix}
=\begin{pmatrix}d\\0\\0\end{pmatrix}
+s\begin{pmatrix}-b\\1\\0\end{pmatrix}
+t\begin{pmatrix}-c\\0\\1\end{pmatrix}$$
「簡単」な拡大係数行列に出来たら、解を求めるのは容易です。成分たちを規則的に並べるだけですからね。ちなみに、任意定数をもつ解はベクトル表記する方が都合がよいことが多いです。一般の場合は次のような階段行列を目指せばよいです。
$$\left(
\begin{array}{cccccc|c}
1&a_2&0&a_4&0&a_6&d_1\\
0&0&1&b_4&0&b_6&d_2\\
0&0&0&0&1&c_6&d_3\\
0&0&0&0&0&0&0\\
0&0&0&0&0&0&0
\end{array}
\right)
$$この拡大係数行列が表す連立一次方程式の解は、任意定数を \(3\) 個もつ。\(1\) が書いていない列、すなわち \(2,4,6\) に対応する \(x_2,x_4,x_6\) に任意定数 \(t_2,t_4,t_6\) を代入して解けばよい。
解くべき方程式は、次のようになるので、$$
\begin{cases}
x_1&+a_2x_2&&+a_4x_4&&+a_6x_6&=&d_1\\
&&x_3&+b_4x_4&&+b_6x_6&=&d_2\\
&&&&x_5&+c_6x_6&=&d_3
\end{cases}
$$任意定数 \(t_2,t_4,t_6\) を用いて、解は以下のように表せる。
$$
\begin{pmatrix}x_1\\x_2\\x_3\\x_4\\x_5\\x_6\end{pmatrix}
=\begin{pmatrix}d_1\\0\\d_2\\0\\d_3\\0\end{pmatrix}
+t_2\begin{pmatrix}-a_2\\1\\0\\0\\0\\0\end{pmatrix}
+t_4\begin{pmatrix}-a_4\\0\\-b_4\\1\\0\\0\end{pmatrix}
+t_6\begin{pmatrix}-a_6\\0\\-b_6\\0\\-c_6\\1\end{pmatrix}
$$
$$\left(
\begin{array}{ccc|c}
1&a&0&d_1\\
0&0&1&d_2\\
0&0&0&0
\end{array}
\right)
$$この拡大係数行列が表す連立一次方程式の解は、\(t\) を任意定数として$$
\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}
=\begin{pmatrix}d_1\\0\\d_2\end{pmatrix}
+t\begin{pmatrix}-a\\1\\0\end{pmatrix}$$
実際には次のような階段形にできた時点で、とりあえず解は求められます。計算は大変かもしれませんが。
$$\left(
\begin{array}{cccccccc|c}
1&*&*&*&*&*&*&*&*\\
0&0&1&*&*&*&*&*&*\\
0&0&0&0&0&1&*&*&*\\
0&0&0&0&0&0&0&0&0\\
0&0&0&0&0&0&0&0&0
\end{array}
\right)
$$この拡大係数行列が表す連立一次方程式の解は、任意定数を \(5\) 個もつ。\(1\) が書いていない列、すなわち \(2,4,5,7,8\) に対応する \(x_2,x_4,x_5,x_7,x_8\) に任意定数を代入して解けばよい。
$$\left(
\begin{array}{cccccc|c}
1&10&11&12&13&14&5\\
0&0&1&20&21&22&25\\
0&0&0&0&1&30&125\\
0&0&0&0&0&0&0
\end{array}
\right)
$$この拡大係数行列が表す連立一次方程式の解は、任意定数を \(3\) 個もつ。\(1\) が書いていない列、すなわち \(2,4,6\) に対応する \(x_2,x_4,x_6\) に任意定数を代入して解けばよい。
注意点
掃き出し法による連立一次方程式の解法において、行基本変形を強調しました。列基本変形ではいけません。方程式の解が変わってしまうからです。例えば、$$
\begin{cases}
x_1&+x_2&=&1\\
x_1&&=&0
\end{cases}$$の解は \(\begin{pmatrix}0\\1\end{pmatrix}\) ですが、列の入れ替えをすると方程式が$$
\begin{cases}
x_1&+x_2&=&1\\
&+x_2&=&0
\end{cases}$$となり、解は \(\begin{pmatrix}1\\0\end{pmatrix}\) となってしまいます。
ちなみに、この掃き出し法は、中学数学の連立一次方程式の「加減法」の拡張になっています。あの変形は同値変形だったということです。