Hostname: page-component-745bb68f8f-b6zl4 Total loading time: 0 Render date: 2025-01-10T22:23:56.027Z Has data issue: false hasContentIssue false
  • English
  • Français

Surjectivity of near-square random matrices

Part of: Special matrices Linear algebraic groups and related topics

Published online by Cambridge University Press:  06 November 2019

Hoi. H. Nguyen  and
Elliot Paquette
Hoi. H. Nguyen*
Affiliation:
Department of Mathematics, The Ohio State University, 231 West 18th Avenue, Columbus, OH43210, USA
Elliot Paquette
Affiliation:
Department of Mathematics, The Ohio State University, 231 West 18th Avenue, Columbus, OH43210, USA
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that a nearly square independent and identically distributed random integral matrix is surjective over the integral lattice with very high probability. This answers a question by Koplewitz [6]. Our result extends to sparse matrices as well as to matrices of dependent entries.

MSC classification

Primary: 15B52: Random matrices
Secondary: 20G40: Linear algebraic groups over finite fields
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 2 , March 2020 , pp. 267 - 292
Copyright
© Cambridge University Press 2019

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

The first author is supported by research grants DMS-1600782 and DMS-1752345.

References

Basak, A. and Rudelson, M. (2017) Invertibility of sparse non-Hermitian matrices. Adv. Math. 310 426–483.CrossRefGoogle Scholar
Bourgain, J., Vu, V. and Wood, P. M. (2010) On the singularity probability of discrete random matrices. J. Funct. Anal. 258 559–603.CrossRefGoogle Scholar
Halász, G. (1977) Estimates for the concentration function of combinatorial number theory and probability. Periodica Math. Hungar. 8 197–211.CrossRefGoogle Scholar
Kahn, J., Komlós, J. and Szemerédi, E. (1995) On the probability that a random ±1 matrix is singular. J. Amer. Math. Soc. 8 223–240.Google Scholar
Komlós, J. (1967) On the determinant of (0–1) matrices. Studia Sci. Math. Hungar. 2 7–22.Google Scholar
Koplewitz, S. (2016) The corank of a rectangular random integer matrix. arXiv:1611.06441Google Scholar
Koplewitz, S. (2017) Random graphs, sandpile groups, and surjectivity of random matrices. PhD thesis, Yale University.Google Scholar
Maples, K. (2010) Singularity of random matrices over finite fields. arXiv:1012.2372Google Scholar
Maples, K. (2011) Arithmetic properties of random matrices. PhD thesis, University of California, Los Angeles.Google Scholar
Maples, K. (2013) Cokernels of random matrices satisfy the Cohen–Lenstra heuristics. arXiv:1301.1239Google Scholar
Nguyen, H. (2012) Inverse Littlewood–Offord problems and the singularity of random symmetric matrices. Duke Math. J. 161 545–586.CrossRefGoogle Scholar
Nguyen, H. (2018) Random matrices: Overcrowding estimates for the spectrum. J. Funct. Anal. 275 2197–2224.CrossRefGoogle Scholar
Rudelson, M. and Vershynin, R. (2008) The Littlewood–Offord problem and invertibility of random matrices. Adv. Math. 218 600–633.CrossRefGoogle Scholar
Stanley, R. (1997) Enumerative Combinatorics, Vol. 1, Cambridge University Press.CrossRefGoogle Scholar
Tao, T.and Vu, V. (2006) Additive Combinatorics, Vol. 105, Cambridge University Press.CrossRefGoogle Scholar
Tao, T. and Vu, V. (2007) On the singularity probability of random Bernoulli matrices. J. Amer. Math. Soc. 20 603–673.CrossRefGoogle Scholar
Vershynin, R. (2014) Invertibility of symmetric random matrices. Random Struct. Alg. 44 135–182.CrossRefGoogle Scholar
Wood, M. M. (2017) The distribution of sandpile groups of random graphs. J. Amer. Math. Soc. 30 915–958.CrossRefGoogle Scholar
Wood, M. M. (2019) Random integral matrices and the Cohen–Lenstra heuristics. Amer. J. Math. 141 383–398.CrossRefGoogle Scholar