Natural density distribution of Hermite normal forms of integer matrices (Q640872)

The author analyses the probability that the Hermite Normal Form (HNF) of a random \(n\times m\) integer matrix has a given diagonal. The starting point is Hermite's result which states that for any \(n\times m\) integer matrix \(A\) there exists an \(n\times n\) unimodular matrix \(U\) and a unique \(n\times n\) integer matrix \(H\) in HNF such that \(A=UH\); \(H\) is called the HNF of \(A\) and it has \(r\leq n\) non-zero rows, for each row \(i\leq r\) the first non-zero entry \(h_{ij_i}\) is strictly positive, \(j_1<j_2<\cdots<j_r\) and for each \(1\leq k\leq i\leq r\) the entries \(h_{kj_i}\) of \(H\) satisfy \(0\leq h_{kj_i}<h_{ij_i}\). An algorithm is proposed which compute the HNF of a matrix \(A\). The paper presents the concept of natural density in \({\mathbb Z}^k\) which is used to obtain the main result of the paper (Proposition 6) which provides the frequency of appearance of a given non-zero diagonal in the HNF of a random looking matrix and shows that the density of these HNFs is 0. A corollary proves that given \(d_1,d_2,\dots,d_{n-1}\in{\mathbb N}^*\), the natural density of \(n\times n\) matrices whose HNF has the diagonal \((d_1,d_2,\dots,d_{n-1},\det A/\prod_{i=1}^{n-1}d_i)\) is \[ (\zeta(n)\zeta(n-1)\cdots\zeta(2)d_1^nd_2^{n-1}\cdots d_{n-1}^2)^{-1}, \] where \(\zeta\) is the usual zeta function. Two applications are presented, concerning the selection of random lattices that arise in cryptology, respectively the distribution of gcd\((\det[A|x],\det[A|y])\), where \(A\) is a random looking \(n\times(n-1)\) integer matrix and \(x,y\) are two \(n\)-vectors.