§D3.2連立一次方程式と行基本変形

証明.定義 2.1 (1)については同じ二つの行を入れ替える操作、定義 2.1 (2)については同じ行を$c^{-1}$倍する操作、定義 2.1 (3)については第$p$行に第$q$行の$-c$倍を加える操作が逆操作を与える。これらが同じ種類の行基本変形であり、それぞれの合成が$M$を与えることの成分による確認は演習とする（問題 5.2）。▨

証明.$\vec x \in \mathbb{R}^n$を$A\vec x = \vec b$の解とし、その第$j$成分を$x_j$と書く。仮定より、$1 \le i \le m$を満たすどの$i$についても$\sum_{j=1}^{n} a_{ij}x_j = b_i$が成り立つ。$A'$の$(i, j)$成分を$a'_{ij}$、$\vec b'$の第$i$成分を$b'_i$と書き、施した行基本変形の種類で分ける。

定義 2.1 (1)の場合、$[A' \mid \vec b']$の各行は$[A \mid \vec b]$の行を並べ替えたものであるから、$1 \le i \le m$を満たす各$i$に対して$\sum_{j=1}^{n} a'_{ij}x_j = b'_i$は$[A \mid \vec b]$のある行が与える等式であり、$\vec x$はそれを満たす。

定義 2.1 (2)の場合、第$p$行を$c$倍したとすると、$i \ne p$については$a'_{ij} = a_{ij}$かつ$b'_i = b_i$であるから等式は成り立つ。$i = p$については$a'_{pj} = c\,a_{pj}$かつ$b'_p = c\,b_p$であるから

が成り立つ。

定義 2.1 (3)の場合、第$p$行に第$q$行の$c$倍を加えたとすると、$i \ne p$については$a'_{ij} = a_{ij}$かつ$b'_i = b_i$であるから等式は成り立つ。$i = p$については$a'_{pj} = a_{pj} + c\,a_{qj}$かつ$b'_p = b_p + c\,b_q$であるから

が成り立つ。以上より、いずれの場合も$\vec x$は$A'\vec x = \vec b'$の解である。

逆の包含を示す。補題 2.2により、施した行基本変形には、$[A' \mid \vec b']$へ施すと$[A \mid \vec b]$を与える逆操作が存在する。すでに示したことを$[A' \mid \vec b']$とこの逆操作へ適用すれば、$A'\vec x = \vec b'$の解はすべて$A\vec x = \vec b$の解である。よって二つの解集合は一致する。

有限回の場合を、行基本変形の回数$k$についての帰納法で示す。$k = 0$のときは変形後の行列が$[A \mid \vec b]$自身であるから解集合は一致する。$k$回続けて得られる行列を$[A^{(k)} \mid \vec b^{(k)}]$と書き、$A\vec x = \vec b$の解集合と$A^{(k)}\vec x = \vec b^{(k)}$の解集合が一致すると仮定する。$k+1$回目の行基本変形について上で示したことを$[A^{(k)} \mid \vec b^{(k)}]$へ適用すると、$A^{(k)}\vec x = \vec b^{(k)}$の解集合と$A^{(k+1)}\vec x = \vec b^{(k+1)}$の解集合が一致する。よって$A\vec x = \vec b$の解集合と$A^{(k+1)}\vec x = \vec b^{(k+1)}$の解集合が一致する。▨

証明. はじめに、行基本変形の定義から従う二つの事実を述べる。第一に、三種類の操作はいずれも各列に同じ仕方で作用するので、$M$の第$s$列から第$n$列までを取り出して並べた行列へ同じ行基本変形を施した結果は、変形後の$M$の第$s$列から第$n$列までを取り出して並べた行列に等しい。とくに、すべての成分が$0$である列は、どの行基本変形によってもすべての成分が$0$である列へ移る。第二に、第$2$行から第$m$行までだけに関わる行基本変形は、それらの行を取り出して並べた行列に対する同じ種類の行基本変形に対応し、第$1$行を変えない。

列の個数$n$についての帰納法で示す。

