Ермітова нормальна форма
Ермітова нормальна форма — це аналог ступінчастого вигляду матриці для матриць над кільцем цілих чисел. Тоді як ступінчастий вигляд матриці використовується для розв'язання систем лінійних рівнянь виду для , ермітову нормальну форму можна використати для розв'язання лінійних систем діофантових рівнянь, у яких мається на увазі, що . Ермітова нормальна форма використовується у розв'язанні задач цілочисельного програмування[1], криптографії[2] і загальної алгебри[3].
Визначення
Матриця є ермітовою нормальною формою цілочисельної матриці якщо є унімодулярна матриця така що і задовольняє таким вимогам[4][5][6]:
- є верхньо-трикутною, тобто, якщо і будь-який рядок, що цілком складається з нулів, лежить нижче від всіх інших.
- Ведучий елемент будь-якого ненульового рядка завжди додатний і лежить правіше від ведучого коефіцієнта рядка над ним.
- Елементи під ведучими дорівнюють нулю, а елементи над ведучими невід'ємні і строго менші від ведучого.
Деякі автори в третій умові вимагають, щоб елементи були недодатними[7][8] або взагалі не накладають на них знакових обмежень[9].
Існування та єдиність ермітової нормальної форми
Ермітова нормальна форма існує і єдина для будь-якої цілочисельної матриці [5][10][11].
Приклади
У прикладах нижче матриця є ермітовою нормальною формою матриці , а відповідною унімодулярною матрицею є матриця така що .
Алгоритми
Перші алгоритми обчислення ермітової нормальної форми датуються 1851 роком. При цьому перший алгоритм, що працює за строго поліноміальний час, розроблено лише 1979 року[12]. Один із широко використовуваних класів алгоритмів для зведення матриці до ермітової нормальної форми ґрунтується на модифікованому методі Гауса[10][13][14]. Іншим поширеним методом обчислення ермітової нормальної форми є LLL-алгоритм[ru][15][16].
Застосування
Обчислення в ґратках
Зазвичай ґратки в мають вигляд , де . Якщо розглянути матрицю , чиї рядки складені із векторів , то її ермітова нормальна форма задаватиме деякий єдиним чином визначений базис ґратки. Це спостереження дозволяє швидко перевіряти, чи збігаються ґратки, породжені рядками матриць і , для чого достатньо перевірити, що в матриць збігаються їхні ермітові нормальні форми. Аналогічно можна перевірити, чи є ґратка підґраткою ґратки , для чого достатньо розглянути матрицю , отриману з об'єднання рядків і . У такій постановці є підґраткою якщо і тільки якщо збігаються ермітові нормальні форми і [17].
Лінійні діофантові рівняння
Система лінійних рівнянь має цілочисельний розв'язок , якщо і тільки якщо система має цілочисельний розв'язок, де — ермітова нормальна форма матриці [10] .
Реалізація
Обчислення ермітової нормальної форми реалізовано в багатьох системах комп'ютерної алгебри:
- HermiteForm в Maple
- HermiteDecomposition в Mathematica
- hermiteForm в MATLAB
- hermite_form в SageMath[ru]
Див. також
Примітки
- ↑ 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: .
- ↑ Evangelos, Tourloupis, Vasilios. Hermite normal forms and its cryptographic applications. — University of Wollongong, 2013. — . — 1.
- ↑ Adkins, William; Weintraub, Steven. Algebra: An Approach via Module Theory. — Springer Science & Business Media, 2012. — С. 306. — ISBN 9781461209232.
- ↑ Dense matrices over the integer ring — Sage Reference Manual v7.2: Matrices and Spaces of Matrices. doc.sagemath.org. Процитовано 22 червня 2016.
- ↑ а б Mader, A. Almost Completely Decomposable Groups. — CRC Press, 2000. — ISBN 9789056992255.
- ↑ Micciancio, Daniele; Goldwasser, Shafi. Complexity of Lattice Problems: A Cryptographic Perspective. — Springer Science & Business Media, 2012. — ISBN 9781461508977.
- ↑ W., Weisstein, Eric. Hermite Normal Form. mathworld.wolfram.com (англ.). Процитовано 22 червня 2016.
- ↑ Bouajjani, Ahmed; Maler, Oded. Computer Aided Verification: 21st International Conference, CAV 2009, Grenoble, France, June 26 - July 2, 2009, Proceedings. — Springer Science & Business Media, 2009. — ISBN 9783642026577.
- ↑ Hermite normal form of a matrix - MuPAD. www.mathworks.com. Процитовано 22 червня 2016.
- ↑ а б в Schrijver, Alexander. Theory of Linear and Integer Programming. — John Wiley & Sons, 1998. — ISBN 9780471982326.
- ↑ Cohen, Henri. A Course in Computational Algebraic Number Theory. — Springer Science & Business Media, 2013. — ISBN 9783662029459.
- ↑ 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: .
- ↑ Euclidean Algorithm and Hermite Normal Form. 2 березня 2010. Архів оригіналу за 7 серпня 2016. Процитовано 30 березня 2020.
- ↑ 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.
- ↑ 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.
- ↑ 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 (26 August). — P. 130—131. — ISSN 1058-6458.
- ↑ Micciancio, Daniele. Basic Algorithms (PDF). Процитовано 25 червня 2016.