# Surjectivity of near-square random matrices

@article{Nguyen2019SurjectivityON, title={Surjectivity of near-square random matrices}, author={Hoi H. Nguyen and Elliot Paquette}, journal={Combinatorics, Probability and Computing}, year={2019}, volume={29}, pages={267 - 292} }

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.

#### Topics from this paper

#### 4 Citations

Random integral matrices: universality of surjectivity and the cokernel

- Mathematics
- Inventiones mathematicae
- 2021

For a random matrix of entries sampled independently from a fairly general distribution in Z we study the probability that the cokernel is isomorphic to a given finite abelian group, or when it is… Expand

The characteristic polynomial of a random matrix

- Mathematics
- 2020

Form an $n \times n$ matrix by drawing entries independently from $\{\pm1\}$ (or another fixed nontrivial finitely supported distribution in $\mathbf{Z}$) and let $\phi$ be the characteristic… Expand

Polynomial Data Structure Lower Bounds in the Group Model

- Computer Science, Mathematics
- 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
- 2020

This work proves a polynomial lower bound for an explicit range counting problem of $n^{3}$ convex polygons in $\mathbb{R}^{2}$ (each with $n^{\tilde{O}(1)}$ facets/semialgebraic-complexity), against linear storage arithmetic data structures in the group model. Expand

The Rank of the Sandpile Group of Random Directed Bipartite Graphs

- Mathematics
- 2021

We identify the asymptotic distribution of p-rank of the sandpile group of a random directed bipartite graphs which are not too imbalanced. We show this matches exactly that of the Erdös-Rényi random… Expand

#### References

SHOWING 1-10 OF 24 REFERENCES

Cokernels of random matrices satisfy the Cohen-Lenstra heuristics

- Mathematics
- 2013

Let A be an n by n random matrix with iid entries taken from the p-adic integers or Z/NZ. Then under mild non-degeneracy conditions the cokernel of A has a universal probability distribution. In… Expand

The Littlewood-Offord problem and invertibility of random matrices

- Mathematics
- 2007

Abstract We prove two basic conjectures on the distribution of the smallest singular value of random n × n matrices with independent entries. Under minimal moment assumptions, we show that the… Expand

Invertibility of symmetric random matrices

- Mathematics, Computer Science
- Random Struct. Algorithms
- 2014

It is shown that H is singular with probability at most exp-nc, and ||H-1||=On, and the spectrum of H is delocalized on the optimal scale on-1/2, improving upon a polynomial singularity bound due to Costello, Tao and Vu. Expand

The corank of a rectangular random integer matrix

- Mathematics
- 2016

We show that under reasonable conditions, a random $n\times (2+\epsilon) n$ integer matrix is surjective on $\mathbb{Z}^{n}$ with probability $1-O(e^{-cn})$. We also conjecture that this should hold… Expand

Random matrices: Overcrowding estimates for the spectrum

- Mathematics
- Journal of Functional Analysis
- 2018

Abstract We address overcrowding estimates for the singular values of random iid matrices, as well as for the eigenvalues of random Wigner matrices. We show evidence of long range separation under… Expand

Singularity of Random Matrices over Finite Fields

- Mathematics
- 2010

Let $A$ be an $n \times n$ random matrix with iid entries over a finite field of order $q$. Suppose that the entries do not take values in any additive coset of the field with probability greater… Expand

Inverse Littlewood-Offord problems and The Singularity of Random Symmetric Matrices

- Mathematics
- 2011

Let $M_n$ denote a random symmetric $n$ by $n$ matrix, whose upper diagonal entries are iid Bernoulli random variables (which take value -1 and 1 with probability 1/2). Improving the earlier result… Expand

On the singularity probability of discrete random matrices

- Mathematics
- 2009

Abstract Let n be a large integer and M n be an n by n complex matrix whose entries are independent (but not necessarily identically distributed) discrete random variables. The main goal of this… Expand

On the probability that a random ±1-matrix is singular

- Mathematics
- 1995

We report some progress on the old problem of estimating the probability, Pn, that a random n× n ± 1 matrix is singular: Theorem. There is a positive constant ε for which Pn < (1− ε)n. This is a… Expand

Random integral matrices and the Cohen-Lenstra heuristics

- Mathematics
- American Journal of Mathematics
- 2019

Abstract:We prove that given any $\epsilon>0$, random integral $n\times n$ matrices with independent entries that lie in any residue class modulo a prime with probability at most $1-\epsilon$ have… Expand