行階段形

線形代数において、行列がガウス消去法によって得られる場合、その行列は行階段形であると言います。すべての行列は、一連の基本行操作を適用することで行階段形にすることができます。「階段形」という用語は、フランス語のéchelon（「はしごの段」または「段」）に由来し、行階段形の行列の非ゼロ要素が階段の段のように見えるという事実を表しています。

正方行列の場合、対角成分がゼロでない上三角行列は行階段形であり、行階段形の行列は（弱）上三角行列である。したがって、行階段形は長方形行列の上三角形の一般化と見なすことができる。

行列が簡約行階段形であるとは、行階段形であることに加えて、各行の最初の非ゼロ要素が次の値に等しいという性質を持つ場合をいう。${\displaystyle 1}$そして、その列の唯一の非ゼロ要素です。行列の簡約行階段形は一意であり、それを得るために使用される基本行操作の順序には依存しません。行列を簡約行階段形に変換する特定のタイプのガウス消去法は、ガウス・ジョルダン消去法と呼ばれることがあります。

行列の転置行列が行階段形である場合、その行列は列階段形である。したがって、列階段形のすべての性質は、対応する行階段形の性質から直ちに導き出すことができるため、本稿の残りの部分では行階段形のみを考察する。

行列が行階段形であるのは、

• エントリがゼロの行はすべて一番下にあります。^{[ 1 ]}
• ゼロ以外のすべての行の先頭のエントリ（つまり、最も左にあるゼロ以外のエントリ）はピボットと呼ばれ、その上のすべての行の先頭のエントリの右側にあります。^{[ 2 ]}

一部のテキストでは、先頭係数が 1 でなければならないという条件を追加していますが^{[ 3 ]、}他のテキストでは、簡約行階段形の場合にのみこれを要求しています。

これらの2つの条件は、先頭係数より下の列のすべてのエントリがゼロであることを意味します。^{[ 4 ]}

以下は、$4×5$行階段形行列ではあるが、簡約行階段形ではない行列：

${\displaystyle \left[{\begin{array}{ccccc}1&a_{0}&a_{1}&a_{2}&a_{3}\\0&0&2&a_{4}&a_{5}\\0&0&0&1&a_{6}\\0&0&0&0&0\end{array}}\right]}$

行列の多くの性質は、行階段形から容易に推測できます。例えば、ランクやカーネルなどです。

行列が簡約行階段形（行標準形とも呼ばれる）であるのは、次の条件を満たす場合である。^{[ 5 ]}

• これは行階段形です。
• ゼロ以外の各行の先頭の値は1です（これを先頭1と呼びます）。
• 先頭に1がある列は、それ以外のすべての項目がゼロです。

最初の2つの条件が満たされる場合、最後の条件は以下と同等です。

• 先頭に1がある各列では、先頭の1より上のすべてのエントリがゼロになります。

行列には複数の階段形が存在する可能性があるが、簡約階段形は一意である。^{[ 6 ]}

簡約行階段形の行列が与えられたとき、 i行目の先頭の1がi列目に入るように列を並べ替えると、次の形式の行列が得られます。

${\displaystyle {\begin{pmatrix}I&X\\0&0\end{pmatrix}},}$

ここで、Iは次元の 単位行列である。${\displaystyle j}$行列全体のランクに等しい、Xは次のような行列です。${\displaystyle j}$行と${\displaystyle nj}$列、そして 2 つの0は適切なサイズのゼロ行列です。列の置換は行操作ではないため、結果として得られる行列は基本行操作の下では等価ではありません。ガウス消去法では、これは元の線形システムの未知数の置換に対応し、行空間の線形パラメータ化を可能にします。${\displaystyle j}$係数は制約されておらず、残りの${\displaystyle nj}$これらは、これらの線形結合として決定される。

線形方程式系は、その拡大行列が行階段形である場合に、行階段形であると言われます。同様に、線形方程式系は、その拡大行列が簡約行階段形である場合に、簡約行階段形または標準形であると言われます。

標準形は、線形システムの明示的な解と見なすことができます。実際、システムは、標準形の方程式のいずれかが 0 = 1 に還元される場合、つまり定数項の列に先頭の 1 がある場合に限り、矛盾します。 [ 7 ^{]それ以外}の場合は、先頭の項を除く方程式のすべての項を右辺にまとめると、ピボットに対応する変数が定数または他の変数の線形関数として表現されます。

ガウス消去法は、あらゆる行列を行階段形行列に変換する主要なアルゴリズムです。ガウス・ジョルダン消去法と呼ばれる変種は、縮小行階段形を生成します。どちらも有限個の基本行操作から構成され、 m × n行列の場合 、必要な基本行操作の数は最大でmnです。^{[ 8 ]} 与えられた行列に対して、行階段形は一意ではありませんが、縮小行階段形を含むすべての行階段形は、ゼロ行の数が同じで、ピボットの位置も同じです。^{[ 8 ]}

これは簡約行階段形行列の例であり、行列の左側の部分が必ずしも単位行列ではないことを示しています。

${\displaystyle \left[{\begin{array}{ccccc}1&0&a_{1}&0&b_{1}\\0&1&a_{2}&0&b_{2}\\0&0&0&1&b_{3}\end{array}}\right]}$

