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

Определение

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

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

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

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

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

Примеры

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

${\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)}$

${\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)}$

Алгоритмы

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

Применения

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

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

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

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

Реализация

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

• в Maple
• в Mathematica
• в MATLAB
• в SageMath

См. также

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

Примечания