第39話  連立一次方程式

この記事を読む助けになる数学の記事
・数値計算：1話、 5話、 30話、 31話、 33話、 34話、 35話、 36話、 37話、 38話

　今回は次の連立一次方程式 \[ \begin{align} a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n &= c_1 \\\\ a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n &= c_2 \\\\ \ \ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\\\ a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n &= c_m \\\\ \end{align}\] について考えます。ここで、\( n \) と \( m \) は自然数ですが、両者は一致していなくても構いません。 \[ \begin{align} A = \left( \begin{array}{cccc} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{array} \right) , \ \tilde{A} = \left( \begin{array}{ccccc} a_{11} & a_{12} & \ldots & a_{1n} & c_1 \\ a_{21} & a_{22} & \ldots & a_{2n} & c_2 \\ \vdots & \vdots & & \vdots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} & c_m \end{array} \right) \end{align}\] とおき、\( A \) を上の連立一次方程式の係数行列、\( \tilde{A} \) を拡大係数行列と呼びます。 また、 \[ \begin{align} \boldsymbol x = \left( \begin{array}{c} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \end{array} \right) , \ \ \ \tilde{\boldsymbol x} = \left( \begin{array}{c} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \\ -1 \end{array} \right) , \ \ \ \boldsymbol c = \left( \begin{array}{c} c_{1} \\ c_{2} \\ \vdots \\ c_{m} \end{array} \right) \end{align}\] とおけば、上の連立一次方程式は次の \( \left( 1 \right) \) および \( \left( 1 ' \right) \) の形に書くことができます。 \[ \begin{align} A \boldsymbol x &= \boldsymbol c \ \ \ldots \left( 1 \right) \\\\ \tilde{A} \tilde{\boldsymbol x} &= O_{m,1} \ \ \ldots \left( 1 ' \right) \end{align}\]

　\( \left( 1 ' \right) \) の両辺に左から任意の \( m \) 次正則行列 \( P \) をかけると、次の \( \left( 1 '' \right) \) の形になります。 \[ \begin{align} P \tilde{A} \tilde{\boldsymbol x} &= O_{m,1} \ \ \ldots \left( 1 '' \right) \end{align}\] つまり、\( \left( 1 ' \right) \) の解は \( \left( 1 '' \right) \) の解と等しくなります。 そこで、\( \left( 1 ' \right) \) を解く代わりに、拡大係数行列 \( \tilde{A} \) に左基本変形をいくらか施した \( \left( 1 '' \right) \) を解いても構わないということになります。 また、拡大係数行列 \( \tilde{A} \) において、最後の列以外の列の交換は未知数の順序交換を意味しますが、この操作を行っても未知数の順序が変わる以外の変化は起こりません。 以上のことから、拡大係数行列 \( \tilde{A} \) に左基本変形と最後の列以外の列の交換を施した行列を利用すれば、\( \left( 1 ' \right) \) の解の公式が作れると考えられます。 そこで、まずは次の定理を証明します。

　まずは、\( \tilde{B} \) が \( \tilde{A} \) から得られたして、\( r \) が \( A \) の階数に等しいことを示します。 左基本変形は行についての操作であるため、\( \tilde{A} \) に左基本変形を施すと、\( \tilde{A} \) の一部分である \( A \) にも同じ左基本変形が施されます。 行列に基本変形を何回施しても、その行列の階数は変わらないため、\( \tilde{B} \) から最後の列を除いた \( \left( m , n \right) \) 型行列を \( B \) とすれば、 \( A \) の階数と \( B \) の階数は等しくなります。 \( B \) の第 \( r + j \) 列 \( \left( j = 1,2, \ldots , n-r \right) \) から第 \( k \) 列 \( \left( k = 1,2, \ldots , r \right) \) の \( b_{k,r+j} \) 倍を引けば、標準形 \( F_{m, \ n} \left( r \right) \) を得ます。 よって、\( B \) の階数は \( r \) となり、これは \( A \) の階数でもあるため、\( r \) は \( A \) の階数に等しいと言えます。

