列階段形式

線形代数では、ガウス消去法の結果として得られる行列は階段行列形式になります。すべての行列は、一連の基本的な行演算を適用することで階段行列形式にすることができます。階段行列という用語は、フランス語のéchelon（「レベル」または梯子の段）に由来し、階段行列形式の行列のゼロ以外の要素が逆の階段のように見えることを指します。

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

行列が行階段形式であるとは、行階段形式でありながら、各行の最初の非ゼロ要素がその列の唯一の非ゼロ要素に等しく、かつその列の唯一の非ゼロ要素であるという追加の特性を持つ場合です。行列の行階段形式は一意であり、それを得るために使用される基本行演算の順序に依存しません。行列を行階段形式に変換するガウス消去法の変形は、ガウス・ジョルダン消去法と呼ばれることもあります。 ${\displaystyle 1}$

行列の転置が行階段形式である場合、その行列は列階段形式です。列階段形式のすべての特性は行階段形式の対応する特性から直ちに推測できるため、この記事の残りの部分では行階段形式のみを考慮します。

行列が階段状になっているのは、

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

いくつかのテキストでは、先頭の係数が1でなければならないという条件を追加していますが^[3]、他のテキストでは、この条件は簡約された階段状の形式でのみ要求されます。

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

以下は、簡約された階段状行列ではない、階段状行列形式の行列の例です (下記参照)。 ${\displaystyle 4\times 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 が含まれる各列の他のすべてのエントリには 0 が含まれます。

最初の 2 つの条件が検証された場合、最後の条件は次の式と同等になります。

• 先頭に1 が含まれる各列では、先頭の1より上のすべてのエントリに 0 が含まれます。

マトリックスには複数の階段形式が存在する場合がありますが、その簡約階段形式は一意です。

縮小された行階段形式の行列が与えられ、 i番目の行の先頭の1がi番目の列になるように列を並べ替えると、次の形式の行列が得られます。

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

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

線形方程式のシステムでは、その拡張行列が階段状になっている場合、そのシステムは階段状になっていると言われます。同様に、線形方程式のシステムでは、その拡張行列が階段状になっている場合、そのシステムは階段状になっている、または標準形式になっていると言われます。

正準形式は線形システムの明示的な解として見ることができます。実際、正準形式の方程式の 1 つが 0 = 1 に簡約される場合にのみ、システムは矛盾します。つまり、定数項の列の先頭に1がある場合です。 ^[6]それ以外の場合は、方程式の先頭の項を除くすべての項を右側にまとめると、ピボットに対応する変数が定数または他の変数の線形関数として表現されます (存在する場合)。

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

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

${\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{add row 2 to row 1}}}{\begin{bmatrix}1&4&6\\0&1&7\\\end{bmatrix}}.}$

この例では、最初の行から 2 番目の行を 3 回減算することで、一意の簡約された行階段形式を取得できます。

${\displaystyle {\begin{bmatrix}1&3&-1\\0&1&7\\\end{bmatrix}}\xrightarrow {{\text{subtract 3}}\times {\text{(row 2) from row 1}}} {\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}}.}$

他のすべての要素は基底体の任意の要素であるため、形状を持つすべての縮小階段状行列の集合は次元のKアフィン空間である^{[8] [9]}${\displaystyle K}$${\displaystyle A(k,n,L_{1},\ldots ,L_{j})}$${\displaystyle (k,n,L_{1},\ldots ,L_{j})}$

${\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}$${\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}.}$

行階段形式は、ベクトル空間の次元部分空間のグラスマン多様体に関連付けられたシューベルト細胞を具体的に記述するために使用できます。 ${\displaystyle k}$

の場合、行列は最大階数 であり、自由- モジュールの- 次元部分空間を、その範囲が ${\displaystyle j=k\leq n}$${\displaystyle A\in A(k,n,L_{1},\dots ,L_{k})}$${\displaystyle k}$${\displaystyle k}$${\displaystyle w\subset V}$${\displaystyle K}$${\displaystyle V:=K^{n}}$

${\displaystyle w={\text{span}}\{W_{1},\dots ,W_{k}\}}$

線形結合の

${\displaystyle W_{i}:=\sum _{l=1}^{n}A_{il}e_{l},\quad i=1,\dots ,k}$

