Ермітова нормальна форма

У прикладах нижче матриця ${\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.