整数係数を持つ行列の場合、エルミート標準形は、ユークリッド除法またはベズーの恒等式を用いることで分母を導入することなく計算できる行階段形です。整数要素を持つ行列の簡約階段形は、階段形の各行を先頭係数で割る必要があるため、一般に非整数要素を含みます。

行列の行階段形が一意でないのは、いくつかの基本行操作によって、行階段形の行列が、同じく行階段形の別の（同等の）行列に変換されるという事実から生じます。これらの基本行操作には、行にゼロ以外のスカラーを乗算すること、および行のスカラー倍をその上の行のいずれかに加えることが含まれます。例：

${\displaystyle {\begin{bmatrix}1&3&-1\\0&1&7\\\end{bmatrix}}{\xrightarrow {\text{行2を行1に加える}}}{\begin{bmatrix}1&4&6\\0&1&7\\\end{bmatrix}}.}$

この例では、第1行から第2行の3倍を引くことで、一意の簡約行階段形が得られます 。

${\displaystyle {\begin{bmatrix}1&3&-1\\0&1&7\\\end{bmatrix}}\xrightarrow {{\text{1行目から2行目まで3を減算します}}} {\begin{bmatrix}1&0&-22\\0&1&7\\\end{bmatrix}}.}$

次に、連続する行の先頭エントリを含む列の位置を示します。${\displaystyle k\times n}$マトリックス${\displaystyle A}$簡約行階段形（ピボット）では${\displaystyle (L_{1},\dots ,L_{j})}$、 と

${\displaystyle 0<L_{1}\cdots <L_{j}\leq n,}$

どこ${\displaystyle j\leq k}$は行列の行空間の次元です。${\displaystyle (k,n,L_{1},\ldots ,L_{j})}$形状は​${\displaystyle A}$先頭にゼロ以外のエントリがある ${\displaystyle \{A_{i,L_{i}}=1\}_{i=1,\dots ,j}}$列のエントリ${\displaystyle L_{i}}$その上下にあるものはすべて消え、同じ行内の左側にあるものもすべて消え、さらにその行内のすべてのエントリも消えます。${\displaystyle i}$行目${\displaystyle i>j}$:

${\displaystyle {\begin{aligned}A_{i,L_{i}}=1\qquad &{\text{for }}i=1,\dots ,j,\\A_{l,L_{i}}=0\qquad &{\text{for }}l\neq i,\\A_{i,l}=0\qquad &{\text{for }}l<L_{i},\\A_{i,l}=0\qquad &{\text{for }}i>j\end{aligned}}.}$

他のすべてのエントリは基本フィールドの任意の要素であるため${\displaystyle K}$セット${\displaystyle A(k,n,L_{1},\ldots ,L_{j})}$形状が 1 の縮約階段形行列すべて${\displaystyle (k,n,L_{1},\ldots ,L_{j})}$は次元^{[ 9 ] [ 10 ]}のKアフィン空間である。

${\displaystyle {\text{dim}}(A(k,n,L_{1},\dots ,L_{j}))=nj-{\frac {1}{2}}j(j-1)-\sum _{i=1}^{j}L_{i}.}$

これを確認するには、${\displaystyle nj}$最初の行列内の可能なエントリ${\displaystyle j}$行、${\displaystyle j^{2}}$次のように決定されます${\displaystyle 0}$'s と${\displaystyle 1}$なぜならそれらは列にあるからです${\displaystyle (L_{1},\dots ,L_{j})}$ピボットを含む。さらに $\displaystyle \sum _{i=1}^{j}(L_{i}-1)}$また、${\displaystyle 0}$なぜなら、それらは支点の左側にあるからだが、これらのうち、

$\displaystyle \sum _{i=0}^{j-1}i={\frac {1}{2}}j(j-1)}$

列にも${\displaystyle (L_{1},\dots ,L_{j})}$したがって、固定されていないエントリの総数は、${\displaystyle 0}$または${\displaystyle 1}$は

${\displaystyle nj-j^{2}+{\frac {1}{2}}j(j-1)-\sum _{i=1}^{j}L_{i}+j=nj-{\frac {1}{2}}j(j-1)-\sum _{i=1}^{j}L_{i}.}$

• Leon, Steven J. (2010)、Lynch, Deirdre、Hoffman, William、Celano, Caroline (編)、Linear Algebra with Applications (第8 版)、Pearson、ISBN 978-0-13-600929-0行列は、(i) 各非ゼロ行の最初の非ゼロ要素が 1 である場合、(ii) k 行目がすべてゼロで構成されていない場合、行の先頭のゼロ要素の数が 1 である場合、行階段形であると言われます。${\displaystyle k+1}$行kの先頭のゼロエントリの数よりも大きい。(iii) エントリがすべてゼロである行がある場合、それらの行は、ゼロ以外のエントリを持つ行の下に位置する。。
• Meyer, Carl D. (2000), Matrix Analysis and Applied Linear Algebra , SIAM , ISBN 978-0-89871-454-8。

• カルディ・テクノモ博士によるインタラクティブな行階段形チュートリアル