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

Ермітова нормальна форма — це аналог ступінчастого вигляду матриці для матриць над кільцем ${\displaystyle \mathbb {Z} }$ цілих чисел. Тоді як ступінчастий вигляд матриці використовується для розв'язання систем лінійних рівнянь виду ${\displaystyle Ax=b}$ для ${\displaystyle x\in \mathbb {R} ^{n}}$, ермітову нормальну форму можна використати для розв'язання лінійних систем діофантових рівнянь, у яких мається на увазі, що ${\displaystyle x\in \mathbb {Z} ^{n}}$. Ермітова нормальна форма використовується у розв'язанні задач цілочисельного програмування^[1], криптографії^[2] і загальної алгебри^[3].

Визначення

Матриця ${\displaystyle H}$ є ермітовою нормальною формою цілочисельної матриці ${\displaystyle A}$ якщо є унімодулярна матриця ${\displaystyle U}$ така що ${\displaystyle H=UA}$ і ${\displaystyle H}$ задовольняє таким вимогам^[4][5][6]:

1. ${\displaystyle H}$ є верхньо-трикутною, тобто, ${\displaystyle h_{ij}=0}$ якщо ${\displaystyle i>j}$ і будь-який рядок, що цілком складається з нулів, лежить нижче від всіх інших.
2. Ведучий елемент будь-якого ненульового рядка завжди додатний і лежить правіше від ведучого коефіцієнта рядка над ним.
3. Елементи під ведучими дорівнюють нулю, а елементи над ведучими невід'ємні і строго менші від ведучого.

Деякі автори в третій умові вимагають, щоб елементи були недодатними^[7][8] або взагалі не накладають на них знакових обмежень^[9].

Існування та єдиність ермітової нормальної форми

Ермітова нормальна форма ${\displaystyle H}$ існує і єдина для будь-якої цілочисельної матриці ${\displaystyle A}$^[5][10][11].

Приклади

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

Реалізація

Обчислення ермітової нормальної форми реалізовано в багатьох системах комп'ютерної алгебри:

• HermiteForm [Архівовано 23 січня 2021 у Wayback Machine.] в Maple
• HermiteDecomposition [Архівовано 10 грудня 2019 у Wayback Machine.] в Mathematica
• hermiteForm [Архівовано 14 квітня 2021 у Wayback Machine.] в MATLAB
• hermite_form [Архівовано 6 травня 2021 у Wayback Machine.] в SageMath^[ru]

Див. також

• Нормальна форма Сміта
• Діофантові рівняння

Джерела

• Гантмахер Ф. Р. Теорія матриць. — 2025. — 757 с.(укр.)