線形代数 – 行基本変形・行簡約化 | 試験に出ない科学の話

本ページでは行基本変形の定義、基本的な性質、それらに関連する定義などについて述べます。

定義1

以下$3$つの操作を行基本変形（elementary row operation）という。

$ 1\ $2つの行を入れ替える

$ 2\ $ある行を定数倍する

$ 3\ $ある行を定数倍し別の行に加える

定義2

行基本変形によって以下のような行列に変形することを行簡約化（row reduction）、この形式を行簡約階段形（reduced row echelon form）、このような行列を行簡約階段行列とよぶ。

・各行の最も左にある$0$以外の成分は$1$　※これを主成分（leading entry）またはピボット（pivot）という。

・第$2$行以下に主成分がある場合、主成分は上の行の主成分より右にある

・全て$0$の行がある場合、その行は主成分がある行より下にある

・主成分のある列は主成分以外の成分は全て$0$

*は任意の値

例

以下は行簡約階段形の行列です。

単位行列も行簡約階段形です。

以下は行簡約階段形ではありません。

・最も左の$0$以外の成分が$1$ではない行がある

・ある主成分の下の行かつ左の列に$0$以外の成分がある

・主成分がある列に$0$以外の成分がある

・全て$0$の行が、主成分のある行より上にある

定義3

行基本変形によって$A$から$B$が得られる場合、$A$と$B$は行同値である（row equivalent）という。

定理1

全ての行列は有限回の行基本変形によって行簡約化することができる。

以下の手順のように、どのような行列であっても行簡約化することが可能であることが明らかです。ただし、行簡約化する方法は$1$通りとは限りません。異なる行基本変形によって行簡約化することができる場合もあります。

*は任意の数字です。

第$1$行の定数倍を第$2$行に加えることにより第$2$行$1$列を$0$にする。

同様にして第$1$列の第$3$行以降を$0$にする。

第$1$行を定数倍して$1$にする。

同様に第$2$列も$0$に変える。ただし定数倍の元となるのは第$1$行ではなく第$2$行の成分。

もし定数倍の元となるはずであった成分が$0$であった場合は下の$0$ではない行と入れ替え、同じように演算を続ける。

もし下の全ての成分が$0$であった場合はその列に関しては何も行わない（その成分より上の成分は初期の状態のまま残る）。

全ての列に対して同様に行う。

定理2

ある行列に対する行基本変形によって行簡約化できる行列は$1$つしか存在しない。

$1$つの行列が行簡約化できる行基本変形の組み合わせは$1$通りとは限りませんが、異なる行基本変形によってそれぞれが行簡約化できたとしたら、それらは同じ行列です。

証明

$m\times n$の行列$A$に対し別々の行基本変形を行い、$B$と$C$の異なる行列に行簡約化されたとする。

数学的帰納法を使用し$B=C$であることを証明する。

$m\times 1$の行列の場合は明らかに、どのように変形しても行簡約階段形は$1$種類しか存在せず、$B=C$となる。

次に$m \times n$の行列を考える。$B$と$C$の第$1$列から第$n-1$列は等しく、異なるのは第$n$列のみと仮定する。

$\boldsymbol{x}$を$n$個の成分からなるベクトルとし、以下の解を考える。

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

行基本変形によって得られた行列の解は変わらないので、

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

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

の解は同じである。したがって以下の解も同じである。

$$(B-C)\boldsymbol{x}=\boldsymbol{0}$$

$B$と$C$の第$n-1$列までは同一と仮定したので、$B-C$の第$n-1$列までの成分は$0$であり、第$n$列のみが、この時点では任意となる。

$B$と$C$の$i$行目の成分$b_i$、$c_i$が異なっていたとする。

$(b_i-c_i)x_n=0$より、$x_n=0$でなければならない。

$B\boldsymbol{x}=\boldsymbol{0}$が成立するためには第$n-1$列までが$0$で、第$n$列が$1$の行がなければならない。この$1$は主成分となり、第$n$列の他の成分は全て$0$でなければならない。

$C$も同様なので仮定の$B \neq C$に反する。したがって、$m \times n$の行列においても$B=C$となる。数学的帰納法により全ての大きさの行列について$B=C$が成立する。

■

補足

※証明の中で、「行基本変形によって得られた行列の解は変わらない」と述べましたが、後述「定理4」を参照ください。

さて、$m \times 1$の行列の場合、明らかに行簡約階段形は$1$つしか存在しかないので$B=C$であることがわかります。

次に$m \times n$の行列の場合です。

$B$と$C$を以下とします。

$B-C$は以下のように第$n$列のみ値が$0$であることが確定していません。

$B$と$C$では第$i$行$n$列の成分が異なるとします。

$(B-C)\boldsymbol{x}$は次のようになります。

この関係が成立するためには$x_n=0$である必要があります。

$B\boldsymbol{x}=0$においても同じ解になるので、$B$の第$1$列から第$n-1$列までが$0$で第$n$列が$1$の行があるはずです。

上記はややこしいので簡略化し$B$は$4\times 4$の行列であるとして考えましょう。

$B$と$C$では第$2$行の最も右の列の成分が異なるとします。下の式は$B$についてです。$3$のところが$C$では異なると仮定します。

上の式を連列方程式にすると、

となりますが未知数が$4$つに対し式が$3$つしかなく、解が一意に決まりません。

もし$B$の第$4$行$4$列が$1$であれば、

と式が$4$つになるので連立方程式は、

