1-3 行基本変形とGauss消去法
読み始める前の問い
消去で式を書き換えてよいのはなぜか。また、答えが何個あるかを途中で予測できるだろうか。
このページでできるようになること
Gauss消去を解集合を保つ操作として実行し、主変数と自由変数を読み取れるようになる。
前のページでは、連立一次方程式の解集合が「一つの解＋斉次方程式の解」になることを示しました。しかし、未知数が増えると代入法では式の管理が難しくなります。このページでは、方程式の意味を変えない操作だけを組み合わせ、解の存在と自由度を同時に読み取ります。
係数だけを記録する
次の方程式を考えます。
$$
\begin{cases}
x+y+z=6,\\
2x-y+z=3,\\
x+2y-z=2.
\end{cases}
$$
係数と定数項を並べると、拡大係数行列
$$
\left(
\begin{array}{ccc|c}
1&1&1&6\\
2&-1&1&3\\
1&2&-1&2
\end{array}
\right)
$$
になります。縦線の左が係数、右が定数項で、各行が一つの方程式を表します。
解集合を変えない三つの操作
行列に対する次の三操作を行基本変形という。
- 二つの行を交換する。
- 一つの行を零でない数倍する。
- 一つの行に、別の行の定数倍を加える。
行列 $A$ から有限回の行基本変形によって行列 $B$ が得られるとき、$A$ と $B$ は行同値であるといい $A\sim_{\mathrm{row}}B$ と書く。
行同値は同値関係です。何もしなければ反射律、一連の操作を逆順に戻せば対称律、二つの操作列を続ければ推移律が成り立ちます。
証明を読む前の見取り図
三つの行操作が可逆であることを確認し、各段階で元の系と新しい系が同値であることをつなぐ。
拡大係数行列に一回の行基本変形を施して得られる連立一次方程式は、元の連立一次方程式と同じ解集合をもつ。
各行を等式とみなす。
第一の操作は方程式を並べ替えるだけである。すべての方程式を同時に満たすという条件は、書く順序に依存しない。
第二の操作を考える。等式 $L=r$ を零でない数 $c$ 倍すると $cL=cr$ になる。$L=r$ なら両辺を $c$ 倍して $cL=cr$ を得る。逆に $cL=cr$ なら、$c\ne0$ なので両辺を $c$ で割って $L=r$ を得る。したがって二つの等式は同値である。零倍を許さないのは、$0=0$ から元の等式を回復できないためである。
第三の操作を考える。二つの等式を
$$
L_i=r_i,
\qquad L_j=r_j
$$
とし、第 $i$ 行を
$$
L_i+cL_j=r_i+cr_j
$$
で置き換える。元の二式を満たすなら、新しい第 $i$ 式も満たす。逆に、新しい第 $i$ 式と変更していない第 $j$ 式を満たすなら、前者から後者の $c$ 倍を引いて $L_i=r_i$ を回復できる。
各操作の前後で解集合が一致するので、有限回組み合わせても解集合は変わらない。
Gauss消去法を途中式まで実行する
Gauss消去法は次の有限手順です。
- 未処理部分が零なら停止する。
- 未処理部分の最も左にある非零列を探す。
- その列の非零成分をもつ行を未処理部分の最上段へ移す。
- その成分を主成分として、下の成分を行基本変形で零にする。
- 主成分の行と、その列までを処理済みとして右下部分へ進む。
各回で処理済みの行が一つ増えます。行は有限本しかないため、遅くとも $m$ 回で停止します。後退代入まで含めて主成分を1にし、その上も零にすれば簡約行階段形になります。
最初の行列に
$$ R_2\leftarrow R_2-2R_1, \qquad R_3\leftarrow R_3-R_1 $$
を施します。
$$ \left( \begin{array}{ccc|c} 1&1&1&6\\ 2&-1&1&3\\ 1&2&-1&2 \end{array} \right) \longrightarrow \left( \begin{array}{ccc|c} 1&1&1&6\\ 0&-3&-1&-9\\ 0&1&-2&-4 \end{array} \right). $$
続いて
$$ R_3\leftarrow R_3+\frac{1}{3}R_2 $$
とすると
$$ \left( \begin{array}{ccc|c} 1&1&1&6\\ 0&-3&-1&-9\\ 0&0&-\frac{7}{3}&-7 \end{array} \right) $$
を得ます。最下行から
$$ -\frac{7}{3}z=-7, \qquad z=3. $$
第二行へ戻して
$$ -3y-z=-9, \qquad -3y-3=-9, \qquad y=2. $$
第一行へ戻して
$$ x+y+z=6, \qquad x+2+3=6, \qquad x=1. $$
したがって $(x,y,z)=(1,2,3)$ です。元の三式へ代入すると左辺は順に $6,3,2$ となり、検算も完了します。
主変数と自由変数
階段状に変形した行列で、各非零行の最初の非零成分を主成分と呼びます。主成分を含む列に対応する未知数が主変数、それ以外が自由変数です。
$$
\left(
\begin{array}{ccc|c}
1&2&-1&4\\
0&1&3&2\\
0&0&0&0
\end{array}
\right)
$$
では、主変数は $x,y$、自由変数は $z$ です。$z=t$ と置くと、第二行から
$$
y+3t=2,
\qquad y=2-3t.
$$
第一行から
$$
x+2(2-3t)-t=4,
\qquad x=7t.
$$
よって
$$
\begin{pmatrix}x\\y\\z\end{pmatrix}
=
\begin{pmatrix}0\\2\\0\end{pmatrix}
+t\begin{pmatrix}7\\-3\\1\end{pmatrix}.
$$
自由変数一個が、解集合の一つの自由な方向に対応しています。
階数と解の存在
行列を行基本変形で階段形にしたときの非零行の個数、すなわち主成分の個数を階数と呼び、$\operatorname{rank}A$ と書く。
階段形の作り方によらずこの個数が同じになることは、後に像の次元として説明します。
証明を読む前の見取り図
三つの行操作が可逆であることを確認し、各段階で元の系と新しい系が同値であることをつなぐ。
$A$ を $m\times n$ 行列、$\boldsymbol{b}\in\mathbb{R}^m$ とする。方程式 $A\boldsymbol{x}=\boldsymbol{b}$ が解をもつための必要十分条件は
$$
\operatorname{rank}A
=
\operatorname{rank}(A\mid\boldsymbol{b})
$$
である。
拡大係数行列 $(A\mid\boldsymbol{b})$ を行基本変形で階段形にする。行基本変形は解集合を変えないので、変形後の方程式が解をもつかどうかを調べればよい。
係数部分がすべて零で、定数項だけが非零である行が現れたとする。その行は
$$
0x_1+\cdots+0x_n=c,
\qquad c\ne0,
$$
すなわち $0=c$ を要求する。この等式を満たす数は存在しないので、方程式全体にも解はない。この行は係数行列 $A$ には主成分を増やさないが、拡大係数行列では最後の列に主成分を一つ増やす。したがって
$$
\operatorname{rank}A
<
\operatorname{rank}(A\mid\boldsymbol{b}).
$$
逆に、そのような矛盾行がないとする。自由変数へ任意の値を与える。階段形では、最下段の非零行から順に、その行の主変数の係数が非零であるため、主変数を一意に決められる。同じ操作を一行ずつ上へ進めれば、すべての主変数が決まり、解が得られる。
矛盾行がないことは、最後の列にだけ新しい主成分が現れないことと同値である。したがって、解が存在することと二つの階数が等しいことは同値である。
多項式補間も同じ消去法で解ける
二次以下の多項式 $p(t)=a+bt+ct^2$ が
$$
p(0)=1,
\qquad p(1)=2,
\qquad p(2)=5
$$
を満たすとします。係数について
$$
\begin{pmatrix}
1&0&0\\
1&1&1\\
1&2&4
\end{pmatrix}
\begin{pmatrix}a\\b\\c\end{pmatrix}
=
\begin{pmatrix}1\\2\\5\end{pmatrix}
$$
です。第一行から $a=1$。第二行と第三行から第一行を引くと
$$
\begin{cases}
b+c=1,\\
2b+4c=4.
\end{cases}
$$
第二式から第一式の二倍を引いて $2c=2$、よって $c=1$、$b=0$ です。したがって
$$
p(t)=1+t^2.
$$
消去法は、未知数が座標のときだけでなく、多項式の係数を決める問題にもそのまま使えます。
適用できない境界
方程式 $x^2-y=0$ は、係数を行列に並べてGauss消去することができない。$x^2$ は未知数 $x$ の定数倍ではなく、入力の加法と両立しないからである。
実際、$(x_1+x_2)^2$ は一般に $x_1^2+x_2^2$ と等しくない。Gauss消去法が機能する理由は、各式が未知数の一次結合になっていることである。
魔法の窓：Lights Outを方程式として解く
三つのライトが横一列に並び、各ボタンを押すとその場所と隣のライトが反転するとする。消灯を $0$、点灯を $1$ とし、二度反転すると元へ戻るので、足し算は $2$ で割った余りで行う。
ボタンを押すかどうかを $x=(x_1,x_2,x_3)^{\mathsf T}$、最初の点灯状態を $b$ とすると、全消灯させる条件は
$$
\begin{pmatrix}
1&1&0\\
1&1&1\\
0&1&1
\end{pmatrix}x=b
\qquad(\text{成分は }0,1)
$$
である。例えば $b=(1,0,1)^{\mathsf T}$ なら、拡大係数行列を $2$ を法として消去することで、押すべきボタンを決められる。
この例では「パズルを試行錯誤すること」が「有限体 $\mathbb{F}_2$ 上の連立方程式を解くこと」に変わった。解がない盤面は階数の不一致で、複数の解法がある場合は斉次方程式の非零解で説明できる。数の種類を替えても、Gauss消去法の論理は変わらない。
演習と解答
次の連立方程式を解き、解が一点・空集合・無限集合のどれか判定せよ。
$$
x+y+z=2,\qquad 2x+2y+2z=4,\qquad x-y=0.
$$
第2式から第1式の2倍を引くと $0=0$ となる。第3式から $x=y$、これを第1式へ入れて $2x+z=2$。$x=t$ と置けば
$$
(x,y,z)=(t,t,2-2t)=(0,0,2)+t(1,1,-2).
$$
$t$ は任意なので解は直線をなし、無限個ある。
次の方程式系をGauss消去し、どの行が解の不存在を示すか明記せよ。
$$
\begin{cases}
x+2y-z=1,\\
2x+4y-2z=3,\\
x-y+z=0.
\end{cases}
$$
拡大係数行列で $R_2\leftarrow R_2-2R_1$ を行うと
$$
\left(
\begin{array}{ccc|c}
1&2&-1&1\\
0&0&0&1\\
1&-1&1&0
\end{array}
\right)
$$
となる。第二行は $0x+0y+0z=1$、すなわち $0=1$ を要求する。これはどの $x,y,z$ も満たさないため、方程式系は解をもたない。
$\mathbb{F}_2$ 上で
$$
\begin{cases}
x+y=1,\\
y+z=0,\\
x+z=1
\end{cases}
$$
を解き、解が何個あるか求めよ。
第一式から $x=1+y$、第二式から $z=y$ である。第三式へ代入すると
$$
x+z=(1+y)+y=1+(y+y)=1+0=1
$$
となり、第三式は自動的に満たされる。$y$ は0または1を自由に取れる。
$y=0$ なら $(x,y,z)=(1,0,0)$、$y=1$ なら $(x,y,z)=(0,1,1)$ である。したがって解は2個である。
次の抽象化
消去法で階段形までは得られましたが、手順の選び方によらない標準形があるかはまだ分かりません。次のページでは簡約階段形を定義し、その存在と一意性を証明します。
このページで回収したもの
当てずっぽうの代入が標準手順になった。補間やLights Outも同じ消去法で解ける。
次へ持ち越す問い
この見方を、次のページではより広い対象またはより計算しやすい形へ移す。
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
