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

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

Определение

Пусть $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}}$ .

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

Пусть $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$ -й по $m$ -ю матрицы $A$ .

Свойства

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