Эрмитова нормальная форма

Эрмитова нормальная форма — это аналог ступенчатого вида матрицы для матриц над кольцом целых чисел. В то время, как ступенчатый вид матрицы используется для решения систем линейных уравнений вида для , эрмитова нормальная форма может быть использована для решения линейных систем диофантовых уравнений, в которых подразумевается, что . Эрмитова нормальная форма используется в решении задач целочисленного программирования[1], криптографии[2] и общей алгебры[3].

Определение

Матрица является эрмитовой нормальной формой целочисленной матрицы если есть унимодулярная матрица такая что и удовлетворяет следующим ограничениям[4][5][6]:

  1. является верхне-треугольной, то есть, если и любая строка, целиком состоящая из нулей находится ниже всех остальных.
  2. Ведущий элемент любой ненулевой строки всегда положителен и лежит правее ведущего коэффициента строки над ней.
  3. Элементы под ведущими равны нулю, а элементы над ведущими неотрицательны и строго меньше ведущего.

Некоторые авторы в третьем условии требуют, чтобы элементы были неположительными[7][8] или вообще не накладывают на них знаковых ограничений[9].

Существование и единственность эрмитовой нормальной формы

Эрмитова нормальная форма существует и единственна у любой целочисленной матрицы [5][10][11].

Примеры

В примерах ниже матрица является эрмитовой нормальной формой матрицы , а соответствующей унимодулярной матрицей является матрица такая что .

Алгоритмы

Первые алгоритмы вычисления эрмитовой нормальной формы датируются 1851 годом. При этом первый алгоритм, работающий за строго полиномиальное время был разработан лишь в 1979 году[12]. Один из широко используемых классов алгоритмов для приведения матрицы к эрмитовой нормальной форме основан на модифицированном методе Гаусса[10][13][14]. Другим распространённым методом вычисления эрмитовой нормальной формы является LLL-алгоритм[15][16].

Применения

Вычисления в решётках

Обычно решётки в имеют вид , где . Если рассмотреть матрицу , чьи строки составлены из векторов , то её эрмитова нормальная форма будет задавать некоторый единственным образом определённый базис решётки. Данное наблюдение позволяет быстро проверять, совпадают ли решётки, порождённые строками матриц и , для чего достаточно проверить, что у матриц совпадают их эрмитовы нормальные формы. Аналогичным образом можно проверить, является ли решётка подрешёткой решётки , для чего достаточно рассмотреть матрицу , полученную из объединения строк и . В такой постановке является подрешёткой если и только если совпадают эрмитовы нормальные формы и [17].

Диофантовы линейные уравнения

Система линейных уравнений имеет целочисленное решение если и только если система имеет целочисленное решение, где  — эрмитова нормальная форма матрицы [10]:55.

Реализация

Вычисление эрмитовой нормальной формы реализовано во многих системах компьютерной алгебры:

См. также

Примечания

  1. Hung, Ming S.; Rom, Walter O. An application of the Hermite normal form in integer programming (англ.) // Linear Algebra and its Applications : journal. — 1990. — 15 October (vol. 140). P. 163—179. doi:10.1016/0024-3795(90)90228-5.
  2. Evangelos, Tourloupis, Vasilios. Hermite normal forms and its cryptographic applications (англ.) : journal. — University of Wollongong, 2013. — 1 January.
  3. Adkins, William; Weintraub, Steven. Algebra: An Approach via Module Theory (англ.). Springer Science & Business Media, 2012. — P. 306. — ISBN 9781461209232.
  4. Dense matrices over the integer ring — Sage Reference Manual v7.2: Matrices and Spaces of Matrices. doc.sagemath.org. Дата обращения: 22 июня 2016.
  5. Mader, A. Almost Completely Decomposable Groups (англ.). CRC Press, 2000. — ISBN 9789056992255.
  6. Micciancio, Daniele; Goldwasser, Shafi. Complexity of Lattice Problems: A Cryptographic Perspective (англ.). Springer Science & Business Media, 2012. — ISBN 9781461508977.
  7. W., Weisstein, Eric Hermite Normal Form (англ.). mathworld.wolfram.com. Дата обращения: 22 июня 2016.
  8. 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.
  9. Hermite normal form of a matrix - MuPAD. www.mathworks.com. Дата обращения: 22 июня 2016.
  10. Schrijver, Alexander. Theory of Linear and Integer Programming (англ.). John Wiley & Sons, 1998. — ISBN 9780471982326.
  11. Cohen, Henri. A Course in Computational Algebraic Number Theory (англ.). Springer Science & Business Media, 2013. — ISBN 9783662029459.
  12. Kannan, R.; Bachem, A. Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix (англ.) // SIAM Journal on Computing : journal. — 1979. — 1 November (vol. 8, no. 4). P. 499—507. ISSN 0097-5397. doi:10.1137/0208040.
  13. Euclidean Algorithm and Hermite Normal Form (недоступная ссылка) (2 марта 2010). Дата обращения: 30 марта 2020. Архивировано 7 августа 2016 года.
  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. P. 130—131. ISSN 1058-6458.
  17. Micciancio, Daniele Basic Algorithms. Дата обращения: 25 июня 2016.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.