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

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

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

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

Нормальная форма Эрмита стиле строки в

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

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

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

Нормальная форма Эрмита в стиле колонны [ править ]

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

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

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

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

Каждая полная ранга m - n матрица с целочисленными элементами имеет уникальную m размером - n матрицу H в нормальной форме Эрмита, такую, что H = UA для некоторой квадратной унимодулярной матрицы U . ^[5]^[11]^[12]

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

В примерах ниже $H$ — нормальная форма Эрмита матрицы $A$ , а $U$ унимодулярная матрица такая, что $UA = H.$ —

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)

A={\begin{pmatrix}2&3&6&2\\5&6&1&6\\8&3&1&1\end{pmatrix}}\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 года. Один из таких алгоритмов описан в . ^[13]^: 43--45 алгоритм вычисления нормальной формы Эрмита, работавший за сильно полиномиальное время ; Но только в 1979 году был впервые разработан ^[14] то есть количество шагов для вычисления нормальной формы Эрмита ограничено сверху полиномом от размеров входной матрицы, а пространство, используемое алгоритмом (промежуточные числа), ограничено полиномом от размера двоичного кодирования числа во входной матрице.

Один класс алгоритмов основан на методе исключения Гаусса , в котором повторно используются специальные элементарные матрицы. ^[11]^[15]^[16] Алгоритм LLL также можно использовать для эффективного вычисления нормальной формы Эрмита. ^[17]^[18]

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

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

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

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

Линейная система $Ax = b$ имеет целочисленное решение $x$ тогда и только тогда, когда система $Hy = b$ имеет целочисленное решение $y$ , где $y = U -1 x$ и $H$ в виде столбца $— нормальная форма Эрмита A$ . Проверить, что $Hy = b$ имеет целочисленное решение, проще, чем $Ax = b,$ поскольку матрица $H$ треугольная. ^[11]^: 55

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

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

По произвольному домену Дедекинда [ править ]

Нормальную форму Эрмита можно определить, заменив Z произвольной дедекиндовой областью . ^[20] (например, любой принципиально-идеальный домен ). Например, в теории управления может быть полезно рассмотреть нормальную форму Эрмита для многочленов $F [x]$ над заданным полем $F$ .

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

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

