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

Эрмитова нормальная форма — это аналог ступенчатого вида матрицы для матриц над кольцом $\mathbb{Z}$$\mathbb {Z}$ целых чисел. В то время, как ступенчатый вид матрицы используется для решения систем линейных уравнений вида $Ax=b$$Ax=b$ для $x\in <!--\; \in \; -->{\mathbb{R}}^n$$x\in \mathbb{R} ^{n}$, эрмитова нормальная форма может быть использована для решения линейных систем диофантовых уравнений, в которых подразумевается, что $x\in <!--\; \in \; -->{\mathbb{Z}}^n$$x\in \mathbb {Z} ^{n}$. Эрмитова нормальная форма используется в решении задач целочисленного программирования, криптографии и общей алгебры.

ОпределениеПравить

Матрица $H$$H$  является эрмитовой нормальной формой целочисленной матрицы $A$$A$  если есть унимодулярная матрица $U$$U$  такая что $H=UA$$H=UA$  и $H$$H$  удовлетворяет следующим ограничениям:

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

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

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

Эрмитова нормальная форма $H$$H$  существует и единственна у любой целочисленной матрицы $A$$A$ .

ПримерыПравить

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

$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)$ 

$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 году. Один из широко используемых классов алгоритмов для приведения матрицы к эрмитовой нормальной форме основан на модифицированном методе Гаусса. Другим распространённым методом вычисления эрмитовой нормальной формы является LLL-алгоритм.

ПримененияПравить

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

Обычно решётки в ${\mathbb{R}}^n$$\mathbb {R} ^{n}$  имеют вид $L=\left\{{\mathrm{\alpha <!--\; \alpha \; -->}}_1{a}_1+{\mathrm{\alpha <!--\; \alpha \; -->}}_2{a}_2+\cdots <!--\; \cdots \; -->+{\mathrm{\alpha <!--\; \alpha \; -->}}_n{a}_n|{\mathrm{\alpha <!--\; \alpha \; -->}}_i\in <!--\; \in \; -->\mathbb{Z}\right\}$${\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\}}$ , где $a_i\in <!--\; \in \; -->{\mathbb{R}}^n$$a_{i}\in \mathbb {R} ^{n}$ . Если рассмотреть матрицу $A$$A$ , чьи строки составлены из векторов $a_i$$a_{i}$ , то её эрмитова нормальная форма будет задавать некоторый единственным образом определённый базис решётки. Данное наблюдение позволяет быстро проверять, совпадают ли решётки, порождённые строками матриц $A$$A$  и $A^{\prime }$$A'$ , для чего достаточно проверить, что у матриц совпадают их эрмитовы нормальные формы. Аналогичным образом можно проверить, является ли решётка $L_{A^{\prime }}$$L_{A'}$  подрешёткой решётки $L_A$$L_{A}$ , для чего достаточно рассмотреть матрицу $A^{″}$$A''$ , полученную из объединения строк $A$$A$  и $A^{\prime }$$A'$ . В такой постановке $L_{A^{\prime }}$$L_{A'}$  является подрешёткой $L_A$$L_{A}$  если и только если совпадают эрмитовы нормальные формы $A$$A$  и $A^{″}$$A''$ .

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

Система линейных уравнений $Ax=b$$Ax=b$  имеет целочисленное решение $x$$x$  если и только если система $Hx=Ub$$Hx=Ub$  имеет целочисленное решение, где $H=UA$$H=UA$  — эрмитова нормальная форма матрицы $A$$A$ .

РеализацияПравить

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

• HermiteForm в Maple
• HermiteDecomposition в Mathematica
• hermiteForm в MATLAB
• hermite_form в SageMath

См. такжеПравить

• Нормальная форма Смита
• Нормальная форма Хауэлла
• Диофантово уравнение