Howell normal form

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

• Let ${\displaystyle r}$ be the number of non-zero rows of ${\displaystyle A}$. Then the topmost ${\displaystyle r}$ rows of the matrix are non-zero,
• For ${\displaystyle 1\leq i\leq r}$, let ${\displaystyle j_{i}}$ be the index of the leftmost non-zero element in the row ${\displaystyle i}$. Then ${\displaystyle 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 ${\displaystyle 1\leq i\leq r}$, the leading element ${\displaystyle A_{ij_{i}}}$ is a divisor of ${\displaystyle N}$,
• For each ${\displaystyle 1\leq k<i\leq r}$ it holds that ${\displaystyle 0\leq A_{kj_{i}}<A_{ij_{i}}}$.

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

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

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

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

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

For example, the matrices

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

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

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

Note that ${\displaystyle A}$ and ${\displaystyle 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 ${\displaystyle \mathbb {Z} }$, the ring of integers.^[2]

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

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

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

• 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. Zbl 1403.11084. Wikidata Q110883424.