【連立方程式編】消去法と階段行列

2017年1月29日作成2018年6月26日更新

こんにちは、おぐえもん(@oguemon_com)です。

今までの記事で行列の基本を学習しましたので、これからは行列をガンガン使って色々考えていきたいと思います。

まずは、行列と深い結びつきを持つ「連立1次方程式」について何回かに分けて議論を展開していきます。

解法の鉄板「消去法」

中学校のおさらいです！これ、どうやって解きますか？

\begin{aligned} \left\{ \begin{array}{rclc} 5x-2y&=&5 &(1) \\ x+y&=&8 &(2) \end{array} \right. \end{aligned}

多分、式の両辺にある数を掛けたり、互いの式を足し合わせたりして、変数の数を減らしていきますよね？

この式だと、こんな感じ。

ステップ1：(2)を $-5$ 倍したものを(1)に足し合わせます（つまり5倍したものを引く）

\begin{aligned} \left\{ \begin{array}{rclc} 5x-2y-5(x+y)&=&5-5*8 &(1)\\ x+y&=&8 &(2) \end{array} \right. \end{aligned}

ステップ2：(1)の両辺に $-\frac{1}{7}$ を掛けます（= $-7$ でわる）

\begin{aligned} \left\{ \begin{array}{rclc} -7y*(-\frac{1}{7})&=&-35*(-\frac{1}{7}) &(1)\\ x+y&=&8 &(2) \end{array} \right. \end{aligned}

ステップ3：(1)と(2)で入れ替えます。

\begin{aligned} \left\{ \begin{array}{rclc} x+y&=&8 &(1)\\ y&=&5 &(2) \end{array} \right. \end{aligned}

ステップ4：(1)に $y=5$ を代入する

\begin{aligned} \left\{ \begin{array}{rclc} x+5&=&8 &(1)\\ y&=&5 &(2) \end{array} \right. \end{aligned}

→答えとして「 $x=3,y=5$ 」が導かれて終了。

さて、こうやって、

ある方程式を何倍かにする
ある方程式を何倍かにしたものを他の方程式に加える
ある2つの方程式を入れ替える

という地道な操作をひたすら繰り返して、変数を消していきました。

このように、上の3操作を駆使して連立方程式を簡単にしていく方法を「消去法」と言います。

ここで、ステップ3の時点で $y$ の値が判明しており、あとは思考停止で代入していくだけという状況ですので、消去法では、ステップ3のような状況（次式みたいな状況）を目指して頑張ることになります。

\begin{aligned} \left\{ \begin{array}{rclc} x+y&=&8 &(1)\\ y&=&5 &(2) \end{array} \right. \end{aligned}

ステップ3の式は、下に行くほど変数の個数が少なく、左辺がギザギザの階段状になっているのが特徴です。この特徴は後ほど重要になってきます。

階段行列

さて、これからは連立方程式を行列に見立てて計算していきます。

前に触れたように、

\begin{aligned} \left\{ \begin{array}{rcl} 5x-2y&=&5 \\ x+y&=&8 \end{array} \right. \end{aligned}

は、次のような行列とベクトルの積の形に変換できました。

\left( \begin{array}{cc} 5 & -2 \\ 1 & 1 \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right)= \left( \begin{array}{c} 5 \\ 8 \end{array} \right)

ここで、次の $A$ を係数行列と呼びます。その名の通り、連立方程式の係数をまとめた行列です。

A=\left( \begin{array}{cc} 5 & -2 \\ 1 & 1 \end{array} \right), \boldsymbol{b}=\left( \begin{array}{c} 5 \\ 8 \end{array} \right)

そして、定数項をまとめたベクトル $\boldsymbol{b}$ を係数行列 $A$ の右側にくっつけた

[A \ \boldsymbol{b}]=\left( \begin{array}{ccc} 5 & -2 & 5\\ 1 & 1 & 8 \end{array} \right)

を拡大係数行列と呼びます。これからは、連立方程式に対応する拡大係数行列について考えることになります。

連立方程式を解くにあたって、拡大係数行列に対して次に掲げる操作（行基本操作）を行うことで、前項のステップ3のような状況を作ります。

行基本操作

ある行を何倍かにする
ある行を何倍かにしたものを他の行に加える
ある2つの行を入れ替える

連立方程式を解くために、チマチマやってきた操作と同じですね。行列に対してチマチマと行基本操作を繰り返すと、やがて次のような形をした行列になります。

\left( \begin{array}{ccc} 1&1&8 \\ 0&1&5 \end{array} \right)

これ、さっき出てきた消去法の「ステップ3」に似てますよね？

ここでのポイントは、行を下るほど、左側にある0の個数が多くなり、ギザギザの階段状になっている点です。（行列のサイズが小さ過ぎて階段状と言えるか微妙ですが…）

このような行列を階段行列と呼ぶことにします。

階段行列と階数(rank)

行番号が増えるほど左端から連続する0の数が増える行列のことを階段行列という（以下の行列 $A$ がその例）。

A=\left( \begin{array}{cccccccc} 0&0&5&4&9&3&2&3 \\ 0&0&0&0&1&3&4&2 \\ 0&0&0&0&0&3&1&0 \\ 0&0&0&0&0&0&0&3 \\ 0&0&0&0&0&0&0&0 \\ \end{array} \right)

また、階段行列において、0でない成分が存在する行の数を階数といい、 $A$ の階数を ${\rm rank}A$ と書く（上の例において ${\rm rank}A=4$ である）。

ただし、 $A$ が階段行列でない場合は、 $A$ に対して行基本操作を行って得られた階段行列の階数のことを $A$ の階数（ ${\rm rank}A$ ）をいう。

ここで、階段行列は、ある1つの連立方程式に対して無数のパターンがあることに注意です！ただし、階段行列のパターンこそ無数にあれど、その階数はみんな同じなので、今後の議論に支障はありません（階数が同じって話は今後どこかの記事で扱います）。

例えば、先ほどの行列

\left( \begin{array}{ccc} 1&1&8 \\ 0&1&5 \end{array} \right)

の階数は2です。

A=\left( \begin{array}{cccccc} 5&4&9&3&2&3 \\ 0&1&2&4&5&6 \\ 0&1&2&3&1&3 \\ 0&0&0&1&4&3 \end{array} \right)

こんな行列はどうでしょうか？って？

バカヤロウ！2行目と3行目で左から並ぶ0の数が被ってるじゃねえか！

こんなのは、行基本操作が甘い証拠です。ちょこちょこっといじって…

A'=\left( \begin{array}{cccccc} 5&4&9&3&2&3 \\ 0&1&2&3&1&3 \\ 0&0&0&1&4&3 \\ 0&0&0&0&0&0 \end{array} \right)

これで初めて階段行列となります。ちなみに階数は3です。

また、零行列の階数は0ということになっていることも覚えておきましょう。

階段行列の作り方

一見難しそうですが、あるルールに従って行基本操作を繰り返せば必ず階段行列が作れます。

念のため、行基本操作を再掲します。

行基本操作

【操作1】ある行を何倍かにする
【操作2】ある行を何倍かにしたものを他の行に加える
【操作3】ある2つの行を入れ替える

さて、作っていきましょう！

階段行列の作り方

A=\left( \begin{array}{cccc} a*{11}&a*{12}&\ldots&a\_{1n} \\ a*{21}&a*{22}&\ldots&a\_{2n} \\ \vdots&\vdots&\ddots&\vdots \\ a*{m1}&a*{m2}&\ldots&a\_{mn} \\ \end{array} \right)

に対して行基本操作を繰り返して階段行列を作ります。

【ステップ1】

$a\_{11}=0$ ならば、1列目にある他の成分の中から0でないものを探し、その行と1行目をチェンジしましょう（操作3）。

1列目の成分が全部 $0$ でどうしようも無いならステップ3へ進みましょう。

【ステップ2】

ステップ1で $a\_{11} \neq 0$ になったら、

(i\text{行目})-(1\text{行目}) \times \frac{1}{a_{11}}a_{i1}

を2行目から $n$ 行目（最終行）までの全てに対して行いましょう（操作2）。これで、 $a*{21}$ 〜 $a*{n1}$ が全て0になります。

【ステップ3】

ステップ2をこなしたら(1)の形を行列が出来上がり、ステップ2を飛ばした場合は(2)のようになったと思います。

(1) \ \left( \begin{array}{cccc} a*{11}&a*{12}&\ldots&a\_{1n} \\ 0&a'_{11}&\ldots&a'_{1(n-1)} \\ \vdots&\vdots&\ddots&\vdots \\ 0&a'_{(m-1)1}&\ldots&a'_{(m-1)(n-1)} \end{array} \right)

(2) \ \left( \begin{array}{cccc} 0&a*{11}&\ldots&a*{1(n-1)} \\ 0&a''_{21}&\ldots&a''_{2(n-1)} \\ \vdots&\vdots&\ddots&\vdots \\ 0&a''_{m1}&\ldots&a''_{m(n-1)} \end{array} \right)

(1)なら、部分的な行列

A'=\left( \begin{array}{ccc} a'_{11}&\ldots&a'_{1(n-1)} \\ \vdots&\ddots&\vdots \\ a'_{(m-1)1}&\ldots&a'_{(m-1)(n-1)} \\ \end{array} \right)

を、

(2)なら、部分的な行列

A''=\left( \begin{array}{ccc} a*{11}&\ldots&a*{1(n-1)} \\ a''_{21}&\ldots&a''_{2(n-1)} \\ \vdots&\ddots&\vdots \\ a''_{m1}&\ldots&a''_{m(n-1)} \\ \end{array} \right)

について、再びステップ1の作業を行い、これを繰り返す（高々列数分の繰り返し）ことで階段行列が完成します。

連立方程式から拡大係数行列 $[A \ \boldsymbol{b}]$ を作って、それに対して行基本操作を次々に展開することで、階段行列を作る。やっていること自体は、今までの解き方と変わらないのですが、行列に見立てた上で「階数」という概念を導入することで、連立方程式を解くことができるだけでなく、連立方程式の解の性質などについても考えることができるようになります。

次回では、階段行列や階数を絡めつつ、連立方程式の解に関する性質を紐解いていきます。