2020/10/13 by Jain, Vishesh, Sah, Ashwin, Sawhney, Mehtaab · 4 citations
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2010.06554
Let ξ be a non-constant real-valued random variable with finite support, and let Mn(ξ) denote an n× n random matrix with entries that are independent copies of ξ. For ξ which is not uniform on its support, we show that ℙ[Mn(ξ) is singular] amp;= ℙ[zero row or column] + (1+on(1))ℙ[two equal (up to sign) rows or columns], thereby confirming a folklore conjecture. As special cases, we obtain: (1) For ξ= Bernoulli(p) with fixed p ∈ (0,1/2), ℙ[Mn(ξ) is singular] = 2n(1-p)n + (1+on(1))n(n-1)(p2 + (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 ξ= Bernoulli(p) with fixed p ∈ (1/2,1), ℙ[Mn(ξ) is singular] = (1+on(1))n(n-1)(p2 + (1-p)2)n. Previously, only the much weaker upper bound of (√(p) + on(1))n was known due to the work of Bourgain-Vu-Wood. For ξ which is uniform on its support: (1) We show that ℙ[Mn(ξ) is singular] amp;= (1+on(1))nℙ[two rows or columns are equal]. (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 Mn(ξ).