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

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

Определение

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

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

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

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

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

Примеры

В примерах ниже матрица $H$ является эрмитовой нормальной формой матрицы $A$, а соответствующей унимодулярной матрицей является матрица $U$ такая что $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}$ имеют вид ${\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 \mathbb {R} ^{n}$. Если рассмотреть матрицу $A$, чьи строки составлены из векторов $a_{i}$, то её эрмитова нормальная форма будет задавать некоторый единственным образом определённый базис решётки. Данное наблюдение позволяет быстро проверять, совпадают ли решётки, порождённые строками матриц $A$ и $A'$, для чего достаточно проверить, что у матриц совпадают их эрмитовы нормальные формы. Аналогичным образом можно проверить, является ли решётка $L_{A'}$ подрешёткой решётки $L_{A}$, для чего достаточно рассмотреть матрицу $A''$, полученную из объединения строк $A$ и $A'$. В такой постановке $L_{A'}$ является подрешёткой $L_{A}$ если и только если совпадают эрмитовы нормальные формы $A$ и $A''$.

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

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

Реализация

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

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

См. также

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