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

Эрмитова нормальная форма — это аналог ступенчатого вида матрицы для матриц над кольцом $\mathbb{Z}$ целых чисел. В то время, как ступенчатый вид матрицы используется для решения систем линейных уравнений вида $Ax=b$ для $x\in {ℝ}^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=\left(\begin{array}{cccc}3& 3& 1& 4\\ 0& 1& 0& 0\\ 0& 0& 19& 16\\ 0& 0& 0& 3\end{array}\right)H=\left(\begin{array}{cccc}3& 0& 1& 1\\ 0& 1& 0& 0\\ 0& 0& 19& 1\\ 0& 0& 0& 3\end{array}\right)U=\left(\begin{array}{cccc}1& -3& 0& -1\\ 0& 1& 0& 0\\ 0& 0& 1& -5\\ 0& 0& 0& 1\end{array}\right)$

$A=\left(\begin{array}{cccc}2& 3& 6& 2\\ 5& 6& 1& 6\\ 8& 3& 1& 1\end{array}\right)H=\left(\begin{array}{cccc}1& 0& 50& -11\\ 0& 3& 28& -2\\ 0& 0& 61& -13\end{array}\right)U=\left(\begin{array}{ccc}9& -5& 1\\ 5& -2& 0\\ 11& -6& 1\end{array}\right)$

Алгоритмы

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

Применения

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

Обычно решётки в ${ℝ}^n$ имеют вид $L=\{{\alpha }_1{a}_1+{\alpha }_2{a}_2+\dots +{\alpha }_n{a}_n|{\alpha }_i\in \mathbb{Z}\}$, где $a_i\in {ℝ}^n$. Если рассмотреть матрицу $A$, чьи строки составлены из векторов $a_i$, то её эрмитова нормальная форма будет задавать некоторый единственным образом определённый базис решётки. Данное наблюдение позволяет быстро проверять, совпадают ли решётки, порождённые строками матриц $A$ и $A^{\prime }$, для чего достаточно проверить, что у матриц совпадают их эрмитовы нормальные формы. Аналогичным образом можно проверить, является ли решётка $L_{A^{\prime }}$ подрешёткой решётки $L_A$, для чего достаточно рассмотреть матрицу $A^{″}$, полученную из объединения строк $A$ и $A^{\prime }$. В такой постановке $L_{A^{\prime }}$ является подрешёткой $L_A$ если и только если совпадают эрмитовы нормальные формы $A$ и $A^{″}$.

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

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

Реализация

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

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

См. также

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