【線型代数学入門】連立一次方程式の解法

1. 記事の目的
以下の記事で、行列の基本変形と行列の階数について述べた。本記事ではこれらの概念を用いて、連立一次方程式の開放について解説する。

camelsan.hatenablog.com

2. 連立一次方程式
中学生の時に、未知変数二つに対して、方程式を２個用意すれば、未知変数を決定することができるということを習ったはずでる。ここではより一般的に $n$ 個の未知変数に対し、 $m$ 本の連立方程式を用意した時にいつ解が求められるのか、あるいはどうやって求められるのかを解説する。数学では非線形的な問題を線形的に近似して、連立方程式を解いて近似解を求めるというアプローチがしばしば取られる。こういった意味でも連立一次方程式の解法は重要となってくる。ここで、連立一次方程式とは次のようなものである。

$n$ 個の未知変数 $x_1,\dots,x_n$ に関する $m$ 個の一次方程式の組、

$\begin{split} &a_{11}x_1+a_{12}+\dots+a_{1n}x_n=c_1 \\ &a_{21}x_1+a_{22}+\dots+a_{2n}x_n=c_2 \\ &\vdots\\ &a_{m1}x_1+a_{m2}+\dots+a_{mn}x_n=c_m \\ \end{split} \tag{1}$

を連立一次方程式という。

連立方程式は常にただ一つの解を持つとは限らない。例えば、

$x_1+x_2=1$

は無数の解を持つ( $(x_1,x_2)=(a+1,-a)$ 、 $a$ は任意の実数は全て解)

また、連立一次方程式が解をもたない時もある。例えば、

$0\cdot x_1=1$

は解をもたない。

3. 拡大係数行列
連立一次方程式(1)を考える。係数 $a_{ij}$ を並べた行列

$A= \begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots &&\vdots \\ a_{m1} & a_{m2} & \dots & a_{mn} \\ \end{pmatrix}$

を(1)の係数行列という。また $A$ の右端に $c_i$ を付け加えた行列

$\hat{A}= \begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n} & c_1 \\ a_{21} & a_{22} & \dots & a_{2n} & c_2 \\ \vdots & \vdots &&\vdots &\vdots\\ a_{m1} & a_{m2} & \dots & a_{mn} & c_m \\ \end{pmatrix}$

を(1)の拡大係数行列という。また、

$\bf{x}= \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}, \hat{\bf{x}}= \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \\ -1 \end{pmatrix}, \bf{c}= \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_m \end{pmatrix}$

とすると、(1)を次の(2)と(3)の形に書くことができる。

$A\bf{x}=\bf{c} \tag{2}$

$\hat{A}\hat{\bf{x}}=0 \tag{3}$

4. 拡大係数行列に関する定理
任意の $m$ 次正方行列 $P$ に対し、(3)は、

$P\hat{A}\hat{\bf{x}}=0 \tag{4}$

と同じである。これは(3)と(4)の解が全く同じであることを示す。また、(4)は、 $\hat{\bf{A}}$ に左基本変形を施しても、その結果得られる新しい方程式は、元の方程式(3)と同じことを意味する。即ち、 $\hat{A}$ を左基本変形で、簡単な形にすることで、連立一次方程式の解を求めることができることを示す。また、足し算の順序を変えることで、変数の順序を変えることができる。これは、拡大係数行列の最終列以外の順番を任意に変えることができることを示す。まとめると

左基本変形
最終列以外の順番を変える

操作のみで、拡大係数行列をなるべく簡単な形にして、連立方程式を解く方法が考えられるのではないかというアプローチが考えられる。

上記の２点の変形で拡大係数行列は、次の定理に示す形まで変形することができる。

定理
拡大係数行列 $\hat{A}$ に、左基本変形及び、最後の列以外の列の交換を何回か行うことで、[tex\hat{A}]は図１の[tex\hat{B}]に変形することができる。

f:id:camelsan:20210227113303p:plain — 図１拡大係数行列の変形後

ただし、 $r$ は係数行列 $A$ の階数である。
証明： $A=0$ ならば

$\hat{A}= \begin{pmatrix} 0 & \dots & 0 & c_1 \\ \vdots &&\vdots&\vdots \\ 0 & \dots & 0 & c_m \\ \end{pmatrix}$

より、 $\hat{B}$ の $r=0$ の場合である。 $A\neq 0$ ならば、行の変換もしくは、 $n+1$ 列以外の交換によって、 $(1,1)$ 成分が $0$ でないようにすることができる。そこで、 $(1,1)$ をかなめとして第１列を掃き出す。掃き出しに関しては以下の記事を参照。

camelsan.hatenablog.com

