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

Ермітова нормальна форма — це аналог ступінчастого вигляду матриці для матриць над кільцем ${\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]

Див. також

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

Джерела

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

Примітки

1. Hung, Ming S.; Rom, Walter O. An application of the Hermite normal form in integer programming // Linear Algebra and its Applications : 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] — Springer Science & Business Media, 2012. — С. 306. — ISBN 9781461209232. Архівовано з джерела 13 вересня 2020
4. Dense matrices over the integer ring — Sage Reference Manual v7.2: Matrices and Spaces of Matrices. doc.sagemath.org. Архів оригіналу за 6 травня 2021. Процитовано 22 червня 2016.
5. Mader, A. [2] — CRC Press, 2000. — ISBN 9789056992255. Архівовано з джерела 14 червня 2020
6. Micciancio, Daniele; Goldwasser, Shafi. [3] — Springer Science & Business Media, 2012. — ISBN 9781461508977. Архівовано з джерела 26 червня 2020
7. W., Weisstein, Eric. Hermite Normal Form. mathworld.wolfram.com (англ.). Архів оригіналу за 6 травня 2021. Процитовано 22 червня 2016.
8. Bouajjani, Ahmed; Maler, Oded. [4] — Springer Science & Business Media, 2009. — ISBN 9783642026577. Архівовано з джерела 5 вересня 2020
9. Hermite normal form of a matrix - MuPAD. www.mathworks.com. Архів оригіналу за 17 лютого 2019. Процитовано 22 червня 2016.
10. Schrijver, Alexander. [5] — John Wiley & Sons, 1998. — ISBN 9780471982326. Архівовано з джерела 14 червня 2020
11. Cohen, Henri. [6] — Springer Science & Business Media, 2013. — ISBN 9783662029459. Архівовано з джерела 28 вересня 2020
12. Kannan, R.; Bachem, A. Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix // SIAM Journal on Computing^[en] : journal. — 1979. — Vol. 8, no. 4, (11). — P. 499—507. — ISSN 0097-5397. — DOI:10.1137/0208040. Архівовано з джерела 6 травня 2021. Процитовано 25 березня 2021.
13. Euclidean Algorithm and Hermite Normal Form. 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. — Springer Science & Business Media, 2012. — ISBN 9781461549758.
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. — ISBN 9781439807040.
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 (23 January). — P. 130—131. — ISSN 1058-6458. Архівовано з джерела 22 червня 2020. Процитовано 25 березня 2021.
17. Micciancio, Daniele. Basic Algorithms (PDF). Архів оригіналу (PDF) за 27 грудня 2015. Процитовано 25 червня 2016.