Русская Википедия:Эрмитова нормальная форма
Эрмитова нормальная форма — это аналог ступенчатого вида матрицы для матриц над кольцом <math>\Z</math> целых чисел. В то время, как ступенчатый вид матрицы используется для решения систем линейных уравнений вида <math>Ax=b</math> для <math>x \in \R^n</math>, эрмитова нормальная форма может быть использована для решения линейных систем диофантовых уравнений, в которых подразумевается, что <math>x \in \Z^n</math>. Эрмитова нормальная форма используется в решении задач целочисленного программирования[1], криптографии[2] и общей алгебры[3].
Определение
Матрица <math>H</math> является эрмитовой нормальной формой целочисленной матрицы <math>A</math> если есть унимодулярная матрица <math>U</math> такая что <math>H = UA</math> и <math>H</math> удовлетворяет следующим ограничениям[4][5][6]:
- <math>H</math> является верхне-треугольной, то есть, <math>h_{ij}=0</math> если <math>i > j</math> и любая строка, целиком состоящая из нулей находится ниже всех остальных.
- Ведущий элемент любой ненулевой строки всегда положителен и лежит правее ведущего коэффициента строки над ней.
- Элементы под ведущими равны нулю, а элементы над ведущими неотрицательны и строго меньше ведущего.
Некоторые авторы в третьем условии требуют, чтобы элементы были неположительными[7][8] или вообще не накладывают на них знаковых ограничений[9].
Существование и единственность эрмитовой нормальной формы
Эрмитова нормальная форма <math>H</math> существует и единственна у любой целочисленной матрицы <math>A</math>[5][10][11].
Примеры
В примерах ниже матрица <math>H</math> является эрмитовой нормальной формой матрицы <math>A</math>, а соответствующей унимодулярной матрицей является матрица <math>U</math> такая что <math>H = UA</math>.
- <math>
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) </math>
<math> 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) </math>
Алгоритмы
Первые алгоритмы вычисления эрмитовой нормальной формы датируются 1851 годом. При этом первый алгоритм, работающий за строго полиномиальное время был разработан лишь в 1979 году[12]. Один из широко используемых классов алгоритмов для приведения матрицы к эрмитовой нормальной форме основан на модифицированном методе Гаусса[10][13][14]. Другим распространённым методом вычисления эрмитовой нормальной формы является LLL-алгоритм[15][16].
Применения
Вычисления в решётках
Обычно решётки в <math>\R^n</math> имеют вид <math display="inline"> L = \left\{\left. \alpha_1 a_1 + \alpha_2 a_2 + \dots + \alpha_n a_n \; \right\vert \; \alpha_i \in\mathbb{Z} \right\} </math>, где <math>a_i \in \R^n</math>. Если рассмотреть матрицу <math>A</math>, чьи строки составлены из векторов <math>a_i</math>, то её эрмитова нормальная форма будет задавать некоторый единственным образом определённый базис решётки. Данное наблюдение позволяет быстро проверять, совпадают ли решётки, порождённые строками матриц <math>A</math> и <math>A'</math>, для чего достаточно проверить, что у матриц совпадают их эрмитовы нормальные формы. Аналогичным образом можно проверить, является ли решётка <math>L_{A'}</math> подрешёткой решётки <math>L_A</math>, для чего достаточно рассмотреть матрицу <math>A</math>, полученную из объединения строк <math>A</math> и <math>A'</math>. В такой постановке <math>L_{A'}</math> является подрешёткой <math>L_A</math> если и только если совпадают эрмитовы нормальные формы <math>A</math> и <math>A</math>[17].
Диофантовы линейные уравнения
Система линейных уравнений <math>Ax=b</math> имеет целочисленное решение <math>x</math> если и только если система <math>Hx=Ub</math> имеет целочисленное решение, где <math>H=UA</math> — эрмитова нормальная форма матрицы <math>A</math>[10]Шаблон:Rp.
Реализация
Вычисление эрмитовой нормальной формы реализовано во многих системах компьютерной алгебры:
См. также
Примечания
