Эрмитова нормальная форма

В примерах ниже матрица ${\displaystyle H}$ является эрмитовой нормальной формой матрицы ${\displaystyle A}$, а соответствующей унимодулярной матрицей является матрица ${\displaystyle U}$ такая что ${\displaystyle H=UA}$.

${\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=\left({\begin{array}{rrrr}2&3&6&2\\5&6&1&6\\8&3&1&1\end{array}}\right)\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)}$

Первые алгоритмы вычисления эрмитовой нормальной формы датируются 1851 годом. При этом первый алгоритм, работающий за строго полиномиальное время был разработан лишь в 1979 году[12]. Один из широко используемых классов алгоритмов для приведения матрицы к эрмитовой нормальной форме основан на модифицированном методе Гаусса[10][13][14]. Другим распространённым методом вычисления эрмитовой нормальной формы является LLL-алгоритм[15][16].

Обычно решётки в ${\displaystyle \mathbb {R} ^{n}}$ имеют вид ${\textstyle L=\left\{\left.\alpha _{1}a_{1}+\alpha _{2}a_{2}+\dots +\alpha _{n}a_{n}\;\right\vert \;\alpha _{i}\in \mathbb {Z} \right\}}$, где ${\displaystyle a_{i}\in \mathbb {R} ^{n}}$. Если рассмотреть матрицу ${\displaystyle A}$, чьи строки составлены из векторов ${\displaystyle a_{i}}$, то её эрмитова нормальная форма будет задавать некоторый единственным образом определённый базис решётки. Данное наблюдение позволяет быстро проверять, совпадают ли решётки, порождённые строками матриц ${\displaystyle A}$ и ${\displaystyle A'}$, для чего достаточно проверить, что у матриц совпадают их эрмитовы нормальные формы. Аналогичным образом можно проверить, является ли решётка ${\displaystyle L_{A'}}$ подрешёткой решётки ${\displaystyle L_{A}}$, для чего достаточно рассмотреть матрицу ${\displaystyle A''}$, полученную из объединения строк ${\displaystyle A}$ и ${\displaystyle A'}$. В такой постановке ${\displaystyle L_{A'}}$ является подрешёткой ${\displaystyle L_{A}}$ если и только если совпадают эрмитовы нормальные формы ${\displaystyle A}$ и ${\displaystyle A''}$[17].

Система линейных уравнений ${\displaystyle Ax=b}$ имеет целочисленное решение ${\displaystyle x}$ если и только если система ${\displaystyle Hx=Ub}$ имеет целочисленное решение, где ${\displaystyle H=UA}$ — эрмитова нормальная форма матрицы ${\displaystyle A}$[10]^:55.