Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-07T20:14:29.237Z 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: nguyen.1261@math.osu.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 2 , March 2020 , pp. 267 - 292
Copyright
© Cambridge University Press 2019

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