To compute Hermite Normal Form H and U 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

 A: 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

*

*$h_{i,i}>0$

*$0\leq h_{i,j}<h_{i,i} \ ,\forall 1\leq j<i\leq m$

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