The Smallest Singular Value of Dense Random Regular Digraphs

Let A be the adjacency matrix of a uniformly random d-regular digraph on n vertices, and suppose that min(d, n - d) >= lambda n. We show that for any kappa >= 0, P[s(n) (A) <= kappa] <= C-lambda kappa root n + 2e(-c lambda n). Up to the constants C-lambda,c(lambda) > 0, our bound matches optimal bounds for n x n random matrices, each of whose entries is an i.i.d Ber(d/n) random variable. The special case k = 0 of our result confirms a conjecture of Cook regarding the probability of singularity of dense random regular digraphs.