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

В линейной алгебре , то Эрмита нормальная форма является аналогом восстановленной формы эшелона для матриц над целыми числами Z . Подобно тому, как сокращенная форма эшелона может использоваться для решения задач о решении линейной системы Ax = b, где x находится в R ⁿ , нормальная форма Эрмита может решать задачи о решении линейной системы Ax = b, где на этот раз x равно ограничены только целочисленными координатами. Другие приложения нормальной формы Эрмита включают целочисленное программирование , ^[1] криптографию., ^[2] и абстрактная алгебра . ^[3]

Определение [ править ]

Различные авторы могут предпочесть говорить о нормальной форме Эрмита либо в стиле строки, либо в стиле столбца. По сути, они одинаковы до транспонирования.

Строчная нормальная форма Эрмита [ править ]

М по п матрица А с целыми записями имеют (строку) Эрмит нормальной формы H , если есть квадрат унимодулярная матрица U , где Н = UA и Н имеют следующие ограничения: ^{[4] [5] [6]}

1. H является верхнетреугольным (то есть h _ij = 0 для i> j ), и любые строки нулей расположены ниже любой другой строки.
2. Старший коэффициент (первая запись отлична от нуля с левой стороны , также называют стержень ) ненулевым ряда всегда строго справа от старшего коэффициента ряда над ним; кроме того, это положительно.
3. Элементы под опорными точками равны нулю, а элементы над опорными точками неотрицательны и строго меньше, чем опорные.

Третье условие не является стандартным среди авторов, например, некоторые источники заставляют неповоротные диаграммы быть неположительными ^{[7] [8]} или не накладывают на них никаких ограничений по знакам. ^[9] Тем не менее, эти определения эквивалентны с помощью других унимодулярных матриц U . Унимодулярная матрица - это квадратная обратимая целочисленная матрица, определитель которой равен 1 или -1.

Столбчатая нормальная форма Эрмита [ править ]

Матрица A размером m на n с целыми элементами имеет (столбцовую) нормальную форму Эрмита H, если существует квадратная унимодулярная матрица U, где H = AU и H имеет следующие ограничения: ^{[8] [10]}

1. H - нижний треугольник, h _ij = 0 для i <j , а любые столбцы нулей расположены справа.
2. Старший коэффициент (первая запись отличны от нуля от вершины, которая также называется стержень ) колонок ненулевой всегда строго ниже ведущего коэффициент колонки перед ним; кроме того, это положительно.
3. Элементы справа от опорных точек равны нулю, а элементы слева от опорных точек неотрицательны и строго меньше точки опоры.

Обратите внимание , что определение строк стиля имеет унимодулярную матрицу U умножения А слева (то есть U действует на строках A ), в то время как определение столбца стиля имеет унимодулярную матрицу действие на столбцах A . Два определения нормальных форм Эрмита просто заменяют друг друга.

Существование и уникальность нормальной формы Эрмита [ править ]

Каждые м по п матрицы А с целыми записями имеют уникальные м по п матрица Н , такие , что Н = UA для некоторой квадратной матрицы унимодулярного U . ^{[5] [11] [12]}

Примеры [ править ]

В приведенных ниже примерах, Н Эрмита нормальная форма матрицы А , и U представляет собой унимодулярная матрица такая , что UA = H .

${\ 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 & 0 & 19 & 1 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)}$

Если A имеет только одну строку, то либо H = A, либо H = -A , в зависимости от того, имеет ли одна строка A положительный или отрицательный ведущий коэффициент.

Алгоритмы [ править ]

Существует множество алгоритмов для вычисления нормальной формы Эрмита, восходящих к 1851 году. Только в 1979 году был впервые разработан алгоритм для вычисления нормальной формы Эрмита, работающий за строго полиномиальное время ; ^[13], то есть количество шагов для вычисления нормальной формы Эрмита ограничено сверху полиномом от размеров входной матрицы, а пространство, используемое алгоритмом (промежуточные числа), ограничено полиномом в двоичном кодировании размер чисел во входной матрице. Один класс алгоритмов основан на методе исключения Гаусса, в котором многократно используются специальные элементарные матрицы. ^{[11] [14] [15]} LLLАлгоритм также может быть использован для эффективного вычисления нормальной формы Эрмита. ^{[16] [17]}

Приложения [ править ]

Расчеты решетки [ править ]

Типичная решетка в R ⁿ имеет вид, где a _i находятся в R ⁿ . Если столбцы матрицы А являются _я , решетка может быть связана с столбцами матрицы, и называется базис L . Поскольку нормальная форма Эрмита уникальна, ее можно использовать для ответа на многие вопросы о двух решеточных описаниях. В дальнейшем, обозначает решетку, порожденную столбцами матрицы A. Поскольку базис находится в столбцах матрицы A${\displaystyle L=\left\{\left.\sum _{i=1}^{n}\alpha _{i}a_{i}\;\right\vert \;\alpha _{i}\in \mathbb {Z} \right\}}$${\displaystyle L_{A}}$, должна использоваться нормальная форма Эрмита в виде столбцов. Учитывая два основания решетки, A и A ' , проблема эквивалентности состоит в том, чтобы решить, можно ли это сделать, проверив, совпадают ли нормальные формы Эрмита в стиле столбцов для A и A' вплоть до добавления нулевых столбцов. Эта стратегия также полезна для принятия решения о том, является ли решетка подмножеством ( если и только если ), определения того, находится ли вектор v в решетке ( если и только если ), и для других вычислений. ^[18]${\displaystyle L_{A}=L_{A'}.}$${\displaystyle L_{A}\subseteq L_{A'}}$${\displaystyle L_{[A\mid A']}=L_{A'}}$${\displaystyle v\in L_{A}}$${\displaystyle L_{[v\mid A]}=L_{A}}$

Целочисленные решения линейных систем [ править ]

Линейная система Ах = Ь имеет решение целого х тогда и только тогда , когда система Hy = Ь имеет целочисленное решение у , где у = Ux и Н является колонным типом Эрмита нормальной формы А . ^{[11] : 55} Проверить, что Hy = b имеет целочисленное решение, проще, чем Ax = b, потому что матрица H треугольная.

Реализации [ править ]

Многие пакеты математических программ могут вычислить нормальную форму Эрмита:

• Клен с HermiteForm
• Mathematica с HermiteDecomposition
• MATLAB с hermiteForm
• NTL с HNF
• PARI / GP с mathnf
• SageMath с hermite_form

См. Также [ править ]

• Кольцо Hermite
• Нормальная форма Смита
• Диофантово уравнение

Ссылки [ править ]