Singularity of discrete random matrices

DOI10.1007/S00039-021-00580-6MaRDI QIDQ2126277zbMATH OpenOpenAlexFDO

Authors Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Publication date 19 April 2022

Published in Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.06554

zbMATH Keywords

real-valued random variablesingularity probability

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52) Probabilistic methods in Banach space theory (46B09) Random matrices (probabilistic aspects) (60B20)

Abstract: Let $xi$ be a non-constant real-valued random variable with finite support, and let $M_n(xi)$ denote an $nimesn$ random matrix with entries that are independent copies of $xi$. For $xi$ which is not uniform on its support, we show that �egin{align*} mathbb{P}[M_{n}(xi) ext{ is singular}] &= mathbb{P}[ ext{zero row or column}] + (1+o_n(1))mathbb{P}[ ext{two equal (up to sign) rows or columns}], end{align*} thereby confirming a folklore conjecture. As special cases, we obtain: (1) For $xi=extBernoulli(p)$ with fixed $pin(0,1/2)$, [mathbb{P}[M_{n}(xi) ext{ is singular}] = 2n(1-p)^{n} + (1+o_n(1))n(n-1)(p^2 + (1-p)^2)^{n},] which determines the singularity probability to two asymptotic terms. Previously, no result of such precision was available in the study of the singularity of random matrices. (2) For $xi=extBernoulli(p)$ with fixed $pin(1/2,1)$, [mathbb{P}[M_{n}(xi) ext{ is singular}] = (1+o_n(1))n(n-1)(p^2 + (1-p)^2)^{n}.] Previously, only the much weaker upper bound of $(sqrtp+o_n(1){)}^n$ was known due to the work of Bourgain-Vu-Wood. For $xi$ which is uniform on its support: (1) We show that �egin{align*} mathbb{P}[M_{n}(xi) ext{ is singular}] &= (1+o_n(1))^{n}mathbb{P}[ ext{two rows or columns are equal}]. end{align*} (2) Perhaps more importantly, we provide a sharp analysis of the contribution of the `compressible' part of the unit sphere to the lower tail of the smallest singular value of $M_n(xi)$.

Recommendations

• Singularity of sparse Bernoulli matrices
• Singularity of sparse random matrices: simple proofs
• Singularity of random Bernoulli matrices
• On the singularity probability of discrete random matrices
• On the singularity of random matrices with independent entries

Cites work

• An estimate of the remainder in a combinatorial central limit theorem
• Anticoncentration versus the Number of Subset Sums
• Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices
• Asymptotics of the number of threshold functions and the singularity probability of random \( \{\pm 1\}\)-matrices
• DIAMETERS OF SOME FINITE-DIMENSIONAL SETS AND CLASSES OF SMOOTH FUNCTIONS
• High-dimensional probability. An introduction with applications in data science
• scientific article; zbMATH DE number 3245540 (Why is no real title available?)
• Invertibility of random matrices: norm of the inverse
• On random ±1 matrices: Singularity and determinant
• On the counting problem in inverse Littlewood-Offord theory
• On the Increase of Dispersion of Sums of Independent Random Variables
• On the Probability That a Random ± 1-Matrix Is Singular
• On the singularity of random combinatorial matrices
• On the singularity probability of discrete random matrices
• On the singularity probability of random Bernoulli matrices
• Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
• Singularity of random Bernoulli matrices
• Smallest singular value of random matrices and geometry of random polytopes
• Special orthogonal splittings of \(L_1^{2k}\)
• The Littlewood-Offord problem and invertibility of random matrices
• The smallest singular value of heavy-tailed not necessarily i.i.d. random matrices via random rounding
• The smallest singular value of inhomogeneous square random matrices

Cited in

(17)

• On the singularity probability of discrete random matrices
• Singularity dominated strong fluctuations for some random matrix averages
• Singularity of sparse Bernoulli matrices
• On sparse random combinatorial matrices
• Anticoncentration and the Exact Gap-Hamming Problem
• Singularity of random symmetric matrices revisited
• Singularity of sparse random matrices: simple proofs
• On the smallest singular value of symmetric random matrices
• The rank of sparse random matrices
• A note on the singularity probability of random directed \(d\)-regular graphs
• A large deviation inequality for the rank of a random matrix
• The singularity probability of a random symmetric matrix is exponentially small
• On the rank, kernel, and core of sparse random graphs
• Counting matrices over finite rank multiplicative groups
• On the rank of a random symmetric matrix in the large-deviation regime
• LU Factorization of Discrete Random Matrices
• An upper bound on the smallest singular value of dense random combinatorial matrices

This page was built for publication: Singularity of discrete random matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2126277)