続掃き出し法

連立方程式の解き方

掃き出し法の続き

掃き出し法の続きです。前回は拡大係数行列の点線の左側の正方行列を単位行列にして連立方程式を解きました。しかし、常に左側の行列を単位行列に出来るとは限りません。このようなときにはどうやって解けばよいのかを解説します。

階段行列

行列を行基本変形していったとき単位行列に出来ない例としては、まず、行列の行と列の数が一致しないときがあります。例えば
$\left(\begin{array}{ccc} 1& 0 & 1\\ 0& 1 & 1 \end{array}\right)$
のような2行3列の行列は単位行列に出来ません。

また、たとえ行と列の数が一致していても単位行列に出来ない場合があります。それはある行の全ての成分が0になってしまうときです。例えば
$\left(\begin{array}{ccc} 1& 0 & 1\\ 0& 1 & 2\\ 0& 0 & 0 \end{array}\right)$
は3次正方行列ですが、単位行列には出来ません。

しかし、単位行列に出来なくても、すべての行列は階段行列という行列の形に変形することが出来ます。階段行列とは
$\left(\begin{array}{ccccc} 0 & 1 & 3 & 1 & 1\\ 0 & 0 & 2 & 2 & 1\\ 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 \end{array}\right)$
のように0でない成分が階段状にならんでいる行列をいいます。

ただし、階段の段が一度に増えていいのは一段までです。一気に二段以上増えてはいけません。例えば、
$\left(\begin{array}{ccccc} 0 & 1 & 3 & 1 & 1\\ 0 & 0 & 2 & 2 & 1\\ 0 & 0 & 3 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 \end{array}\right)$
は階段行列ではありません。

行列の階数

行列を、基本変形によって階段行列にしたとき、階段の段の数を行列の階数(rank)といいます。例えば、先ほどの行列を
$A:=\left(\begin{array}{ccccc} 0 & 1 & 3 & 1 & 1\\ 0 & 0 & 2 & 2 & 1\\ 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 \end{array}\right)$
とすると $\rm{rank}A=3$ です。

解の存在性の判定

行列の階数を使って連立方程式に解が存在するかどうかをサッと判定することが出来ます。

まず、拡大係数行列を考え、これを行基本変形によって階段行列にします。例えば、
$A':=\left(\begin{array}{ccccccc} 0 & 1 & 3 & 1 & 1 & : & 1\\ 0 & 0 & 2 & 2 & 1 & : & 2\\ 0 & 0 & 0 & 0 & 1 & : & 1\\ 0 & 0 & 0 & 0 & 0 & : & 1 \end{array}\right)$
です。このとき、点線の左側で階段の段の数が増えていたらその連立方程式には解がありません。また、逆に段の数が増えていなければ解があります。
すなわち、この例では解はありません。

これは階数を使うと次のようにいえます。
点線の左側の行列を $A$ 、拡大係数行列を $A'$ で表すと拡大係数行列 $A'$ で表される連立方程式が解を持つための必要十分条件は $\rm{rank}A=\rm{rank}A'$ が成り立つことである。

上の例では $\rm{rank}A=3,\ \rm{rank}A'=4$ より解なしとなります。

連立方程式の解のひとつを求める

連立方程式の解が存在するための必要十分条件が分かったところで、解の求め方を解説したいと思います。解の一つを $\mathbf{x}_0$ としたとき、解空間は $\mathbf{x}_0+\rm{Ker}f$ という構造をしていたのでまずは解の一つ $\mathbf{x}_0$ を求める方法を解説します。

すべての行列は階段行列に出来ますが、実は、行基本変形でもう少し扱いやすい形に出来ます。それは、それぞれの階段の一番左側の列を単位ベクトルにすることです。すなわち、
$\left(\begin{array}{cccc} 1 & 2 & 1 & 1\\ 0 & 1 & 2 & 1\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{array}\right)$
なら、行基本変形で
$\left(\begin{array}{cccc} 1 & 0 & -3 & 0\\ 0 & 1 & 2 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{array}\right)$
とできます。この形をつくることで、連立方程式の解の一つ $\mathbf{x}_0$ が簡単に分かります。

例としてこの拡大係数行列で表される連立方程式のの解の一つを求めてみます。
$\left(\begin{array}{ccccccc} 1 & 0 & -3 & 0 & 2 & : & 1\\ 0 & 1 & 2 & 0 & 1 & : & 3\\ 0 & 0 & 0 & 1 & 4 & : & 2\\ 0 & 0 & 0 & 0 & 0 & : & 0 \end{array}\right)$

まず、点線の左側の行列のそれぞれの列が $x_1$ から $x_5$ に対応しています。
$\ \ \ \ \ \ \ \ x_1\ x_2\ x_3\ x_4\ x_5\\ \left(\begin{array}{ccccccc} 1 & 0 & -3 & 0 & 2 & : & 1\\ 0 & 1 & 2 & 0 & 1 & : & 3\\ 0 & 0 & 0 & 1 & 4 & : & 2\\ 0 & 0 & 0 & 0 & 0 & : & 0 \end{array}\right)$