となり解が一意に決まります。$B$は行簡約階段形なので$(4,4)$成分が$1$であれば第$4$列の他の成分は全て$0$である必要があります。これは$C$も同じです。つまり$B$と$C$は同一ということになります。

$m \times n$の行列でも同様です。$B$と$C$は同一です。これは$B \neq C$の仮定に反します。したがって仮定に反し$B=C$でなければなりません。

これは、$2$つの行列の第$1$列から第$n-1$列までが等しければ第$n$列も等しいということを示しています。つまり、$m \times n-1$の行列が等しければ$m \times n$の行列も等しいということです。

すでに列の数が$1$のときも成立することがわかっています。ということは列の数が$2$の場合、$3$の場合と増やしていっても同様です。このようにして数学的帰納法により、列の数がいくつであっても等しいということが証明できました。

定理3

$A$と$C$に対する同じ行基本変形によってそれぞれ$A’$、$C’$が得られるとする。

$$C=AB$$

の関係にある場合、

$$C’=A’B$$

$2$つの行列の積に対し行基本変形を行った場合、左側の行列のみが変形すると考えられるという定理です。

証明

$$C=AB$$

は、各成分により、

$$c_{ij}=\sum_{k=1}^n a_{ik}b_{kj}$$

と表される。

それぞれの行基本変形について同じように$A’B$を表す。

$ (a) $$A$の第$p$行と第$q$行を入れ替えた場合

$A’B$の$(p,j)$成分は

\begin{align}
\sum_{k=1}^n a’_{pk}b^{\ }_{kj}&=\sum_{k=1}^n a_{qk}b_{kj}\\&=c_{qj}
\end{align}

$(q,j)$成分も同様に

\begin{align}
\sum_{k=1}^n a’_{qk}b^{\ }_{kj}&=\sum_{k=1}^n a_{pk}b_{kj}\\&=c_{pj}
\end{align}

第$p$行、第$q$行以外（$(i,j)$成分）は

\begin{align}
\sum_{k=1}^n a’_{ik}b^{\ }_{kj}&=\sum_{k=1}^n a_{ik}b_{kj}\\&=c_{ij}
\end{align}

より、第$p$行、第$q$行は入れ替わり、他の行は入れ替わらない。

$ (b) $$A$の第$p$行を定数倍した場合

$A’B$の$(p,j)$成分は、

\begin{align}
\sum_{k=1}^n a’_{pk}b^{\ }_{kj}&=\sum_{k=1}^n d a_{pk}b_{kj}\\
&=d \sum_{k=1}^n a_{pk}b_{kj}\\
&=d c_{pj}
\end{align}

第$p$行以外（$(i,j)$成分）は、

\begin{align}
\sum_{k=1}^n a’_{ik}b^{\ }_{kj}&=\sum_{k=1}^n a_{ik}b_{kj}\\
&= c_{ij}
\end{align}

より、第$p$行のみ定数倍される。

$ (c) $$A$の第$p$行の定数倍を第$q$行に加えた場合

$A’B$の$(q,j)$成分は、

\begin{align}
\sum_{k=1}^n a’_{qk}b^{\ }_{kj}&=\sum_{k=1}^n (a_{qk}+da_{pk})b_{kj}\\
&= c_{qj}+dc_{pj}
\end{align}

第$q$行以外（$(i,j)$成分）は、

\begin{align}
\sum_{k=1}^n a’_{ik}b^{\ }_{kj}&=\sum_{k=1}^n a_{ik}b_{kj}\\
&= c_{ij}
\end{align}

より、第$q$行のみ第$p$行の定数倍が加算される。

以上、全ての行基本変形において
$$C’=A’B$$
となる。

■

定理4

以下の両辺に同じ行基本変形を行った結果、 $$A\boldsymbol{x}=\boldsymbol{b}$$ 以下の式となる場合、 $$A’\boldsymbol{x}=\boldsymbol{b}’$$

両式の解は同じ。

証明

行基本変形は左から基本行列を掛けることによって同一の結果が得られる。この基本行列を$E$とすると、

$$EA=A’$$

$$E\boldsymbol{b}=\boldsymbol{b}’ $$

$A\boldsymbol{x}=\boldsymbol{b} $の解を$\boldsymbol{v} $とすると、

$$A\boldsymbol{v}=\boldsymbol{b}$$

両辺の左から$E$を掛けると、

$$EA\boldsymbol{v}=E\boldsymbol{b}$$

$EA$と$E\boldsymbol{b}$を置き換えて、

$$A’\boldsymbol{v}=\boldsymbol{b}’$$

が成立する。したがって両者の解が等しい。

■

上記の$E$は単位行列ではなく基本行列である点に注意してください。

定理5

行基本変形の逆も行基本変形である。

証明

それぞれの変形の逆は以下の通り。

1. $2$列を入れ替える

第$i$行と第$j$行を入れ替える変形の逆も第$i$行と第$j$の入れ替える変形である。

2. ある行を定数倍する

第$i$行を第$c$倍する変形の逆は第$i$行を$\frac{1}{c}$倍する変形である。

3. ある行を定数倍し別の行に加える

第$i$行を$c$倍して第$j$行に加える変形の逆は、第$i$行を$-c$倍して第$j$行に加える変形である。

以上のようにいずれも行基本変形である。

■

定義4

以下を列基本変形という。

$1.\ \ $ $2$列を入れ替える

$2.\ \ $ ある列を定数倍する

$3.\ \ $ ある列を定数倍し別の列に加える

ここまで行基本変形について述べてきましたが、転置行列を考えればわかるように、基本的には列基本変形も同様の性質があります。