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

Нормальная форма Хауэлла — аналог ступенчатого вида матрицы для матриц над кольцом ${\mathbb{Z}}_N$ остатков по модулю $N$.

Определение

Пусть $A\in {\mathbb{Z}}_N^{n\times m}$ — матрица над ${\mathbb{Z}}_N$. Матрица находится в ступенчатом виде если она удовлетворяет следующим условиям:

• Пусть $r$ — число ненулевых строк $A$. Тогда первые $r$ строк матрицы ненулевые,
• Для $1\le i\le r$, пусть $j_i$ — индекс первого ненулевого элемента в строке $i$. Тогда $j_1<j_2<\dots <j_r$.

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

• Для любого $1\le i\le r$, ведущий элемент $A_{i{j}_i}$ делит $N$ нацело,
• Для любых $1\le k<i\le r$ выполнено $0\le A_{k{j}_i}<A_{i{j}_i}$.

Про матрицу, удовлетворяющую условиям выше говорят, что она находится в приведённом ступенчатом виде.

Пусть $S(A)$ — линейная оболочка строк матрицы $A$. Матрица в приведённой ступенчатом виде находится в нормальной форме Хауэлла, если дополнительно выполнено следующее условие:

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

Свойства

Пусть $A,B\in {\mathbb{Z}}_N^{n\times m}$ — матрицы над ${\mathbb{Z}}_N$. Линейные оболочки их строк совпадают если и только если совпадают их нормальные формы Хауэлла. Например, для матриц

$A=\left[\begin{array}{ccc}4& 1& 0\\ 0& 0& 5\\ 0& 0& 0\end{array}\right],B=\left[\begin{array}{ccc}8& 5& 5\\ 0& 9& 8\\ 0& 0& 10\end{array}\right]$

над ${\mathbb{Z}}_{12}$, их нормальная форма Хауэлла совпадает и имеет вид

$H=\left[\begin{array}{ccc}4& 1& 0\\ 0& 3& 0\\ 0& 0& 1\end{array}\right].$

Литература

• Шаблон:Cite Q
• Шаблон:Cite Q