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

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

Определение

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

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

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

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

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

Примеры

В примерах ниже матрица ${\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 году^[12]. Один из широко используемых классов алгоритмов для приведения матрицы к эрмитовой нормальной форме основан на модифицированном методе Гаусса^[10][13][14]. Другим распространённым методом вычисления эрмитовой нормальной формы является LLL-алгоритм^[15][16].

Применения

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

Обычно решётки в ${\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''}$^[17].

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

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

Реализация

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

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

См. также

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