　続いて、\( \tilde{A} \) が \( \tilde{B} \) に変形できることを示します。
　まず、\( A=O \) の場合、変形なしで \( \tilde{A} = \tilde{B} \) となります。
　次に、\( A \neq O \) の場合、行の交換と第 \( n+1 \) 列以外の列の交換により、\( \left( 1,1 \right) \) 成分が 0 でないようにします。 それから、\( \left( 1,1 \right) \) をかなめとして左から第 1 列を掃出します。 この段階で、第 2 列から第 \( n \) 列までの第 2 行以下の成分がすべて 0 なら、これが \( \tilde{B} \ \left( r = 1 \right) \) となります。 そうでない場合、先ほど同様に \( \left( 2,2 \right) \) 成分を 1 にしてから、\( \left( 2,2 \right) \) をかなめとして左から第 2 列を掃出します。 この操作をできる限り続けると、\( m \) 回以下の操作で必ず \( \tilde{B} \) に到達します。 以上より、\( \tilde{A} \) は \( \tilde{B} \) に変形できることが示せました。

　方程式 \[ \begin{align} \tilde{B} \tilde{\boldsymbol x} &= O_{m,1} \ \ \ldots \left( 2 \right) \end{align}\] また、\( \left( 2 \right) \) を書き下した \[ \begin{align} \begin{array}{ccccccccc} x_1 & & & & + b_{1, \ r+1} \ x_{r+1} & + \ \ \ \ \cdots & + b_{1, \ n} \ x_n & = d_1 \\ & x_2 & & & + b_{2, \ r+1} \ x_{r+1} & + \ \ \ \ \cdots & + b_{2, \ n} \ x_n & = d_2 \\ & & \ddots & & \vdots & & \vdots & \vdots \\ & & & x_r & + b_{r, \ r+1} \ x_{r+1} & + \ \ \ \ \cdots & + b_{r, \ n} \ x_n & = d_r \\ & & & & & & 0 & \ \ \ = d_{r+1} \\ & & & & & & \vdots & \vdots \\ & & & & & & 0 & \ = d_m \end{array} \end{align}\] の解について考えます。\( d_{r+1} , \ldots , d_m \) のうちに 0 でないものがあるなら、\( \left( 2 \right) \) は解を持ちません。 \( d_{r+1} , \ldots , d_m \) がすべて 0 であるなら、\( x_{r+1} , \ldots , x_n \) に任意の数 \( \alpha _{r+1} , \ldots , \alpha _n \) を代入して、それらを左辺に移行すると、\( \left( 2 \right) \) は次の形になります。 \[ \begin{align} \left. \begin{array}{1} x_1 = d_1 - b_{1, \ r+1} \ \alpha _{r+1} - \cdots - b_{1, \ n} \ \alpha _n \\ x_2 = d_2 - b_{2, \ r+1} \ \alpha _{r+1} - \cdots - b_{2, \ n} \ \alpha _n \\ \cdots \cdots \cdots \cdots \\ x_r = d_r - b_{r, \ r+1} \ \alpha _{r+1} - \cdots - b_{r, \ n} \ \alpha _n \\ x_{r+1} = \alpha _{r+1} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \cdots \cdots \cdots \cdots \\ x_n = \alpha _n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \end{array} \right\} \ \ \ \ldots \left( 3 \right) \end{align}\] また、\( \left( 3 \right) \) を列ベクトルを用いて書くなら、 \[ \begin{align} \left( \begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_r \\ x_{r+1} \\ x_{r+2} \\ \vdots \\ x_n \end{array} \right) = \left( \begin{array}{c} d_1 \\ d_2 \\ \vdots \\ d_r \\ 0 \\ 0 \\ \vdots \\ 0 \end{array} \right) + \alpha _{r+1} \left( \begin{array}{c} - b_{1, \ r+1} \\ - b_{2, \ r+1} \\ \vdots \\ - b_{r, \ r+1} \\ 1 \\ 0 \\ \vdots \\ 0 \end{array} \right) + \alpha _{r+2} \left( \begin{array}{c} - b_{1, \ r+2} \\ - b_{2, \ r+2} \\ \vdots \\ - b_{r, \ r+2} \\ 0 \\ 1 \\ \vdots \\ 0 \end{array} \right) + \cdots + \alpha _n \left( \begin{array}{c} - b_{1, \ n} \\ - b_{2, \ n} \\ \vdots \\ - b_{r, \ n} \\ 0 \\ 0 \\ \vdots \\ 1 \end{array} \right) \\\\ \ldots \left( 3 ' \right) \end{align}\] となります。\( \left( 3 \right) \) および \( \left( 3 ' \right) \) は \( \left( 2 \right) \) の解を与える公式であり、未知数の順序を元に戻せば \( \left( 1 \right) \) の解を与える公式にもなります。