の係数が行ベクトルに等しい基本基底ベクトルの集合である。この場合、アフィン空間はグラスマン多様体のシューベルトセル^{[8] [9]}であり、整数分割に対応するの次元部分空間から構成される。${\displaystyle (e_{1},\dots ,e_{n})}$${\displaystyle A(k,n,L_{1},\dots ,L_{k})}$ ${\displaystyle X_{\lambda }({\mathcal {V}})}$ ${\displaystyle \mathbf {Gr} _{k}(V)}$${\displaystyle k}$${\displaystyle V}$

${\displaystyle \lambda =(\lambda _{1}\geq \cdots \geq \lambda _{k}\geq 0)}$

等しい部分を持つ

${\displaystyle \lambda _{i}:=n-k-L_{i}+i,\quad 1\leq j\leq k,}$

完全なフラグに対する相対

${\displaystyle {\mathcal {V}}=(V_{1}\subset V_{2}\cdots \subset V_{n}=V),}$

どこ

${\displaystyle V_{i}={\text{span}}\{e_{1},\dots ,e_{i}\},\quad i=1,\dots n.}$

これは、 が-次元部分空間で構成され、その部分 空間との交差が次元を持つ ことを意味する。${\displaystyle X_{\lambda }({\mathcal {V}})\subset \mathbf {Gr} _{k}(V)}$${\displaystyle k}$${\displaystyle w\subset V}$${\displaystyle \{V_{j}\}_{j=1,\dots ,n}}$

${\displaystyle {\text{dim}}(w\cap V_{j})=i,\ {\text{for }}n-k-\lambda _{i}+i\leq j\leq n-k-\lambda _{i+1}+i,\quad i=1,\dots ,k.}$

その寸法はパーティションの重量に等しい^[8]${\displaystyle |\lambda |=\sum _{i=1}^{k}\lambda _{i}}$

${\displaystyle \dim({X_{\lambda }({\mathcal {V}})})=|\lambda |.}$

シューベルトセルの同等だがより単純な特徴付けは、双対完全フラグによって与えられる。${\displaystyle X_{\lambda }({\mathcal {V}})}$

${\displaystyle {\tilde {\mathcal {V}}}=({\tilde {V}}_{1}\subset {\tilde {V}}_{2}\cdots \subset {\tilde {V}}_{n}=V),}$

どこ

${\displaystyle {\tilde {V}}_{i}={\text{span}}\{e_{n},\dots ,e_{n-i+1}\},\quad i=1,\dots n.}$

そして、これらの-次元部分空間は、 要素からなる 基底を持ち、${\displaystyle X_{\lambda }({\mathcal {V}})\subset \mathbf {Gr} _{k}(V)}$${\displaystyle k}$${\displaystyle w\subset V}$${\displaystyle ({\tilde {W}}_{1},\dots ,{\tilde {W}}_{k})}$

${\displaystyle {\tilde {W}}_{i}\in {\tilde {V}}_{n-L_{i}+1}={\tilde {V}}_{k+\lambda _{i}-i+1},\quad i=1,\dots ,k}$

標準基底を基準として、逆順に書かれた行階段形式の 行ベクトルである部分空間。${\displaystyle \{{\tilde {V}}_{k+\lambda _{i}-i+1}\}_{i=1,\dots ,k}}$${\displaystyle (W_{k},\dots ,W_{1})}$

• レオン、スティーブン J. (2010)、リンチ、ディアドラ、ホフマン、ウィリアム、セラーノ、キャロライン (編)、線形代数の応用(第 8 版)、ピアソン、ISBN 978-0-13-600929-0行列は、(i) 各非ゼロ行の最初の非ゼロ要素が 1 である場合、行階段形式であると言われます。(ii) 行k がすべてゼロで構成されていない場合、行の先頭のゼロ要素の数は、行kの先頭のゼロ要素の数よりも大きくなります。(iii) 要素がすべてゼロの行がある場合、それらの行は非ゼロ要素を持つ行の下にあります。${\displaystyle k+1}$。
• マイヤー、カール D. (2000)、行列解析と応用線形代数、SIAM、ISBN 978-0-89871-454-8。

ウィキブック線形代数には、行削減と階段形式に関するページがあります。

• 有理的な出力を備えたインタラクティブな行エシェロンフォーム