Howell normal form

In linear algebra and ring theory, the Howell normal form is a generalization of the row echelon form of a matrix over $\mathbb {Z} _{N}$, the ring of integers modulo N. The row spans of two matrices agree if, and only if, their Howell normal forms agree. The Howell normal form generalizes the Hermite normal form, which is defined for matrices over $\mathbb {Z}$.

Definition

A matrix $A\in \mathbb {Z} _{N}^{n\times m}$ over $\mathbb {Z} _{N}$ is called to be in row echelon form if it has the following properties:

• Let $r$ be the number of non-zero rows of $A$. Then the topmost $r$ rows of the matrix are non-zero,
• For $1\leq i\leq r$, let $j_{i}$ be the index of the leftmost non-zero element in the row $i$. Then $j_{1}<j_{2}<\dots <j_{r}$.

With elementary transforms, each matrix in the row echelon form can be reduced in a way that the following properties will hold:

• For each $1\leq i\leq r$, the leading element $A_{ij_{i}}$ is a divisor of $N$,
• For each $1\leq k<i\leq r$ it holds that $0\leq A_{kj_{i}}<A_{ij_{i}}$.

If $A$ adheres to both above properties, it is said to be in reduced row echelon form.

If $A$ adheres to the following additional property, it is said to be in Howell normal form ($S(A)$ denotes the row span of $A$):

• let $v\in S(A)$ be an element of the row span of $A$, such that $v_{k}=0$ for each $1\leq k<j_{i}$. Then $v\in S(A_{i\dots m})$, where $A_{i\dots m}$ is the matrix obtained of rows from $i$-th to $m$-th of the matrix $A$.

Properties

For every matrix $A$ over $\mathbb {Z} _{N}$, there is a unique matrix $H$ in the Howell normal form, such that $S(A)=S(H)$. The matrix $H$ can be obtained from matrix $A$ via a sequence of elementary transforms.

From this follows that for two matrices $A,B\in \mathbb {Z} _{N}^{n\times m}$ over $\mathbb {Z} _{N}$, their row spans are equal if and only if their Howell normal forms are equal.

For example, the matrices

$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}}$

have the same Howell normal form over $\mathbb {Z} _{12}$:

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

Note that $A$ and $B$ are two distinct matrices in the row echelon form, which would mean that their span is the same if they're treated as matrices over some field. Moreover, they're in the Hermite normal form, meaning that their row span is also the same if they're considered over $\mathbb {Z}$, the ring of integers.

However, $\mathbb {Z} _{12}$ is not a field and over general rings it is sometimes possible to nullify a row's pivot by multiplying the row with a scalar without nullifying the whole row. In this particular case,

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

It implies ${\begin{bmatrix}0&3&0\end{bmatrix}}\in S(A)$, which wouldn't be true over any field or over integers.

References

Bibliography

• John A. Howell (April 1986). "Spans in the module (Z_m)^S". Linear and Multilinear Algebra. 19 (1): 67–77. doi:10.1080/03081088608817705. ISSN 0308-1087. Zbl 0596.15013. Wikidata Q110879587.
• Arne Storjohann; Thom Mulders (24 August 1998). "Fast Algorithms for Linear Algebra Modulo N". Lecture Notes in Computer Science: 139–150. doi:10.1007/3-540-68530-8_12. ISSN 0302-9743. Wikidata Q110879586.
• Jean-François Biasse; Claus Fieker; Tommy Hofmann (May 2017). "On the computation of the HNF of a module over the ring of integers of a number field". Journal of Symbolic Computation. 80: 581–615. arXiv:1612.09428. doi:10.1016/J.JSC.2016.07.027. ISSN 0747-7171. Wikidata Q110883424.