Natural density distribution of Hermite normal forms of integer matrices
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.
- A linear space algorithm for computing the hermite normal form
- Cryptography and lattices. 1st international conference, CaLC 2001, Providence, RI, USA, March 29--30, 2001. Revised papers
- Density of integer points on affine homogeneous varieties
- Elementary divisors and determinants of random matrices over a local field.
- Fast computation of Hermite normal forms of random integer matrices
- scientific article; zbMATH DE number 434828 (Why is no real title available?)
- scientific article; zbMATH DE number 3657869 (Why is no real title available?)
- scientific article; zbMATH DE number 473229 (Why is no real title available?)
- Natural density of rectangular unimodular integer matrices
- On the equidistribution of Hecke points
- On the probability that k positive integers are relatively prime. II
- The LLL algorithm. Survey and applications
- The number of 2 2 integer matrices having a prescribed integer eigenvalue
- The Probability that a Matrix of Integers Is Diagonalizable
- A local to global principle for expected values
- On random nonsingular Hermite normal form
- On rectangular unimodular matrices over the algebraic integers
- scientific article; zbMATH DE number 7203492 (Why is no real title available?)
- The Smith normal form distribution of a random integer matrix
- Natural density of integral matrices that can be extended to invertible integral matrices
- On the divisibility of degrees of representations of Lie groups
- Fast computation of Hermite normal forms of random integer matrices
This page was built for publication: Natural density distribution of Hermite normal forms of integer matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q640872)
