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

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

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

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

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

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

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

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

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

${\displaystyle 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}}}$

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

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

• Howell J. A. Spans in the module (Z_m)^S (англ.) // Linear and Multilinear Algebra — Taylor & Francis, 1986. — Vol. 19, Iss. 1. — P. 67—77. — ISSN 0308-1087; 1026-7573; 1563-5139 — doi:10.1080/03081088608817705
• Storjohann A., Mulders T. Fast Algorithms for Linear Algebra Modulo N (англ.) // Lect. Notes Comput. Sci. / G. Goos, J. Hartmanis, J. v. Leeuwen — Berlin, Heidelberg, New York, NY, London [etc.]: Springer, 1998. — P. 139—150. — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-68530-8_12