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

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

Визначення

Матриця $H$ є ермітовою нормальною формою цілочисельної матриці $A$ якщо є унімодулярна матриця $U$ така що $H=UA$ і $H$ задовольняє таким вимогам:

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

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

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

Ермітова нормальна форма $H$ існує і єдина для будь-якої цілочисельної матриці $A$.

Приклади

У прикладах нижче матриця $H$ є ермітовою нормальною формою матриці $A$, а відповідною унімодулярною матрицею є матриця $U$ така що $H=UA$.

$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)$

$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 року. Один із широко використовуваних класів алгоритмів для зведення матриці до ермітової нормальної форми ґрунтується на модифікованому методі Гауса. Іншим поширеним методом обчислення ермітової нормальної форми є LLL-алгоритм.

Застосування

Обчислення в ґратках

Зазвичай ґратки в $\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\}}$, де $a_{i}\in \mathbb {R} ^{n}$. Якщо розглянути матрицю $A$, чиї рядки складені із векторів $a_{i}$, то її ермітова нормальна форма задаватиме деякий єдиним чином визначений базис ґратки. Це спостереження дозволяє швидко перевіряти, чи збігаються ґратки, породжені рядками матриць $A$ і $A'$, для чого достатньо перевірити, що в матриць збігаються їхні ермітові нормальні форми. Аналогічно можна перевірити, чи є ґратка $L_{A'}$ підґраткою ґратки $L_{A}$, для чого достатньо розглянути матрицю $A''$, отриману з об'єднання рядків $A$ і $A'$. У такій постановці $L_{A'}$ є підґраткою $L_{A}$ якщо і тільки якщо збігаються ермітові нормальні форми $A$ і $A''$.

Лінійні діофантові рівняння

Система лінійних рівнянь $Ax=b$ має цілочисельний розв'язок $x$, якщо і тільки якщо система $Hx=Ub$ має цілочисельний розв'язок, де $H=UA$ — ермітова нормальна форма матриці $A$^: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

Див. також

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

Джерела

• Гантмахер Ф. Р. Теория матриц. — 5-е. — М: : Физматлит, 2010. — 559 с. — ISBN 5-9221-0524-8.(рос.)