　\( \left( 3 \right) \) 式を応用すると、次の定理も証明できます。

　係数行列 \( A \) が正則の場合、\( A \) の階数は \( n \) に等しくなります。 すると、\( \left( 3 \right) \) 式において \( r = n \) が成り立つため、上の定理が成り立ちます。

　まず、\( A \) の階数と \( B \) の階数は等しく、\( \tilde{A} \) の階数と \( \tilde{B} \) の階数も等しいことから、 上の定理を証明するには、方程式 \( \left( 2 \right) \) が解を持つための必要十分条件が \( B \) の階数と \( \tilde{B} \) の階数との一致であることを示せばよいです。

　\( d_{r+1} , \ldots , d_m \) がすべて 0 であるなら、\( \tilde{B} \) の最後の列から第 \( j \) 列 \( \left( j = 1,2, \ldots ,r \right) \) の \( d_j \) 倍を引けば、最後の列の成分はすべて 0 になります。 すると、\( B \) を標準形 \( F_{m, \ n} \left( r \right) \) に変形した行列の最後の列に、成分がすべて 0 の列ベクトルを追加した行列は \( \tilde{B} \) を標準形に変形したものに等しくなります。 この標準形の階数は \( F_{m, \ n} \left( r \right) \) に等しいことから、\( B \) の階数と \( \tilde{B} \) の階数が等しいと言えます。

　一方、\( d_{r+1} , \ldots , d_m \) のうちに 0 でないものがある場合、 まずは、先ほど同様の操作により \( d_1, d_2, \ldots , d_r \) を 0 にします。 次に、\( \tilde{B} \) の一部分である \( B \) を標準形 \( F_{m, \ n} \left( r \right) \) に変形しておきます。 そのあと、\( d_{r+1} , \ldots , d_m \) のうちの 0 でない成分 \( d_i \) を 1 つ選び、\( \tilde{B} \) の第 \( i \) 行と第 \( r+1 \) 行を交換した後、 最後の列と第 \( r+1 \) 列を交換すれば、\( d_i \) を \( \left( r+1, r+1 \right) \) 成分に移すことができます。 そして、\( \left( r+1,r+1 \right) \) をかなめとして左から第 1 列を掃出します。 これにより、\( \tilde{B} \) は標準形 \( F_{m, \ n} \left( r+1 \right) \) に変形されるため、\( B \) の階数と \( \tilde{B} \) の階数が一致しないことが示されました。

　以上より、方程式 \( \left( 2 \right) \) が解を持つための必要十分条件、すなわち \( d_{r+1} , \ldots , d_m \) がすべて 0 であるという条件が、\( B \) の階数と \( \tilde{B} \) の階数との一致に等しいことが証明できました。

　右辺の定数項がすべて 0 であるような連立一次方程式を同次一次方程式系と呼びます。 \[ \begin{align} \left. \begin{array}{1} &a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = 0 \\\\ &a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n = 0 \\\\ &\ \ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\\\ &a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n = 0 \\\\ \end{array} \right\} \ \ \ \ldots \left( 4 \right) \end{align}\] また、 \[ \begin{align} A = \left( \begin{array}{cccc} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{array} \right) , \ \boldsymbol x = \left( \begin{array}{c} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \end{array} \right) \end{align}\] と置けば、\( \left( 4 \right) \) は \[ \begin{align} A \boldsymbol x &= O_{m,1} \ \ \ldots \left( 4 ' \right) \end{align}\] とも表せます。 同次一次方程式系 \( \left( 4 ' \right) \) は必ず \( \boldsymbol x = O_{m,1} \) を解に持ち、これを自明な解と呼びます。

