Hermite Normal Form Matrix

A matrix $ M $ of size $ n \times m $ with integer coefficients (natural or relative) has a Hermite decomposition if there exists a triangular matrix $ H $ and a unimodular matrix $ U $ such that $ H = U. M $. Reminder: An upper triangular matrix $ H $ is such that $ H_ {i, j} = 0 $ for $ i> j $ and a unimodular matrix is an invertible square matrix with integer coefficients whose determinant is $ \pm 1 $.

Example: $$ M = \begin{bmatrix} 3 & 2 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix} \Rightarrow H = \begin{bmatrix} 0 & -1 & 1 \\ 0 & 1 & 0 \\ -1 & -1 & 3 \end{bmatrix}, U = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 2 \end{bmatrix} $$

There are two forms for the Hermite matrix, an upper triangular matrix such that $ H = UM $ (also called Hermite's normal form row style) is a lower triangular matrix such that $ H = MU $ ( also called Hermite normal form column style)

dCode uses the LLL algorithm (Lenstra-Lenstra-Lovász) to calculate the Hermite decomposition (the calculation by hand is not recommended)

A normal Hermite-shaped matrix is the triangular scaled matrix $ H $ calculated by the Hermite decomposition (above) via reduction to row echelon form of the matrix.