Publication:2126277

DOI10.1007/S00039-021-00580-6zbMATH Open1491.15040arXiv2010.06554OpenAlexW3208399317MaRDI QIDQ2126277FDOQ2126277

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Publication date: 19 April 2022

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

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)$.

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

zbMATH Keywords

singularity probabilityreal-valued random variable

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

• Singularity of random symmetric matrices revisited
• Singularity dominated strong fluctuations for some random matrix averages
• Singularity of sparse Bernoulli matrices
• Singularity of sparse random matrices: simple proofs
• On the smallest singular value of symmetric random matrices
• Anticoncentration and the Exact Gap-Hamming Problem
• 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 singularity probability of discrete random matrices
• On sparse random combinatorial matrices
• On the rank, kernel, and core of sparse random graphs
• The rank of sparse random 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)