We show that the density μ of the Smith normal form (SNF) of a random integer matrix exists and equals a product of densities μps of SNF over Z/psZ with p a prime and s some positive integer. Our approach is to connect the SNF of a matrix with the greatest common divisors (gcds) of certain polynomials of matrix entries, and develop the theory of multi-gcd distribution of polynomial values at a random integer vector. We also derive a formula for μps and determine the density μ for several interesting types of sets.

Source : oai:HAL:hal-02166330v1

Volume: DMTCS Proceedings, 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016)

Published on: April 22, 2020

Submitted on: July 4, 2016

Keywords: Combinatorics,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]

This page has been seen 12 times.

This article's PDF has been downloaded 34 times.