$n = 1$とする。$M$のすべての成分が$0$であれば零行でない行が存在せず、$r = 0$として四条件はいずれも空虚に成り立つので、$M$は簡約階段形である。そうでない場合、$m_{p1} \ne 0$を満たす$p$を取り、$p \ne 1$ならば第$1$行と第$p$行を入れ替え、続いて第$1$行を$m_{p1}^{-1}$倍する。得られた行列の$(i, 1)$成分を$u_i$と書くと$u_1 = 1$であり、$2 \le i \le m$を満たす各$i$について第$i$行に第$1$行の$-u_i$倍を加えると、第$i$行の第$1$列の成分は$u_i - u_i = 0$となる。これらの操作は第$1$行を変えないので、得られる行列は第$1$成分が$1$、他の成分が$0$である$1$列だけからなり、$r = 1$として四条件を満たす。

$n \ge 2$とし、列の個数が$n-1$である任意の実行列について主張が成り立つと仮定する。$M$を実$m \times n$行列とし、$M$の第$1$列に$0$でない成分があるかどうかで分ける。

$M$の第$1$列のすべての成分が$0$であるとする。$M$の第$2$列から第$n$列までを取り出して並べた$m \times (n-1)$行列を$N$とすると、帰納法の仮定より、有限回の行基本変形で$N$を簡約階段形$N'$へ変形することができる。同じ行基本変形を$M$へ施して得られる行列を$M'$とすると、第一の事実より$M'$の第$1$列のすべての成分は$0$であり、$M'$の第$2$列から第$n$列までを取り出して並べた行列は$N'$である。したがって$M'$の第$i$行が零行であることと$N'$の第$i$行が零行であることは同値であり、零行でない第$i$行の主成分の列番号は、$N'$における列番号に$1$を加えたものである。$N'$が四条件を満たすことから$M'$も四条件を満たすので、$M'$は簡約階段形である。

$M$の第$1$列に$0$でない成分があるとする。$n = 1$の場合と同じ操作を施して、第$1$列が第$1$成分だけ$1$で他の成分が$0$である行列$M_1$を得る。$m = 1$ならば、$M_1$は零行でない行を第$1$行だけもち、その主成分は第$1$列の$1$であって第$1$列に他の成分はないので、$M_1$は簡約階段形である。以下$m \ge 2$とする。$M_1$の第$2$行から第$m$行まで、かつ第$2$列から第$n$列までを取り出して並べた$(m-1) \times (n-1)$行列を$N$とすると、帰納法の仮定より、有限回の行基本変形で$N$を簡約階段形$N'$へ変形することができる。第二の事実により、対応する行基本変形を$M_1$の第$2$行から第$m$行へ施すことができ、その結果を$M_2$と書く。これらの操作は第$1$行を変えず、$M_1$の第$1$列の第$2$成分から第$m$成分までがすべて$0$であることから、$M_2$の第$1$列は$M_1$の第$1$列に等しい。また第一と第二の事実より、$M_2$の第$2$行から第$m$行まで、かつ第$2$列から第$n$列までを取り出して並べた行列は$N'$である。

$N'$の零行でない行の個数を$s$とし、$N'$の第$k$行（$1 \le k \le s$）の主成分の列番号を$l_k$とする。$M_2$の第$1$行は第$1$列に$1$をもつので零行でなく、$M_2$の第$k+1$行（$1 \le k \le m-1$）は第$1$列の成分が$0$であるから、その行が零行であることと$N'$の第$k$行が零行であることは同値である。よって$M_2$の零行でない行の個数は$s+1$であり、$M_2$は定義 3.1 条件 (a)を満たす。$M_2$の第$1$行の主成分の列番号は$1$であり、第$k+1$行（$1 \le k \le s$）の主成分の列番号は$l_k + 1 \ge 2$であって、$l_1 < \cdots < l_s$であるから、$M_2$は定義 3.1 条件 (b)を満たす。主成分はいずれも$1$であるから、$M_2$は定義 3.1 条件 (c)を満たす。

