2
$\begingroup$

Consider a $n$-by-$n$ matrix $A$ over the integers and let $H$ be its Hermite Normal Form. Is there any result about the distribution of the diagonal entries of $H$, when $A$ is "randomly selected"? For example, each entry of $A$ can be uniformly random from some $[0, N)$?

$\endgroup$

1 Answer 1

3
+50
$\begingroup$

This problem was studied by Gerard Maze in Natural Density Distribution of Hermite Normal Forms of Integer Matrices (2010). One result:

The probability that an $n\times n$ integer matrix $A$ has an Hermite normal form (HNF) with the integers $d_1,d_2,\ldots,d_{n−1},d$ on the diagonal is given by $$\bigl(\zeta(n)\zeta(n-1)\cdots\zeta(2)d_1^n d_2^{n-1}\cdots d_{n-1}^2\bigr)^{-1},$$ with $\zeta(n)$ the Riemann zeta function.

The expectation value and variance of a diagonal element have been calculated by Hu et al. in On random nonsingular Hermite Normal Form (2015, paywall). I quote their result:

Note that the distribution of the matrices is different in the two papers: Maze chooses the matrix elements uniformly in the interval $(-M,M)$ for large $M$, while Hu et al. choose the determinant uniformly from that interval.

$\endgroup$
2
  • $\begingroup$ Thanks a lot! A follow up question: has anyone studied the conditional distribution of the diagonal terms in the Smith normal form, given the diagonals on the Hermite normal form? $\endgroup$
    – hao chen
    Commented Nov 12, 2019 at 18:21
  • $\begingroup$ you may want to ask this second question in a separate thread, it seems largely unrelated to your first question. $\endgroup$ Commented Nov 12, 2019 at 20:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .