Sharp invertibility of random Bernoulli matrices

arXiv2010.06553MaRDI QIDQ6351210FDOQ6351210

Ashwin Sah, Mehtaab Sawhney, Vishesh Jain

Publication date: 13 October 2020

Abstract: Let $pin(0,1/2)$ be fixed, and let $B_n(p)$ be an $nimesn$ random matrix with i.i.d. Bernoulli random variables with mean $p$. We show that for all $tge0$, [mathbb{P}[s_n(B_n(p)) le tn^{-1/2}] le C_p t + 2n(1-p)^{n} + C_p (1-p-epsilon_p)^{n},] where $s_n(B_n(p))$ denotes the least singular value of $B_n(p)$ and $C_p,epsilo{n}_p>0$ are constants depending only on $p$. In particular, [mathbb{P}[B_{n}(p) ext{ is singular}] = 2n(1-p)^{n} + C_{p}(1-p-epsilon_p)^{n},] which confirms a conjecture of Litvak and Tikhomirov. We also confirm a conjecture of Nguyen by showing that if $Q_n$ is an $nimesn$ random matrix with independent rows that are uniformly distributed on the central slice of ${0,1}^n$, then [mathbb{P}[Q_{n} ext{ is singular}] = (1/2 + o_n(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.

This page was built for publication: Sharp invertibility of random Bernoulli matrices

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