ここで、第２列から第 $n$ 列までの第２行以下が $0$ ならば、これが求める形である( $r=1$ の場合)。第２列と第 $n$ 列の間に $0$ でないものがあれば、 $(2,2)$ 成分を1にし、第２列の $(2,2)$ 成分以外を全て0にすることができる。この操作を可能な限り続けることで、ある $r$ に対して、 $\hat{B}$ の形になる。

次に、 $r$ が $A$ の階数に等しいことを証明する。次のことに注意する。 $\hat{A}$ に施した基本変形により、 $\hat{A}$ の１部分である $A$ にも同じ基本変形が施される。従って、 $\hat{B}$ から最後の列を取り除いた $(m,n)$ 型行列を $B$ とすると、 $A$ の階数と、 $B$ の階数とは次の記事の定理により等しい( $B$ は $A$ に基本変形を施されて得られている。即ちある正則行列 $P$ に対して

$B=PA$

一方、Bの階数を $r_B$ とすると、基本行列 $P^{\prime}$ 、 $Q^{\prime}$ を用いて、

$P^{\prime}BQ^{\prime}=F(r_B)$

よって、

$P^{\prime}PAQ^{\prime}=F(r_B)$

行列の階数は変形対象の行列のみで決定されるので、 $r_B$ は $A$ の回数でもある。従って、 $A$ と $B$ の階数は等しい。 )。

camelsan.hatenablog.com

$B$ の第 $r+j$ 列 $(j=1,2,\dots,n-r)$ から、第 $k$ 列 $(k=1,2,\dots,r)$ の $b_{k,r+j}$ 倍を引けば、標準形 $F_{m,n}(r)$ を得る。 $B$ の階数は $r$ となり、また $B$ の階数と $A$ の階数は等しいので、 $r$ は $A$ の階数と等しい。

5. 連立一次方程式の解法
従って、上記の定理から(3)は、

$\hat{B}\hat{\bf{x}}=0$

の形になる。これは、

$\begin{split} & x_1 + b_{1,r+1}x_{r+1}+\dots+b_{1,n}x_n=d_1 \\ & x_2 + b_{2,r+1}x_{r+1}+\dots+b_{2,n}x_n=d_2 \\ & \vdots \\ & x_r + b_{r,r+1}x_{r+1}+\dots+b_{r,n}x_n=d_r \\ &0=d_{r+1} \\ &\vdots \\ &0=d_{m} \\ \end{split}$

の形になる。ここで、 $d_{r+1}, d_{r+2}, \dots, d_m$ の中に $0$ でないものがあれば、(2)は解をもたない。 $d_{r+1}=d_{r+2}=\dots =d_m=0$ の時は $x_{r+1}, x_{r+2}, \dots, x_m$ に任意の数、 $\alpha_{r+1}, \alpha_{r+2}, \dots, \alpha_m$ を代入し、その部分を移行すると、次の形になる。

$\begin{split} &x_1 = d_1-b_{1,r+1}\alpha_{r+1}-\dots -b_{1,n}\alpha_n \\ &x_2 = d_2-b_{2,r+1}\alpha_{r+1}-\dots -b_{2,n}\alpha_n \\ & \vdots\\ &x_r = d_r-b_{r,r+1}\alpha_{r+1}-\dots -b_{r,n}\alpha_n \\ &x_{r+1}=\alpha_{r+1}\\ &\vdots\\ &x_{n}=\alpha_{n}\\ \end{split} \tag{5}$

従って、次の定理が得られる。

定理5.1
方程式(1)は、拡大係数行列 $\hat{A}$ に、左基本変形及、最終右列以外の列の変換を施して $\hat{B}$ に変形した時、 $d_{r+1}=d_{r+2}=\dots=d_m=0$ の時に限って解を持つ。その時の解は、 $x_{r+1},x_{r+2},\dots,x_n$ に、 $n-r$ 個の任意定数 $\alpha_{r+1},\alpha_{r+2},\dots,\alpha_n$ を代入し、(4)によって、 $x_1,x_2,\dots,x_r$ を定めることによって得られる。ただし、未知数の順序は、列の交換に対応して入れ替わっている。

6. 例
次の連立一次方程式を解く。

$\begin{split} &3x_2+3x_3-2x_4=-4 \\ &x_1+x_2+2x_3+3x_4=2 \\ &x_1+2x_2+3x_3+2x_4=1 \\ &x_1+3x_2+4x_3+2x_4=-1 \\ \end{split}$

拡大係数行列 $\hat{A}$ は次のように変形される。

