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 the ring of integers modulo N, $\mathbb {Z} _{N}$.

Definition

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

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

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

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

If matrix adheres to the properties above, it is said to be in the reduced row echelon form.

Let $S(A)$ be the row span of $A$. Matrix in reduced row echelon form is said to be in the Howell normal form if it adheres to the following additional property:

• let $v\in S(A)$ be an elements of the row span of $A$, such that $v_{k}=0$ for any $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.