NDLI: The Smith Normal Form Distribution of A Random Integer Matrix

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Stanley, Richard P. Wang, Yinghui
Copyright Year	2017
Abstract	We show that the density $\mu$ of the Smith normal form (SNF) of a random integer matrix exists and equals a product of densities $\mu_{p^s}$ of SNF over $\Bbb{Z}/p^s\Bbb{Z}$ 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 $\mu_{p^s}$ and compute the density $\mu$ for several interesting types of sets. As an application, we determine the probability that the cokernel of a random integer square matrix has at most $\ell$ generators for a positive integer $\ell$, and establish its asymptotics as $\ell \to \infty$, which extends a result of Ekedahl (1991) on the case $\ell=1$.
Sponsorship	National Science Foundation
Starting Page	2247
Ending Page	2268
Page Count	22
File Format	PDF
ISSN	08954801
DOI	10.1137/16M1098140
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	3
Volume Number	31
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2017-09-28
Access Restriction	Subscribed
Subject Keyword	greatest common divisor distribution Random matrices Canonical forms, reductions, classification random integer matrix Polynomials Smith normal form Matrices over special rings Matrices, determinants Permutations, words, matrices
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix

On the Smith Normal Form of Structured Polynomial Matrices, II

Parallelism in Hermite and Smith normal forms

Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices

On the Smith Normal Form of Structured Polynomial Matrices

Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix

Parallelism in Hermite and Smith normal forms

On the greatest common divisor of the value of two polynomials

Computing the Smith normal form of a matrix. [Computer greatest common divisor of n polynomials]

The Smith Normal Form Distribution of A Random Integer Matrix

Similar Documents

Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix

On the Smith Normal Form of Structured Polynomial Matrices, II

Parallelism in Hermite and Smith normal forms

Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices

On the Smith Normal Form of Structured Polynomial Matrices

Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix

Parallelism in Hermite and Smith normal forms

On the greatest common divisor of the value of two polynomials

Computing the Smith normal form of a matrix. [Computer greatest common divisor of n polynomials]

The Smith Normal Form Distribution of A Random Integer Matrix