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.

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 $i_{1}<i_{2}<\dots <i_{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 the column count $m$,
• 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<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

Let $A,B\in \mathbb {Z} _{N}^{n\times m}$ be matrices over $\mathbb {Z} _{N}$. Their linear 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}}.$

References

• 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.