$\begin{split} \hat{A}&= \begin{pmatrix} 0&3&3&-2&-4\\ 1&1&2&3&2\\ 1&2&3&2&1\\ 1&3&4&2&-1 \end{pmatrix} \\ &\rightarrow^{(1)} \begin{pmatrix} 1&1&2&3&2\\ 0&3&3&-2&-4\\ 1&2&3&2&1\\ 1&3&4&2&-1 \end{pmatrix} (\text{第１行と第２行を入れ替える})\\ &\rightarrow^{(2)} \begin{pmatrix} 1&1&2&3&2\\ 0&3&3&-2&-4\\ 0&1&1&-1&-1\\ 0&2&2&-1&-3 \end{pmatrix} (\text{第１列を掃き出す})\\ &\rightarrow^{(3)} \begin{pmatrix} 1&1&2&3&2\\ 0&1&1&-1&-1\\ 0&3&3&-2&-4\\ 0&2&2&-1&-3 \end{pmatrix} (\text{第２行と第３行を入れ替える})\\ &\rightarrow^{(4)} \begin{pmatrix} 1&0&1&4&3\\ 0&1&1&-1&-1\\ 0&0&0&1&-1\\ 0&0&0&1&-1 \end{pmatrix} (\text{第２列を掃き出す})\\ &\rightarrow^{(5)} \begin{pmatrix} 1&0&4&1&3\\ 0&1&-1&1&-1\\ 0&0&1&0&-1\\ 0&0&1&0&-1 \end{pmatrix} (\text{第３列と第４列を交換する})\\ &\rightarrow^{(6)} \begin{pmatrix} 1&0&0&1&7\\ 0&1&0&1&-2\\ 0&0&1&0&-1\\ 0&0&0&0&0 \end{pmatrix} (\text{第３列を掃き出す})\\ \end{split}$

第４行が0からなるので、解は存在し、 $4-3=1$ 個の任意定数を含む。(5)の操作で、第３列と第４列を交換したので、

$\begin{split} &x_1+x_3=7\\ &x_2+x_3=-2\\ &x_4=-1 \end{split}$

従って、解は $x_3=\alpha$ として、

$x_1=7-\alpha, x_2=-\alpha -2, x_4=-4, x_3=\alpha$

となる。

7. 斉次一次方程式
式(2)で、 $\boldsymbol{c}=\boldsymbol{0}$ であるような一次方程式を、斉次一次方程式という。斉次一次方程式に関し、次の定理が成り立つ。

定理7.1
$A$ が $(m,n)$ 型行列、 $\boldsymbol{x}\in\mathbb{R}^n$ とする。
$n>m$ ならば、斉次一次方程式

$A\boldsymbol{x}=\boldsymbol{0}$

は少なくとも1つの自明でない解( $\boldsymbol{x}=\boldsymbol{0}$ 以外の解)を持つ。

定理7.1は、ベクトル空間の次元の定義において重要になる。次の定理7.2を使って証明される。

定理7.2
$n$ 個の未知数に関する $m$ 個の斉次一次方程式

$A\boldsymbol{x}=\boldsymbol{0}\tag{6}$

において、係数行列 $A$ の階数が $r$ ならば、(6)は $n-r$ 個の自明でない解 $\boldsymbol{x}_{r+1},\boldsymbol{x}_{r+2},\dots,\boldsymbol{x}_n$ を持ち、任意の解はこれらの線型結合として表される。また、 $\boldsymbol{x}_{r+1},\boldsymbol{x}_{r+2},\dots,\boldsymbol{x}_n$ のどの１つもほかの $n-r-1$ 個のベクトルの線型結合として表されない。
証明：式(5)において、 $d_1=d_2=\dots =d_r=0$ である。従って、斉次一次方程式(6)は、式(5)の係数の記号を用いて、

$\boldsymbol{x}_{r+1}= \begin{pmatrix} -b_{1,r+1} \\ -b_{2,r+1} \\ \vdots \\ -b_{r,r+1} \\ 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}, \boldsymbol{x}_{r+2}= \begin{pmatrix} -b_{1,r+2} \\ -b_{2,r+2} \\ \vdots \\ -b_{r,r+2} \\ 0 \\ 1 \\ \vdots \\ 0 \end{pmatrix}, \dots, \boldsymbol{x}_{n}= \begin{pmatrix} -b_{1,n} \\ -b_{2,n} \\ \vdots \\ -b_{r,n} \\ 0 \\ 0 \\ \vdots \\ 1 \end{pmatrix}$

という、 $n-r$ 個の解を持ち、そのほかの解はこれらの線型結合として表すことができる。また、 $\boldsymbol{x}_{r+1},\boldsymbol{x}_{r+2},\dots,\boldsymbol{x}_n$ の第 $r+1$ 成分以降の形から、 $\boldsymbol{x}_{r+1},\boldsymbol{x}_{r+2},\dots,\boldsymbol{x}_n$ のどの一つも、ほかの $n-r-1$ 個の元で表すことができない。