To compute Hermite Normal Form H and U

Question

I bounced off this problem now for the third time within a few years. While there are (a few) sources on the internet, including

• wikipedia
• a calculator for the Hermite Normal Form
• a youtube video on the subject

none of those sites really explains, how to calculate both H and U. They only say "U must be co-computed" and then they blather more extensively about the 2 different forms (upper and lower triangle form). So, given a simple 2x2 matrix

1 -3
1  4

can anyone show step by step, how it is done? I know some augmentation of the matrix is part of it. But I could not find a comprehensive explanation anywhere.

update

While waiting for an answer, I kept fiddling around and I think I figured it out now. Please confirm.

julia> using LinearAlgebra

julia> M = [ 1 -3; 1 4 ]
2×2 Array{Int64,2}:
 1  -3
 1   4

julia> U = Matrix(1I,2,2)
2×2 Array{Int64,2}:
 1  0
 0  1

julia> s0 = hcat(M,U)
2×4 Array{Int64,2}:
 1  -3  1  0
 1   4  0  1

julia> s1 = [ s0[1,:]'; (s0[2,:] - s0[1,:])']
2×4 Array{Int64,2}:
 1  -3   1  0
 0   7  -1  1
# -3 is still wrong. It should be between 0 and 7

julia> s2 = [ (s1[1,:] + s1[2,:])'; s1[2,:]' ]
2×4 Array{Int64,2}:
 1  4   0  1
 0  7  -1  1

julia> H = s2[1:2,1:2]
2×2 Array{Int64,2}:
 1  4
 0  7

julia> U = s2[1:2,3:4]
2×2 Array{Int64,2}:
  0  1
 -1  1

julia> U * M == H
true

Answer 1

To undestand how the process works, it is best illustrated with a non-squared matrix. As square matrices are easier to work with, it doesn't show the full extend of the process.

Process: The intuitive way to get to the normal hermite form (and obtain the transformation matrix in the process) is to bring the given matrix into a Hermite normal form using only unitarian elementary column operations (UECO below). This means, you can:

• Interchange two columns: $$C_i\leftrightarrow C_j$$
• Multiply a column by $-1$: $$C_i\leftarrow -C_i$$
• Add an integer multiple of another column: $$C_i\leftarrow\lambda C_j \ ,\ \lambda\in\mathbb{Z}$$

To obtain U, you just multiply by the right the identity by the sequence of UECO you did; let me clarify later. To understand which matrix you should use, here is a quick recap: for $M.U, M\in\mathbb{Z}^{m\times n}$, $U\in\mathbb{Z}^{n\times n}$ as desired:

• $C_i\leftrightarrow C_j$ : Keep in mind that this process is symetric We want to exchange column $i$ and $j$, so let us set $U$ as: $C^U_i=C^{I_n}_i$ if $C_i$ is not concerned, and $(U)_{i,j}=(U)_{j,i}=1$, zero otherwise.

Exemple: Interchange column 1 and 3 in $M=\begin{pmatrix}a&b&c\\ d&e&f\end{pmatrix}$. Set $U=\begin{pmatrix}0&0&1\\0&1&0\\1&0&0\end{pmatrix}$: $$\begin{pmatrix}a&b&c\\d&e&f\end{pmatrix}\begin{pmatrix}0&0&1\\0&1&0\\1&0&0\end{pmatrix}=\begin{pmatrix}c&b&a\\f&e&d\end{pmatrix}$$

• $C_i\leftarrow -C_i$ : Only one column is concerned, thus we should only change one column of the identity. Set $C^U_j=C^{I_n}_j$ for all $j\neq i$ and $(U)_{i,i}=-1$.

Exemple: Multiply column 2 by $-1$ in $M=\begin{pmatrix}a&b&c\\ d&e&f\end{pmatrix}$. Set $U=\begin{pmatrix}1&0&0\\0&-1&0\\0&0&1\end{pmatrix}$: $$\begin{pmatrix}a&b&c\\d&e&f\end{pmatrix}\begin{pmatrix}1&0&0\\0&-1&0\\0&0&1\end{pmatrix}=\begin{pmatrix}a&-b&c\\d&-e&f\end{pmatrix}$$

• $C_i\leftarrow\lambda C_j \ ,\ \lambda\in\mathbb{Z}$ : Now again two columns are concerned, but this time the matrix wont be symetric. $C_i$ should stay in her position, and we should simply add $C_j$. So $U$ will take the form of the identity, with the exception that $(C^U_i)_j=\lambda$.

Exemple: Add $\lambda C_3$ to $C_2$ in $M=\begin{pmatrix}a&b&c\\ d&e&f\end{pmatrix}$. Set $U=\begin{pmatrix}1&0&0\\0&1&0\\0&\lambda&1\end{pmatrix}$: $$\begin{pmatrix}a&b&c\\d&e&f\end{pmatrix}\begin{pmatrix}1&0&0\\0&1&0\\0&\lambda&1\end{pmatrix}=\begin{pmatrix}a&b+\lambda c&c\\ d&e+\lambda f& f\end{pmatrix}$$

If this process is undestood, the computation of $H$ and $U$ are just common sens. Recall that a normal Hermite form is of the sort $$H=\begin{pmatrix}h_{1,1}& 0 & \ \cdots& \cdots & 0\\ h_{2,1}& h_{2,2}& 0& \cdots &0\\ \vdots&\vdots&\ddots&\ddots&\vdots\end{pmatrix}\in\mathbb{Z}^{m\times n}$$ where

1. $h_{i,i}>0$
2. $0\leq h_{i,j}<h_{i,i} \ ,\forall 1\leq j<i\leq m$
3. The rest is zero

This is the form I learned in my courses, maybe yours states it should be upper-triangular instead. This does not chage anything in the process, you just have to bring the matrix in upper-triangular form instead of a lower-triangular, as I showcased here

Application: I'll illustrate with an example a little bit more complicated then yours. You should be able to apply the method illustrated above to your example. We want to transform $A=\begin{pmatrix}4&6&10\\6&12&9\end{pmatrix}$ in Hermite normal form $H$ and find $U$ such that $A.U=H$:

Apply the following UECO on the colums of $A$:

$A=\begin{pmatrix}4&6&10\\6&12&9\end{pmatrix}\sim\begin{pmatrix}4&2&2\\6&6&-3\end{pmatrix}\sim\begin{pmatrix}2&4&2\\6&6&-3\end{pmatrix}\sim\begin{pmatrix}2&0&0\\6&-6&-9\end{pmatrix}\sim\begin{pmatrix}2&0&0\\6&3&-9\end{pmatrix}\sim\begin{pmatrix}2&0&0\\6&3&0\end{pmatrix}\sim\begin{pmatrix}2&0&0\\0&3&0\end{pmatrix}=H$

The corresponding UECO transfirmation matrices leads us to: $U=\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}.\begin{pmatrix}1&-1&-2\\0&1&0\\0&0&1\end{pmatrix}\cdots\begin{pmatrix}1&0&0\\-2&1&0\\0&0&1\end{pmatrix}=\begin{pmatrix}-9&4&11\\3&-1&-4\\2&-1&-2\end{pmatrix}$

And one can check that $$A.U=\begin{pmatrix}4&6&10\\6&12&9\end{pmatrix}\begin{pmatrix}-9&4&11\\3&-1&-4\\2&-1&-2\end{pmatrix}=\begin{pmatrix}2&0&0\\0&3&0\end{pmatrix}=H$$

Hope it helps.