エルミート正規形

線型代数において、エルミート正規形は整数Z上の行列の簡約階段形の類似物である。簡約階段形がR ⁿに含まれるxの線型システムAx = bの解に関する問題を解くのに使用できるのと同様に、エルミート正規形はx が整数座標のみに制限される線型システムAx = bの解に関する問題を解くことができる。エルミート正規形の他の応用としては、整数計画法、^[1]、暗号化、^[2]、抽象代数などがある。^[3]

さまざまな著者が、エルミート正規形について行形式または列形式のどちらかで話すことを好む場合があります。それらは転置を除いて本質的に同じです。

整数要素を持つm行n列の行列Aが（行）エルミート正規形Hを持つとは、 H = UAでHが以下の制約を持つ正方ユニモジュラ行列 Uが存在することを意味する。 ^{[4] [5] [6]}

1. H は上三角行列 (つまり、i > jの場合、 h _ij = 0 ) であり、ゼロの行は他の行の下にあります。
2. 非ゼロ行の先頭係数（左から最初の非ゼロのエントリ、ピボットとも呼ばれる）は、常にその上の行の先頭係数の右側にあり、さらに正です。
3. ピボットの下の要素はゼロであり、ピボットの上の要素は非負であり、ピボットよりも厳密に小さくなります。

3番目の条件は著者の間で標準的ではありません。たとえば、いくつかの情報源では非ピボットは非正であることを強制しています^{[7] [8]}またはそれらに符号制限はありません。^{[9]ただし、これらの定義は、異なるユニモジュラー行列}Uを使用することで同等になります。ユニモジュラー行列は、行列式が1または-1である正方逆整数行列です。

整数要素を持つm行n列の行列Aが（列）エルミート正規形Hを持つとは、H = AUで次の制約を持つ正方ユニモジュラー行列 Uが存在することを意味する。 ^[8] [ ^10]

1. H は下三角行列で、i < jに対してh _ij = 0 となり、ゼロの列はすべて右側に配置されます。
2. 非ゼロ列の先頭係数（上から最初の非ゼロのエントリ、ピボットとも呼ばれる）は、常にその前の列の先頭係数よりも厳密に小さく、さらに正です。
3. ピボットの右側の要素はゼロであり、ピボットの左側の要素は非負であり、ピボットよりも厳密に小さくなります。

行スタイルの定義では、ユニモジュラ行列Uが左側でA を乗算します(つまり、 U はAの行に作用します)。一方、列スタイルの定義では、ユニモジュラ行列がAの列に作用します。エルミート正規形の 2 つの定義は、単純に互いの転置です。

整数要素を持つすべてのフル行ランクm行n列行列Aは、エルミート正規形の唯一のm行n列行列Hを持ち、ある正方ユニモジュラ行列Uに対してH = UAとなる。^{[5] [11] [12]}

以下の例では、H は行列Aのエルミート正規形であり、U はUA = Hとなるユニモジュラ行列です。 $${\displaystyle A={\begin{pmatrix}3&3&1&4\\0&1&0&0\\0&0&19&16\\0&0&0&3\end{pmatrix}}\qquad H={\begin{pmatrix}3&0&1&1\\0&1&0&0\\0&0&19&1\\0&0&0&3\end{pmatrix}}\qquad U=\left({\begin{array}{rrrr}1&-3&0&-1\\0&1&0&0\\0&0&1&-5\\0&0&0&1\end{array}}\right)}$$

$${\displaystyle A={\begin{pmatrix}2&3&6&2\\5&6&1&6\\8&3&1&1\end{pmatrix}}\qquad H=\left({\begin{array}{rrrr}1&0&50&-11\\0&3&28&-2\\0&0&61&-13\end{array}}\right)\qquad U=\left({\begin{array}{rrr}9&-5&1\\5&-2&0\\11&-6&1\end{array}}\right)}$$

A に行が 1 つしかない場合は、 Aの 1 つの行の先頭係数が正か負か によって、H = AまたはH = − A のいずれかになります。

エルミート正規形を計算するアルゴリズムは数多く存在し、その歴史は 1851 年にまで遡ります。そのようなアルゴリズムの 1 つが^{[13] : 43--45}に記載されています。しかし、1979 年になって初めて、強多項式時間で実行されるエルミート正規形を計算するアルゴリズムが開発されました。^[14]つまり、エルミート正規形を計算するステップ数は、入力行列の次元の多項式で上限が決まっており、アルゴリズム (中間数) で使用される空間は、入力行列の数値のバイナリ エンコード サイズの多項式で上限が決まっています。

アルゴリズムの1つのクラスは、特殊な基本行列を繰り返し使用するという点でガウス消去法に基づいています。 ^{[11] [15] [16]} LLLアルゴリズムは、エルミート正規形を効率的に計算するためにも使用できます。^{[17] [18]}

R ⁿの典型的な格子は、 a _iがR ⁿにある形式を持ちます。行列Aの列がa _iである場合、格子は行列の列に関連付けることができ、A はLの基底であるといわれます。エルミート正規形は一意であるため、2 つの格子の記述に関する多くの質問に答えるために使用できます。以下では、 はA の列によって生成される格子を表します。基底は行列Aの列にあるため、列スタイルのエルミート正規形を使用する必要があります。格子の 2 つの基底AとA'が与えられた場合、同値問題は かどうかを判断することです。これは、 AとA'の列スタイルのエルミート正規形が、列を 0 個追加するまで同じであるかどうかを確認することで実行できます。この戦略は、格子がサブセットであるかどうかを判断する場合 ( の場合のみ)、ベクトル v が格子内にあるかどうかを判断する場合 (の場合のみ)、およびその他の計算にも役立ちます。^[19]${\textstyle L=\left\{\left.\sum _{i=1}^{n}\alpha _{i}\mathbf {a} _{i}\;\right\vert \;\alpha _{i}\in {\textbf {Z}}\right\}}$${\displaystyle L_{A}}$${\displaystyle L_{A}=L_{A'}.}$${\displaystyle L_{A}\subseteq L_{A'}}$${\displaystyle L_{[A\mid A']}=L_{A'}}$${\displaystyle v\in L_{A}}$${\displaystyle L_{[v\mid A]}=L_{A}}$

線形システムAx = bが整数解xを持つのは、システムHy = bが整数解yを持つ場合のみである。ここで、y = U ⁻¹ xであり、HはAの列スタイルのエルミート標準形である。Hy = bが整数解を持つことを確認するのは、行列Hが三角行列であるため、 Ax = bよりも簡単である。^[11] ：⁵⁵

多くの数学ソフトウェア パッケージは、エルミート正規形を計算できます。

• メープルとHermiteForm
• HermiteDecomposition を使用したMathematica
• hermiteForm を使用したMATLAB
• HNF 付きNTL
• PARI/GPと mathnf
• SageMathと hermite_form

エルミート正規形は、 Zを任意のデデキント領域に置き換えることで定義できます。^[20]（たとえば、任意の主イデアル領域）。たとえば、制御理論では、与えられた体F上の多項式F [ x ]のエルミート正規形を考慮すると便利です。

• エルミートリング
• スミス正規形
• ハウエル正規形
• ディオファントス方程式