2020/10/13 by Jain, Vishesh, Sah, Ashwin, Sawhney, Mehtaab
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2010.06553
Let p ∈ (0,1/2) be fixed, and let Bn(p) be an n× n random matrix with i.i.d. Bernoulli random variables with mean p. We show that for all t ≥ 0, ℙ[sn(Bn(p)) ≤ tn-1/2] ≤ Cp t + 2n(1-p)n + Cp (1-p-εp)n, where sn(Bn(p)) denotes the least singular value of Bn(p) and Cp, εp > 0 are constants depending only on p. In particular, ℙ[Bn(p) is singular] = 2n(1-p)n + Cp(1-p-εp)n, which confirms a conjecture of Litvak and Tikhomirov. We also confirm a conjecture of Nguyen by showing that if Qn is an n× n random matrix with independent rows that are uniformly distributed on the central slice of \0,1\n, then ℙ[Qn is singular] = (1/2 + on(1))n. This provides, for the first time, a sharp determination of the logarithm of the probability of singularity in any natural model of random discrete matrices with dependent entries.