# Hermite Normal Form in “columns” convention

After describing the Hermite Normal Form (HNF), MathWorld explains:

The Hermite normal form for integer matrices is implemented in Mathematica as HermiteDecomposition[A], which however uses the "rows" convention (thus making $\mathbf H$ upper triangular) and replaces (the condition $h_{i\,j}\leq 0$ and $|h_{i\,j}| < h_{i\,i}$ for $j < i$) with balanced remainders $\pmod {h_{ii}}$.

Is there a way, using Mathematica and without much coding, to compute HNF in "columns" convention?

Not too hard; all that's needed is a simple application of matrix identities:

ColumnHermiteDecomposition[mat_ /; MatrixQ[mat, IntegerQ]] :=
Transpose /@ HermiteDecomposition[Transpose[mat]]


Test:

mat = {{1, 2, 3, 2, 2}, {1, 2, 3, 4, 0}, {0, 5, 4, 2, 1}, {3, 2, 4, 0, 2}};
{u, t} = ColumnHermiteDecomposition[mat];

u
{{8, 24, 22, 7, 28}, {7, 21, 20, 6, 25}, {-11, -32, -30, -9, -38},
{3, 8, 7, 2, 9}, {3, 7, 7, 2, 9}}

t
{{1, 0, 0, 0, 0}, {1, 2, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 1, 0}}

mat.u == t
True

• I see that HermiteDecomposition[Transpose[mat]] works, but I don't quite see what lead you to use Transpose[mat]. Would you care to explain? (+1 because it works, and I couldn't get it to do so) – rcollyer Jun 5 '13 at 18:51
• @rcollyer, the row-oriented Hermite decomposition of $\mathbf A$ is $\mathbf U\mathbf A=\mathbf T$, with $\mathbf U$ unimodular and $\mathbf T$ upper triangular. The column-oriented form is $\mathbf A\mathbf V=\mathbf L$, with $\mathbf V$ unimodular and $\mathbf L$ lower triangular. You should now see how transposition affects the arrangement. – J. M.'s technical difficulties Jun 5 '13 at 18:55
• I see the transposition, but my mind isn't making the leap to the relationship between $\DeclareMathOperator{\H}{H}\H_R(\mathbf{A}^T)$ and $\H_C(\mathbf{A})$. I can see that it is a reasonable guess that $\H_R(\mathbf{A}^T)=\{\mathbf{U}^\prime,\mathbf{T}^\prime\}$ should be related to $\{\mathbf{V},\mathbf{L}\}$, but I don't necessarily see why $\mathbf{A}(\mathbf{U}^\prime)^T$ should be $\mathbf{L}$. That is where my difficulty lies. I see that it works, but I don't see why. – rcollyer Jun 5 '13 at 19:20
• @rcollyer, transpose both sides of $\mathbf U\mathbf A^\top=\mathbf T$. What form does the transpose of an upper-triangular matrix take? – J. M.'s technical difficulties Jun 5 '13 at 19:30
• I knew it was something simple; I just wasn't seeing it. Thanks. – rcollyer Jun 5 '13 at 19:41