$M_2$の$(1, l_k+1)$成分を$w_k$と書き、$k = 1, \ldots, s$について順に、第$1$行に第$k+1$行の$-w_k$倍を加える。$N'$が定義 3.1 条件 (d)を満たすことから、$M_2$の第$l_k+1$列の成分は第$k+1$行が$1$、第$1$行以外の他の行が$0$であり、また$M_2$の第$k+1$行は第$1$列の成分が$0$、$k' \ne k$に対する第$l_{k'}+1$列の成分が$0$である。したがってこれらの操作は第$2$行から第$m$行までを変えず、第$1$列と第$l_{k'}+1$列（$k' \ne k$）の成分も変えず、第$l_k+1$列の第$1$成分を$w_k - w_k = 0$にする。得られる行列を$M_3$とすると、$M_3$の第$1$行は第$1$列に$1$をもつので零行でなく、主成分の列番号は$1$のままであるから、$M_3$は定義 3.1 条件 (a)、定義 3.1 条件 (b)、定義 3.1 条件 (c)を満たし、さらに主成分を含む各列は主成分以外の成分がすべて$0$であるから定義 3.1 条件 (d)を満たす。よって$M_3$は簡約階段形である。

以上により、列の個数が$n$の場合にも主張が成り立つ。▨

証明.命題 2.3により$A\vec x = \vec b$の解集合は$R\vec x = \vec d$の解集合に等しいので、以下では後者を調べる。$[R \mid \vec d]$は簡約階段形であるから、定義 3.1 条件 (a)より第$s+1$行から第$m$行までは零行であり、これらの行が与える等式は$0 = 0$であって、どの$\vec x \in \mathbb{R}^n$についても成り立つ。よって$\vec x$が$R\vec x = \vec d$の解であることは、$1 \le i \le s$を満たすどの$i$についても$\sum_{j=1}^{n} r_{ij}x_j = d_i$が成り立つことと同値である。また$P \subseteq \{1, \ldots, n+1\}$であるから、$n+1 \in P$、$n+1 \notin P$かつ$F = \emptyset$、$n+1 \notin P$かつ$F \ne \emptyset$のうちちょうど一つが起こる。

(1)を示す。$n+1 \in P$とすると、定義 3.1 条件 (b)より$j_s = n+1$である。第$s$行の主成分の列番号が$n+1$であることから、$1 \le j \le n$について$r_{sj} = 0$であり、定義 3.1 条件 (c)より$d_s = 1$である。よって第$s$行が与える等式は$0 = 1$であって、これを満たす$\vec x$は存在しない。したがって解集合は空集合である。

(2)を示す。$n+1 \notin P$かつ$F = \emptyset$とすると$P = \{1, \ldots, n\}$であり、$P$の元の個数は$s$であるから$s = n$である。$j_1 < \cdots < j_n$であることから$j_i = i$（$1 \le i \le n$）となる。定義 3.1 条件 (c)より$r_{ii} = 1$であり、第$i$列は第$i$行の主成分を含むので定義 3.1 条件 (d)より$i \ne i'$のとき$r_{i'i} = 0$である。よって第$i$行が与える等式は$x_i = d_i$であり、$R\vec x = \vec d$の解は、第$i$成分が$d_i$である$\mathbb{R}^n$の元ただ一つである。

