階段行列（行既約な階段行列）とガウス・ジョルダンの消去法

階段行列

行列\(A\in M_{m,n}\left( \mathbb{R} \right) \)を任意に選びます。つまり、\begin{equation*}A=\begin{pmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\cdots & \cdots & \cdots & \cdots \\
a_{m1} & a_{m2} & \cdots & a_{mn}\end{pmatrix}\end{equation*}です。この行列\(A\)の第\(i\ \left( =1,\cdots ,m\right) \)行は\(n\)次元の行ベクトル\begin{equation*}\mathrm{row}\left( A,i\right) =\left( a_{i1},a_{i2},\cdots ,a_{in}\right)
\end{equation*}ですが、これがゼロベクトルではない場合、成分\(a_{i1},a_{i2},\cdots ,a_{in}\)の中にはゼロではない実数が存在します。そこで、非ゼロの成分の中で最も左にあるものを第\(i\)行の主成分（distinguished element）やピボット（pivot）などと呼びます。つまり、第\(i\)行の成分\(a_{ij}\)が主成分であることとは、\(a_{ij}\)が非ゼロであるとともに、\(a_{ij}\)よりも左側にあるすべての成分が\(0\)であること、すなわち、以下の条件\begin{eqnarray*}&&\left( a\right) \ a_{ij}\not=0 \\
&&\left( b\right) \ \forall k\in \left\{ 1,2,\cdots ,j-1\right\} :a_{ik}=0
\end{eqnarray*}がともに成り立つことを意味します。

行列\(A\)の第\(i\)行がゼロベクトルである場合、その行には主成分は存在しません。

行列\(A\in M_{m,n}\left( \mathbb{R} \right) \)が以下の2つの条件を満たす場合、\(A\)を階段行列（echelon matrix）や階段形式（echelon form）にあるなどと言います。

1. 行列\(A\)がゼロベクトルであるような行を持つ場合、それらの行はいずれも非ゼロベクトルであるようなすべての行よりも下に位置している。つまり、ゼロベクトルであるような行\(\mathrm{row}\left( A,i\right) \)と非ゼロベクトルであるような行\(\mathrm{row}\left( A,i^{\prime }\right) \)をそれぞれ任意に選んだとき、\begin{equation*}i^{\prime }<i\end{equation*}が成り立つ。
2. 行列\(A\)が非ゼロベクトルであるような複数の行を持つ場合、それらを見比べたとき、より上にある行の主成分が、より下にある行の主成分よりも左に位置している。すなわち、非ゼロベクトルであるような行\(\mathrm{row}\left( A,i\right) \)の主成分が\(a_{ij}\)であり、同じく非ゼロベクトルであるような行\(\mathrm{row}\left(A,i^{\prime }\right) \)の主成分が\(a_{i^{\prime}j^{\prime }}\)である場合、\begin{equation*}i^{\prime }<i\Rightarrow j^{\prime }<j\end{equation*}が成り立つ。

行列\(A\)のすべての行がゼロベクトルである場合、すなわち\(A\)がゼロ行列である場合には、\(A\)を階段行列とみなします。

行列を階段行列に行簡約する方法

行列の行基本操作とは以下の3種類の操作\begin{eqnarray*}
&&\left( E_{1}\right) \ R_{i}\leftrightarrow R_{j} \\
&&\left( E_{2}\right) \ R_{i}\rightarrow kR_{i}\quad \left( k\not=0\right)
\\
&&\left( E_{3}\right) \ R_{i}\rightarrow R_{i}+kR_{j}
\end{eqnarray*}の総称です。行列\(A\)に対して基本行操作を有限回適用することで行列\(B\)が得られる場合、\(A\)は\(B\)と行同値であると言います。

行列\(A\)がゼロ行列である場合、定義より、それは階段行列です。一方、行列\(A\)がゼロ行列ではない場合、基本行操作を通じて階段行列へ変換できます。まずは具体例を提示し、後に結論を一般化します。

以上のプロセスを一般化します。行列\(A\)がゼロ行列である場合、定義より、それは階段行列です。一方、行列\(A\)がゼロ行列ではない場合、以下の基本行操作を適用すれば、有限ステップ内で階段行列が得られます。これをガウス・ジョルダンの消去法（Gauss-Jordan algorithm）と呼びます。

1. 行列\(A\)は非ゼロ行列であるため、非ゼロベクトルであるような行を持つ。非ゼロベクトルであるような行どうしを見比べた上で、主成分が最も左にある行\(i\)が第\(1\)行になるように行を入れ替える。すなわち、以下の基本行操作\begin{equation*}R_{i}\leftrightarrow R_{1}\end{equation*}を行う。入れ替え後の第\(1\)行の主成分を\(a_{1j}\)で表記する。その上で、\(2\)行目以降のそれぞれの行に対して、すなわち、\(i\geq 2\)を満たすそれぞれの行\(i\)に対して、以下の基本行操作\begin{equation*}R_{i}\rightarrow -a_{i1}R_{1}+a_{11}R_{i}
   \end{equation*}を行う。その結果、\(2\)行目以降のすべての行の第\(j\)成分およびそれより左側の成分がすべて\(0\)になる。\(2\)行目以降がすべてゼロベクトルならば、得られた行列は階段行列である。\(2\)行目以降に非ゼロベクトルである場合には次のステップへ進む。
2. 第\(1\)行を除外したすべての行によって作られる小行列を対象に、先と同様の一連の操作を行う。つまり、非ゼロベクトルであるような\(2\)行目以降の行どうしを見比べた上で、主成分が最も左にある行\(i\)が第\(2\)行になるように行を入れ替える。すなわち、以下の基本行操作\begin{equation*}R_{i}\leftrightarrow R_{2}\end{equation*}を行う。入れ替え後の第\(2\)行の主成分を\(a_{2j}\)で表記する。その上で、\(3\)行目以降のそれぞれの行に対して、すなわち、\(i\geq 3\)を満たすそれぞれの行\(i\)に対して、以下の基本行操作\begin{equation*}R_{i}\rightarrow -a_{i1}R_{2}+a_{21}R_{i}
   \end{equation*}を行う。その結果、\(3\)行目以降のすべての行の第\(j\)成分およびそれより左側の成分がすべて\(0\)になる。\(3\)行目以降がすべてゼロベクトルならば、得られた行列は階段行列である。\(3\)行目以降に非ゼロベクトルである場合には次のステップへ進む。
3. 同様のプロセスを繰り返す。つまり、第\(1\)行から第\(k-1\)行までを除外したすべての行によって作られる小行列を対象に、先と同様の一連の操作を行う。つまり、非ゼロベクトルであるような\(k\)行目以降の行どうしを見比べた上で、主成分が最も左にある行\(i\)が第\(k\)行になるように行を入れ替える。すなわち、以下の基本行操作\begin{equation*}R_{i}\leftrightarrow R_{k}\end{equation*}を行う。入れ替え後の第\(k\)行の主成分を\(a_{kj}\)で表記する。その上で、\(k+1\)行目以降のそれぞれの行に対して、すなわち、\(i\geq k+1\)を満たすそれぞれの行\(i\)に対して、以下の基本行操作\begin{equation*}R_{i}\rightarrow -a_{i1}R_{k}+a_{k1}R_{i}
   \end{equation*}を行う。その結果、\(k+1\)行目以降のすべての行の第\(j\)成分およびそれより左側の成分がすべて\(0\)になる。\(k+1\)行目以降がすべてゼロベクトルならば、得られた行列は階段行列である。\(k+1\)行目以降に非ゼロベクトルである場合には次のステップへ進む。
4. 行列\(A\)の行の個数\(m\)は有限であるため、プロセスは有限ステップで終了し、その結果、階段行列が得られる。

行列が与えられたとき、ガウス・ジョルダンの消去法を適用すれば、必ず有限ステップ内で階段行列が得られます。以上の事実は、任意の行列には、それと行同値な階段行列が存在することを意味します。

行既約な階段行列

以下の3つの条件を満たす行列\(A\)を行既約な階段行列（row reduced echelon matrix）と呼びます。

1. 行列\(A\)は階段行列である。
2. 行列\(A\)が非ゼロベクトルであるような行を持つ場合、それらの行の主成分がいずれも\(1\)である。つまり、非ゼロベクトルであるような行\(\mathrm{row}\left( A,i\right) \)の主成分が\(a_{ij}\)である場合、\begin{equation*}a_{ij}=1\end{equation*}が成り立つ。
3. 行列\(A\)が非ゼロベクトルであるような行を持つ場合、その行の主成分は、その主成分が存在する列において唯一の非ゼロの成分である。つまり、非ゼロベクトルであるような行\(\mathrm{row}\left(A,i\right) \)の主成分が\(a_{ij}\)である場合、\begin{equation*}\forall i^{\prime }\not=i:a_{i^{\prime }j}=0\end{equation*}が成り立つ。

行列\(A\)のすべての行がゼロベクトルである場合、すなわち\(A\)がゼロ行列である場合には、\(A\)を行既約な階段行列とみなします。

階段行列を行既約な階段行列に行簡約する方法

行列\(A\)がゼロ行列である場合、定義より、それは行既約な階段行列です。一方、階段行列\(A\)が行既約ではない場合、基本行操作を通じて行既約な階段行列へ変換できます。まずは具体例を提示し、後に結論を一般化します。

以上のプロセスを一般化します。行列\(A\)がゼロ行列である場合、定義より、それは行既約な階段行列です。一方、階段行列\(A\)が行既約ではない場合、以下の基本行操作を適用すれば、有限ステップ内で行既約な階段行列が得られます。行列を階段行列へ変換する先のプロセスと以下のプロセスをあわせてガウス・ジョルダンの消去法（Gauss-Jordan algorithm）と呼ぶ場合もあります。

1. 階段行列\(A\)の第\(i\)行の主成分を\(a_{ij}\)で表記する。\(k<i\)であるような行\(k\)の中に\(a_{kj}\not=0\)を満たすものが存在する場合、その行\(k\)に対して以下の行基本操作\begin{equation*}R_{k}\rightarrow -a_{kj}R_{i}+a_{ij}R_{k}\end{equation*}を行う。その結果、それぞれの行の主成分は、その主成分が存在する列において唯一の非ゼロの成分となる。
2. 以上の行基本操作を行った後の第\(i\)行の主成分\(a_{ij}\)が\(1\)ではない場合、その行\(i\)に対して以下の行基本操作\begin{equation*}R_{i}\rightarrow \frac{1}{a_{ij}}R_{i}\end{equation*}を行う。その結果、すべての主成分が\(1\)になる。

行列が与えられたとき、それと行同値な階段行列が存在することは先に指摘した通りです。その階段行列に対して上で定義した一連の基本行操作を行えば、必ず行既約な階段行列が得られます。以上の事実は、任意の行列には、それと行同値な行既約な階段行列が存在することを意味します。

演習問題