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

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

Визначення

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

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

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

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

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

Приклади

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

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

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

Зазвичай ґратки в ${\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''}$.

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

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

Див. також

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

Джерела

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

Примітки

1. Hung, Ming S.; Rom, Walter O. An application of the Hermite normal form in integer programming //  : journal. — 1990. — Vol. 140, (10). — P. 163—179. — DOI:10.1016/0024-3795(90)90228-5.
2. Evangelos, Tourloupis, Vasilios. Hermite normal forms and its cryptographic applications. — University of Wollongong, 2013. — . — 1. з джерела 17 лютого 2019. Процитовано 25 березня 2021.
3. Adkins, William; Weintraub, Steven. [1] — , 2012. — С. 306. — . з джерела 13 вересня 2020
4. . doc.sagemath.org. Архів оригіналу за 6 травня 2021. Процитовано 22 червня 2016.
5. Mader, A. [2] — CRC Press, 2000. — . з джерела 14 червня 2020
6. Micciancio, Daniele; Goldwasser, Shafi. [3] — , 2012. — . з джерела 26 червня 2020
7. W., Weisstein, Eric. . mathworld.wolfram.com (англ.). Архів оригіналу за 6 травня 2021. Процитовано 22 червня 2016.
8. Bouajjani, Ahmed; Maler, Oded. [4] — , 2009. — . з джерела 5 вересня 2020
9. . www.mathworks.com. Архів оригіналу за 17 лютого 2019. Процитовано 22 червня 2016.
10. Schrijver, Alexander. [5] — , 1998. — . з джерела 14 червня 2020
11. Cohen, Henri. [6] — , 2013. — . з джерела 28 вересня 2020
12. Kannan, R.; Bachem, A. Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix // ^[en] : journal. — 1979. — Vol. 8, no. 4, (11). — P. 499—507. — ISSN 0097-5397. — DOI:10.1137/0208040. з джерела 6 травня 2021. Процитовано 25 березня 2021.
13. . 2 березня 2010. Архів оригіналу за 7 серпня 2016. Процитовано 30 березня 2020.
14. Martin, Richard Kipp. Chapter 4.2.4 Hermite Normal Form // Large Scale Linear and Integer Optimization: A Unified Approach. — , 2012. — .
15. Bremner, Murray R. Chapter 14: The Hermite Normal Form // Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications. — CRC Press, 2011. — .
16. Havas, George; Majewski, Bohdan S.; Matthews, Keith R. Extended GCD and Hermite normal form algorithms via lattice basis reduction // Experimental Mathematics : journal. — 1998. — Vol. 7, no. 2 (6 July). — P. 130—131. — ISSN 1058-6458. з джерела 22 червня 2020. Процитовано 25 березня 2021.
17. Micciancio, Daniele. (PDF). Архів оригіналу (PDF) за 27 грудня 2015. Процитовано 25 червня 2016.