(3)を示す。$n+1 \notin P$かつ$F \ne \emptyset$とし、$1 \le i \le s$を取る。定義 3.1 条件 (c)より$r_{i j_i} = 1$であり、$i' \ne i$を満たす$i'$について第$j_{i'}$列は第$i'$行の主成分を含むので定義 3.1 条件 (d)より$r_{i j_{i'}} = 0$である。また$j < j_i$を満たす$j$については、主成分の列番号が$j_i$であることから$r_{ij} = 0$である。よって第$i$行が与える等式は

と同値である。

$F$の各元$j$に対して実数$t_j$を与える。$\{1, \ldots, n\}$は$F$と$P$の交わらない和であるから、$j \in F$について第$j$成分が$t_j$であり、$1 \le i \le s$について第$j_i$成分が$d_i - \sum_{j \in F,\ j > j_i} r_{ij}t_j$である$\mathbb{R}^n$の元$\vec x$がただ一つ定まる。上で得た同値により、この$\vec x$は$1 \le i \le s$を満たすどの$i$についても第$i$行の等式を満たすので$R\vec x = \vec d$の解である。逆に、$R\vec x = \vec d$の解であって$j \in F$について第$j$成分が$t_j$であるものを取ると、同じ同値により第$j_i$成分は$d_i - \sum_{j \in F,\ j > j_i} r_{ij}t_j$に等しいので、いま定めた$\vec x$に一致する。よって条件を満たす解はただ一つである。

$F \ne \emptyset$であるから$j_0 \in F$を取ることができる。実数$t$に対して$t_{j_0} = t$、$j \in F \setminus \{j_0\}$について$t_j = 0$と与えると、相異なる$t$に対して第$j_0$成分が相異なる解が得られる。よって解集合は無限集合である。▨

証明.$A$を$R$へ移す行基本変形の列を$[A \mid \vec 0]$へ施して得られる行列を考える。行基本変形はすべての成分が$0$である列をすべての成分が$0$である列へ移し、また各列に同じ仕方で作用するので、得られる行列は$[R \mid \vec 0]$である。$[R \mid \vec 0]$の第$i$行が零行であることと$R$の第$i$行が零行であることは同値であり、零行でない行の主成分も両者で一致するから、$[R \mid \vec 0]$は簡約階段形であって、その主成分の列番号の集合$P$は$R$の主成分の列番号の集合に等しく、とくに$n+1 \notin P$である。

(1)$\Rightarrow$(2)を対偶で示す。$F := \{1, \ldots, n\} \setminus P \ne \emptyset$とし、$j_0 \in F$を取る。定理 4.1 (3)を$[R \mid \vec 0]$へ適用すると、第$j_0$成分が$1$、$j \in F \setminus \{j_0\}$について第$j$成分が$0$である$A\vec x = \vec 0$の解が存在する。この解は$\vec 0$と異なるので(1)は成り立たない。

(2)$\Rightarrow$(3)を示す。$P = \{1, \ldots, n\}$であるから、$R$の零行でない行の個数は$n$であり、$R$は$n$行しかもたないので、主成分の列番号を小さい順に$j_1 < \cdots < j_n$と並べると$j_i = i$（$1 \le i \le n$）となる。定義 3.1 条件 (c)より$R$の$(i, i)$成分は$1$であり、第$i$列は第$i$行の主成分を含むので定義 3.1 条件 (d)より$i \ne i'$のとき$(i', i)$成分は$0$である。§D3.1 定義 3.6の定める$I_n$と成分がすべて一致するので、§D3.1 定義 1.1により$R = I_n$である。

(3)$\Rightarrow$(1)を示す。$R = I_n$とすると、$1 \le j \le n$を満たす各$j$について第$j$行の主成分の列番号は$j$であるから$P = \{1, \ldots, n\}$であり、$F = \emptyset$かつ$n+1 \notin P$である。定理 4.1 (2)を$[R \mid \vec 0]$へ適用すると$A\vec x = \vec 0$の解はただ一つであり、$\vec 0$がその解であるから、解は$\vec 0$のみである。▨

証明. 取った簡約階段形を$[R \mid \vec d]$と書く。行基本変形はすべての成分が$0$である列をすべての成分が$0$である列へ移すので$\vec d = \vec 0$であり、第$n+1$列はどの行の主成分も含まない。よって主成分の列番号の集合$P$は$\{1, \ldots, n\}$に含まれ、その元の個数は$r$である。

$r < n$とすると$F = \{1, \ldots, n\} \setminus P$は空でない。$j_0 \in F$を取り、定理 4.1 (3)を適用すると、第$j_0$成分が$1$、$j \in F \setminus \{j_0\}$について第$j$成分が$0$である$A\vec x = \vec 0$の解が存在する。この解は$\vec 0$と異なるので非自明な解である。

$m < n$とする。$r$は$[R \mid \vec d]$の零行でない行の個数であり、行の個数$m$以下であるから$r \le m < n$が成り立つ。よってすでに示したことから$A\vec x = \vec 0$は非自明な解をもつ。▨