いま、階段のそれぞれの段の一番左側は単位ベクトルになっています。そこで、その単位ベクトルになっている列以外の列に対応する変数を0にします。今の場合は $x_3=0,\ x_5=0$ とします。

そうすると単位ベクトルになっている列が残ります。
$\ \ \ \ x_1\ x_2\ x_4\\ \left(\begin{array}{cccccc} 1 & 0 & 0 & : & 1\\ 0 & 1 & 0 & : & 3\\ 0 & 0 & 1 & : & 2\\ 0 & 0 & 0 & : & 0 \end{array}\right)$
ここで、それぞれの単位ベクトルに対応する数が求める解になっています。

今の場合は
$\left(\begin{array}{c}x_1\\x_2\\x_4\end{array}\right)=\left(\begin{array}{c}1\\3\\2\end{array}\right)$
です。
さきほどの $x_3=0,\ x_5=0$ とあわせると、この連立方程式のの解の一つは
$\left(\begin{array}{c}x_1\\x_2\\x_3\\x_4\\x_5\end{array}\right)=\left(\begin{array}{c}1\\3\\0\\2\\0\end{array}\right)$
です。

核空間 $\rm{Ker}f$ を求める

最後に核空間 $\rm{Ker}f$ を求めます。これが求められれば、連立方程式の解全体の集合が分かったことになります。

核空間 $\rm{Ker}f$ はベクトル空間となります。 (すなわち、変数の個数をnとすると $\rm{Ker}f$ は $\mathb{R}^n$ の部分空間 ) よって、 $\rm{Ker}f$ を生成するベクトル(正確には基底)を求めれば良いことになります。

例として、先ほどの行列の核空間を求めてみます。
$\ \ \ \ \ \ \ \ x_1\ x_2\ x_3\ x_4\ x_5\\ \left(\begin{array}{ccccccc} 1 & 0 & -3 & 0 & 2 & : & 1\\ 0 & 1 & 2 & 0 & 1 & : & 3\\ 0 & 0 & 0 & 1 & 4 & : & 2\\ 0 & 0 & 0 & 0 & 0 & : & 0 \end{array}\right)$
核空間を求めるにあたっては点線の右側は必要ありません。よって行列
$\left(\begin{array}{ccccccc} 1 & 0 & -3 & 0 & 2\\ 0 & 1 & 2 & 0 & 1\\ 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & 0 \end{array}\right)$
を考えればOKです。
まず、単位ベクトルでない(各階段の一番左側でない)列に対応する変数のひとつを-1にして残りを全て0にします。
今の場合は、 $x_3=-1,\ x_5=0$ とします。そして0に対応する列は全て消し、-1に対応する列を点線の右側へ持っていきます。
$\ \ \ \ x_1\ x_2\ x_4\\ \left(\begin{array}{ccccccc} 1 & 0 & 0 & : & -3\\ 0 & 1 & 0 & : & 2\\ 0 & 0 & 1 & : & 0\\ 0 & 0 & 0 & : & 0 \end{array}\right)$
ここで、ここで先ほどと同様にそれぞれの単位ベクトルに対応する数を求めると
$\left(\begin{array}{c}x_1\\x_2\\x_4\end{array}\right)=\left(\begin{array}{c}-3\\2\\0\end{array}\right)$
よって、解空間の生成集合のベクトルのひとつ
$\left(\begin{array}{c}x_1\\x_2\\x_3\\x_4\\x_5\end{array}\right)=\left(\begin{array}{c}-3\\2\\-1\\0\\0\end{array}\right)$
が求まりました。

同様にして、残りの単位ベクトルでない列に対応する変数を順番に-1にしていけば $\rm{Ker}f$ の生成集合のベクトルが全て求まります。

つまり、 $x_3=0,\ x_5=-1$ とすれば先程と同様にして
$\left(\begin{array}{c}x_1\\x_2\\x_3\\x_4\\x_5\end{array}\right)=\left(\begin{array}{c}2\\1\\0\\4\\-1\end{array}\right)$
となるので、核空間 $\rm{Ker}f$ の生成集合は
$\left\{\left(\begin{array}{c}-3\\2\\-1\\0\\0\end{array}\right), \ \left(\begin{array}{c}2\\1\\0\\4\\-1\end{array}\right) \right\}$
となります。つまり、これら2つのベクトルの実数倍と和で $\rm{Ker}f$ の元が表せます。
これは
$\rm{Ker}f=\langle\left(\begin{array}{c}-3\\2\\-1\\0\\0\end{array}\right), \ \left(\begin{array}{c}2\\1\\0\\4\\-1\end{array}\right) \rangle$
という記号で表されます。

したがって、この連立方程式の解空間は
$\left(\begin{array}{c}1\\3\\0\\2\\0\end{array}\right)+\langle\left(\begin{array}{c}-3\\2\\-1\\0\\0\end{array}\right), \ \left(\begin{array}{c}2\\1\\0\\4\\-1\end{array}\right)\rangle$
と求められました。
(注意：集合の表示の仕方は一意ではないのでこの形以外でも表すことができます。)

ためしにこの集合の元のうちのいくつかを連立方程式に代入して、ちゃんと解になっているかどうかを確かめてみると良いと思います。

Next : 部分空間とは

続 掃き出し法