　一般に、\( m \) 項列ベクトル \( \boldsymbol x_1 , \boldsymbol x_2 , \cdots , \boldsymbol x_n \) に対し、\( \beta _1 , \beta _2 , \cdots , \beta _n \) を任意定数として、 \[ \begin{align} \beta _1 \boldsymbol x_1 + \beta _2 \boldsymbol x_2 + \cdots + \beta _n \boldsymbol x_n \end{align}\] の形の列ベクトルを \( \boldsymbol x_1 , \boldsymbol x_2 , \cdots , \boldsymbol x_n \) の線形結合と呼びます。 もし、\( \boldsymbol x_1 , \boldsymbol x_2 , \cdots , \boldsymbol x_n \) が \( \left( 4 ' \right) \) の解ならば、それらの線形結合も \( \left( 4 ' \right) \) の解となります。 以上のことを踏まえて、\( \left( 3 ' \right) \) に戻ると、次の定理が得られます。

　まず、\( \left( 3 ' \right) \) の導出過程において、拡大係数行列 \( \tilde{A} \) から \( \tilde{B} \) を作りましたが、このとき最後の列には列の交換を行いません。 そのため、同次一次方程式系においては \( \tilde{B} \) の最後の列の成分はすべて \( 0 \) であるため、\( \left( 3 ' \right) \) にある \( d_1 , d_2 , \cdots , d_r \) はすべて 0 となります。 よって、\( \left( 3 ' \right) \) の第 1 項は無視できます。 第 2 項以降の列ベクトルを順番に \( \boldsymbol x_{r+1} , \boldsymbol x_{r+2} , \cdots , \boldsymbol x_n \) と置けば、 \( \left( 3 ' \right) \) の右辺はこれらの線形結合で表されることになるため、 \( \left( 4 ' \right) \) の任意の解は \( \boldsymbol x_{r+1} , \boldsymbol x_{r+2} , \cdots , \boldsymbol x_n \) の線形結合として表されると言えます。

　また、\( \alpha _{r+1} , \ldots , \alpha _n \) は任意定数であるため、\( \alpha _{r+1} = 1 \) とし、他の任意定数を 0 と置けば、\( \boldsymbol x_{r+1} \) は \( \left( 4 ' \right) \) の自明でない解となります。 同様の手順を踏むことで、\( \boldsymbol x_{r+1} , \boldsymbol x_{r+2} , \cdots , \boldsymbol x_n \) はいずれも \( \left( 4 ' \right) \) の自明でない解であることが示せます。

　それから、\( \boldsymbol x_i \ \left( i = r+1, r+2, \cdots , n \right) \) はいずれも \( \left( i , 1 \right) \) 成分が 1 であり、 \( i \neq I \) なる他の特別な自明でない解 \( \boldsymbol x_I \) はいずれも \( \left( i , 1 \right) \) 成分が 0 になっています。 これから、任意の \( i \ \left( i = r+1, r+2, \cdots , n \right) \) について、\( \boldsymbol x_i \) の \( \left( i , 1 \right) \) 成分は他の特別な自明でない解の線形結合として表すことができないとわかります。 ゆえに、\( \boldsymbol x_{r+1} , \boldsymbol x_{r+2} , \cdots , \boldsymbol x_n \) のいずれも、これらの内の他の \( n - r - 1 \) 個の列ベクトルの線形結合としては表されないと言えます。


　上の定理を応用すると、自明でない解の存在に関する次の定理が導かれます。

　[1] は係数行列 \( A \) の階数 \( r \) は \( m \) 以下となることから、\( r \leq m \lt n \) が成り立ちます。 よって、\( n - r \geq 1 \) となるため、先ほど証明した階数と同次一次方程式系の解についての定理より、\( \left( 4 ' \right) \) は少なくとも 1 つの自明でない解を持つと言えます。

　[2] では \( r \leq m = n \) が成り立ちます。 また、\( n = m \) より、係数行列 \( A \) は \( n \) 次正方行列であるため、もしこれが正則であるなら、\( r = n \) 、すなわち \( n - r = 0\) が成り立ち、\( \left( 4 ' \right) \) は自明でない解を持たないとわかります。

　[3] は [2] の対偶を取ったものです。

　それから、係数行列 \( A \) が正則であるという条件を、これと同値な行列式についての条件 \( |A| \neq 0 \) に置き換えると、[2] と [3] は次のようにも書けます。