^ Хунг, Мин С.; Ром, Уолтер О. (15 октября 1990 г.). «Применение нормальной формы Эрмита в целочисленном программировании» . Линейная алгебра и ее приложения . 140 : 163–179. дои : 10.1016/0024-3795(90)90228-5 .
^ Евангелос, Турлупи, Василиос (01 января 2013 г.). «Эрмитские нормальные формы и их криптографические приложения» . Сборник диссертаций Университета Вуллонгонга, 1954–2016 гг . Университет Вуллонгонга. {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Адкинс, Уильям; Вайнтрауб, Стивен (6 декабря 2012 г.). Алгебра: подход через теорию модулей . Springer Science & Business Media. п. 306. ИСБН 9781461209232 .
^ «Плотные матрицы над целочисленным кольцом — Справочное руководство Sage v7.2: Матрицы и пространства матриц» . doc.sagemath.org . Проверено 22 июня 2016 г.
^ Jump up to: ^а ^б Мадер, А. (9 марта 2000 г.). Почти вполне разложимые группы . ЦРК Пресс. ISBN 9789056992255 .
^ Миччанчо, Даниэле; Гольдвассер, Шафи (6 декабря 2012 г.). Сложность решеточных задач: криптографическая перспектива . Springer Science & Business Media. ISBN 9781461508977 .
^ Вайсштейн, Эрик В. «Нормальная форма Эрмита» . mathworld.wolfram.com . Проверено 22 июня 2016 г.
^ Jump up to: ^а ^б Буаджани, Ахмед; Малер, Одед (19 июня 2009 г.). Компьютерная проверка: 21-я Международная конференция, CAV 2009, Гренобль, Франция, 26 июня – 2 июля 2009 г., Материалы . Springer Science & Business Media. ISBN 9783642026577 .
^ "Эрмитская нормальная форма матрицы - МуПАД" . www.mathworks.com . Проверено 22 июня 2016 г.
^ Мартин, Ричард Кипп (6 декабря 2012 г.). Крупномасштабная линейная и целочисленная оптимизация: унифицированный подход . Springer Science & Business Media. ISBN 9781461549758 .
^ Jump up to: ^а ^б ^с Шрийвер, Александр (7 июля 1998 г.). Теория линейного и целочисленного программирования . Джон Уайли и сыновья. ISBN 9780471982326 .
^ Коэн, Анри (17 апреля 2013 г.). Курс вычислительной алгебраической теории чисел . Springer Science & Business Media. ISBN 9783662029459 .
^ Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN. 978-3-642-78242-8 , МР 1261419
^ Каннан, Р.; Бахем, А. (1 ноября 1979 г.). «Полиномиальные алгоритмы для вычисления нормальных форм Смита и Эрмита целочисленной матрицы» (PDF) . SIAM Journal по вычислительной технике . 8 (4): 499–507. дои : 10.1137/0208040 . ISSN 0097-5397 .
^ «Алгоритм Евклида и нормальная форма Эрмита» . 2 марта 2010 г. Архивировано из оригинала 7 августа 2016 г. . Проверено 25 июня 2015 г.
^ Мартин, Ричард Кипп (6 декабря 2012 г.). «Глава 4.2.4 Нормальная форма Эрмита» . Крупномасштабная линейная и целочисленная оптимизация: унифицированный подход . Springer Science & Business Media. ISBN 9781461549758 .
^ Бремнер, Мюррей Р. (12 августа 2011 г.). «Глава 14: Нормальная форма Эрмита» . Редукция решеточного базиса: введение в алгоритм LLL и его приложения . ЦРК Пресс. ISBN 9781439807040 .
^ Хавас, Джордж; Маевский, Богдан С.; Мэтьюз, Кейт Р. (1998). «Расширенные алгоритмы НОД и нормальной формы Эрмита посредством редукции базиса решетки» . Экспериментальная математика . 7 (2): 130–131. дои : 10.1080/10586458.1998.10504362 . ISSN 1058-6458 . S2CID 263873475 .
^ Миччанчо, Даниэле. «Основные алгоритмы» (PDF) . Проверено 25 июня 2016 г.
^ Коэн, Анри (1999). Продвинутые темы вычислительной теории чисел . Спрингер. §1.4.2. ISBN 0-387-98727-4 .

[1] Хунг, Мин С.; Ром, Уолтер О. (15 октября 1990 г.). «Применение нормальной формы Эрмита в целочисленном программировании» . Линейная алгебра и ее приложения . 140 : 163–179. дои : 10.1016/0024-3795(90)90228-5 .

[2] Евангелос, Турлупи, Василиос (01 января 2013 г.). «Эрмитские нормальные формы и их криптографические приложения» . Сборник диссертаций Университета Вуллонгонга, 1954–2016 гг . Университет Вуллонгонга. {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

[3] Адкинс, Уильям; Вайнтрауб, Стивен (6 декабря 2012 г.). Алгебра: подход через теорию модулей . Springer Science & Business Media. п. 306. ИСБН 9781461209232 .

[4] «Плотные матрицы над целочисленным кольцом — Справочное руководство Sage v7.2: Матрицы и пространства матриц» . doc.sagemath.org . Проверено 22 июня 2016 г.

[:1-5] Jump up to: ^а ^б Мадер, А. (9 марта 2000 г.). Почти вполне разложимые группы . ЦРК Пресс. ISBN 9789056992255 .

[6] Миччанчо, Даниэле; Гольдвассер, Шафи (6 декабря 2012 г.). Сложность решеточных задач: криптографическая перспектива . Springer Science & Business Media. ISBN 9781461508977 .

[7] Вайсштейн, Эрик В. «Нормальная форма Эрмита» . mathworld.wolfram.com . Проверено 22 июня 2016 г.

[:0-8] Jump up to: ^а ^б Буаджани, Ахмед; Малер, Одед (19 июня 2009 г.). Компьютерная проверка: 21-я Международная конференция, CAV 2009, Гренобль, Франция, 26 июня – 2 июля 2009 г., Материалы . Springer Science & Business Media. ISBN 9783642026577 .

[9] "Эрмитская нормальная форма матрицы - МуПАД" . www.mathworks.com . Проверено 22 июня 2016 г.

[10] Мартин, Ричард Кипп (6 декабря 2012 г.). Крупномасштабная линейная и целочисленная оптимизация: унифицированный подход . Springer Science & Business Media. ISBN 9781461549758 .

[:3-11] Jump up to: ^а ^б ^с Шрийвер, Александр (7 июля 1998 г.). Теория линейного и целочисленного программирования . Джон Уайли и сыновья. ISBN 9780471982326 .

[:2-12] Коэн, Анри (17 апреля 2013 г.). Курс вычислительной алгебраической теории чисел . Springer Science & Business Media. ISBN 9783662029459 .

[:02-13] Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN. 978-3-642-78242-8 , МР 1261419

[14] Каннан, Р.; Бахем, А. (1 ноября 1979 г.). «Полиномиальные алгоритмы для вычисления нормальных форм Смита и Эрмита целочисленной матрицы» (PDF) . SIAM Journal по вычислительной технике . 8 (4): 499–507. дои : 10.1137/0208040 . ISSN 0097-5397 .

[15] «Алгоритм Евклида и нормальная форма Эрмита» . 2 марта 2010 г. Архивировано из оригинала 7 августа 2016 г. . Проверено 25 июня 2015 г.

[16] Мартин, Ричард Кипп (6 декабря 2012 г.). «Глава 4.2.4 Нормальная форма Эрмита» . Крупномасштабная линейная и целочисленная оптимизация: унифицированный подход . Springer Science & Business Media. ISBN 9781461549758 .

[17] Бремнер, Мюррей Р. (12 августа 2011 г.). «Глава 14: Нормальная форма Эрмита» . Редукция решеточного базиса: введение в алгоритм LLL и его приложения . ЦРК Пресс. ISBN 9781439807040 .

[18] Хавас, Джордж; Маевский, Богдан С.; Мэтьюз, Кейт Р. (1998). «Расширенные алгоритмы НОД и нормальной формы Эрмита посредством редукции базиса решетки» . Экспериментальная математика . 7 (2): 130–131. дои : 10.1080/10586458.1998.10504362 . ISSN 1058-6458 . S2CID 263873475 .

[19] Миччанчо, Даниэле. «Основные алгоритмы» (PDF) . Проверено 25 июня 2016 г.

[20] Коэн, Анри (1999). Продвинутые темы вычислительной теории чисел . Спрингер. §1.4.2. ISBN 0-387-98727-4 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]