The smallest singular value of dense random regular digraphs

Abstract

Let $A$ be the adjacency matrix of a uniformly random $d$-regular digraph on $n$ vertices, and suppose that $\min (d,n-d)\ge \lambda n$. We show that for any $\kappa \ge 0$, \[\mathbb{P}[s_n(A)\leqκ]\leq C_λκ\sqrt{n}+2e^{-c_λn}.\] Up to the constants $C_{\lambda },c_{\lambda }>0$, our bound matches optimal bounds for $n\times n$ random matrices, each of whose entries is an i.i.d $\text{Ber}(d/n)$ random variable. The special case $\kappa =0$ of our result confirms a conjecture of Cook regarding the probability of singularity of dense random regular digraphs.

21 pages; comments welcome!