Перейти к содержанию

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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

Эрмитова нормальная форма — это аналог ступенчатого вида матрицы для матриц над кольцом [math]\displaystyle{ \Z }[/math] целых чисел. В то время, как ступенчатый вид матрицы используется для решения систем линейных уравнений вида [math]\displaystyle{ Ax=b }[/math] для [math]\displaystyle{ x \in \R^n }[/math], эрмитова нормальная форма может быть использована для решения линейных систем диофантовых уравнений, в которых подразумевается, что [math]\displaystyle{ x \in \Z^n }[/math]. Эрмитова нормальная форма используется в решении задач целочисленного программирования[1], криптографии[2] и общей алгебры[3].

Определение

Матрица [math]\displaystyle{ H }[/math] является эрмитовой нормальной формой целочисленной матрицы [math]\displaystyle{ A }[/math] если есть унимодулярная матрица [math]\displaystyle{ U }[/math] такая что [math]\displaystyle{ H = UA }[/math] и [math]\displaystyle{ H }[/math] удовлетворяет следующим ограничениям[4][5][6]:

  1. [math]\displaystyle{ H }[/math] является верхне-треугольной, то есть, [math]\displaystyle{ h_{ij}=0 }[/math] если [math]\displaystyle{ i \gt j }[/math] и любая строка, целиком состоящая из нулей находится ниже всех остальных.
  2. Ведущий элемент любой ненулевой строки всегда положителен и лежит правее ведущего коэффициента строки над ней.
  3. Элементы под ведущими равны нулю, а элементы над ведущими неотрицательны и строго меньше ведущего.

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

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

Эрмитова нормальная форма [math]\displaystyle{ H }[/math] существует и единственна у любой целочисленной матрицы [math]\displaystyle{ A }[/math][5][10][11].

Примеры

В примерах ниже матрица [math]\displaystyle{ H }[/math] является эрмитовой нормальной формой матрицы [math]\displaystyle{ A }[/math], а соответствующей унимодулярной матрицей является матрица [math]\displaystyle{ U }[/math] такая что [math]\displaystyle{ H = UA }[/math].

[math]\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) }[/math]

[math]\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) }[/math]

Алгоритмы

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

Применения

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

Обычно решётки в [math]\displaystyle{ \R^n }[/math] имеют вид [math]\displaystyle{ L = \left\{\left. \alpha_1 a_1 + \alpha_2 a_2 + \dots + \alpha_n a_n \; \right\vert \; \alpha_i \in\mathbb{Z} \right\} }[/math], где [math]\displaystyle{ a_i \in \R^n }[/math]. Если рассмотреть матрицу [math]\displaystyle{ A }[/math], чьи строки составлены из векторов [math]\displaystyle{ a_i }[/math], то её эрмитова нормальная форма будет задавать некоторый единственным образом определённый базис решётки. Данное наблюдение позволяет быстро проверять, совпадают ли решётки, порождённые строками матриц [math]\displaystyle{ A }[/math] и [math]\displaystyle{ A' }[/math], для чего достаточно проверить, что у матриц совпадают их эрмитовы нормальные формы. Аналогичным образом можно проверить, является ли решётка [math]\displaystyle{ L_{A'} }[/math] подрешёткой решётки [math]\displaystyle{ L_A }[/math], для чего достаточно рассмотреть матрицу [math]\displaystyle{ A'' }[/math], полученную из объединения строк [math]\displaystyle{ A }[/math] и [math]\displaystyle{ A' }[/math]. В такой постановке [math]\displaystyle{ L_{A'} }[/math] является подрешёткой [math]\displaystyle{ L_A }[/math] если и только если совпадают эрмитовы нормальные формы [math]\displaystyle{ A }[/math] и [math]\displaystyle{ A'' }[/math][17].

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

Система линейных уравнений [math]\displaystyle{ Ax=b }[/math] имеет целочисленное решение [math]\displaystyle{ x }[/math] если и только если система [math]\displaystyle{ Hx=Ub }[/math] имеет целочисленное решение, где [math]\displaystyle{ H=UA }[/math] — эрмитова нормальная форма матрицы [math]\displaystyle{ A }[/math][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. ↑ 5,0 5,1 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. ↑ 10,0 10,1 10,2 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). Дата обращения: 25 июня 2015. Архивировано 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.
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Эрмитова_нормальная_форма&oldid=5878447