Хауэлл нормальная форма

В линейной алгебре и теории колец нормальная форма Хауэлла является обобщением ступенчатой ​​формы матрицы над $\mathbb {Z} _{N}$, кольцо целых чисел по модулю N . Промежутки строк двух матриц согласуются тогда и только тогда, когда их нормальные формы Хауэлла согласуются. Нормальная форма Хауэлла обобщает нормальную форму Эрмита , которая определена для матриц над $\mathbb {Z}$.

Определение

Матрица $A\in \mathbb {Z} _{N}^{n\times m}$ над $\mathbb {Z} _{N}$ называется находящимся в форме эшелона строк, если он имеет следующие свойства:

• Позволять $r$ быть числом ненулевых строк $A$. Тогда самый верхний $r$ строки матрицы ненулевые,
• Для $1\leq i\leq r$, позволять $j_{i}$ быть индексом самого левого ненулевого элемента в строке $i$. Затем $j_{1}<j_{2}<\dots <j_{r}$.

С помощью элементарных преобразований каждую матрицу в форме эшелона строк можно уменьшить таким образом, чтобы сохранялись следующие свойства:

• Для каждого $1\leq i\leq r$, ведущий элемент $A_{ij_{i}}$ является делителем $N$,
• Для каждого $1\leq k<i\leq r$ он утверждает, что $0\leq A_{kj_{i}}<A_{ij_{i}}$.

Если $A$ соответствует обоим вышеперечисленным свойствам, говорят, что он находится в форме сокращенного эшелона строк .

Если $A$ обладает следующим дополнительным свойством, то говорят, что он находится в нормальной форме Хауэлла ( $S(A)$ обозначает диапазон строк $A$):

• позволять $v\in S(A)$ быть элементом диапазона строк $A$, такой, что $v_{k}=0$ для каждого $1\leq k<j_{i}$. Затем $v\in S(A_{i\dots m})$, где $A_{i\dots m}$ — матрица, полученная из строк из $i$-th к $m$-я матрица $A$.

Свойства

Для каждой матрицы $A$ над $\mathbb {Z} _{N}$, существует уникальная матрица $H$ в нормальной форме Хауэлла, такой, что $S(A)=S(H)$. Матрица $H$ можно получить из матрицы $A$ посредством последовательности элементарных преобразований.

Отсюда следует, что для двух матриц $A,B\in \mathbb {Z} _{N}^{n\times m}$ над $\mathbb {Z} _{N}$, их промежутки строк равны тогда и только тогда, когда их нормальные формы Хауэлла равны.

Например, матрицы

$A={\begin{bmatrix}4&1&0\\0&0&5\\0&0&0\end{bmatrix}},\;\;\;B={\begin{bmatrix}8&5&5\\0&9&8\\0&0&10\end{bmatrix}}$

имеют ту же нормальную форму Хауэлла над $\mathbb {Z} _{12}$:

$H={\begin{bmatrix}4&1&0\\0&3&0\\0&0&1\end{bmatrix}}.$

Обратите внимание, что $A$ и $B$ представляют собой две разные матрицы в форме эшелона строк, что означает, что их диапазон одинаков, если они рассматриваются как матрицы по некоторому полю. Более того, они находятся в нормальной форме Эрмита , а это означает, что их диапазон строк также одинаков, если они считаются более чем $\mathbb {Z}$, кольцо целых чисел .

Однако, $\mathbb {Z} _{12}$ не является полем, и в общих кольцах иногда можно обнулить ось строки, умножив строку на скаляр, не обнуляя всю строку. В данном конкретном случае

$3\cdot {\begin{bmatrix}4&1&0\end{bmatrix}}\equiv {\begin{bmatrix}0&3&0\end{bmatrix}}{\pmod {12}}.$

Это подразумевает ${\begin{bmatrix}0&3&0\end{bmatrix}}\in S(A)$, что неверно для любого поля или целых чисел.

Ссылки

Библиография

• Джон А. Хауэлл (апрель 1986 г.). «Пролеты в модуле (Z_m)^S». Линейная и полилинейная алгебра . 19 (1): 67–77. дои : 10.1080/03081088608817705 . ISSN   0308-1087 . Збл   0596.15013 . Викиданные   Q110879587 .
• Арне Сторйоханн; Том Малдерс (24 августа 1998 г.). «Быстрые алгоритмы линейной алгебры по модулю N». Конспекты лекций по информатике : 139–150. дои : 10.1007/3-540-68530-8_12 . ISSN   0302-9743 . Викиданные   Q110879586 .
• Жан-Франсуа Биас; Клаус Фикер; Томми Хофманн (май 2017 г.). «О вычислении ФНФ модуля над кольцом целых числовых полей». Журнал символических вычислений . 80 : 581–615. arXiv : 1612.09428 . дои : 10.1016/J.JSC.2016.07.027 . ISSN   0747-7171 . Збл   1403.11084 . Викиданные   Q110883424 .