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

From MaRDI portal
Revision as of 13:03, 4 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Natural density distribution of Hermite normal forms of integer matrices
scientific article

    Statements

    Natural density distribution of Hermite normal forms of integer matrices (English)
    0 references
    0 references
    21 October 2011
    0 references
    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.
    0 references
    natural density
    0 references
    Hermite normal forms
    0 references
    random matrices
    0 references
    integer lattices
    0 references
    zeta function
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references