Rank and Invertibility of Dense Signed Random Regular Matrices

Abstract

Let $A$ be the (non-symmetric) adjacency matrix of a uniformly random $d$-regular directed graph on $n$ vertices, and let $\Xi$ be independent of $A$ with i.i.d. Rademacher entries. Suppose that $\min(d,n-d)\ge\lambda n$ for some fixed $\lambda\in(0,1/2]$. We show that there exists $c>0$, depending only on $\lambda$, such that \[ \mathbf P_{A,\Xi}\{\operatorname{rank}(A\circ\Xi)\le n-k\}\le e^{-c nk},\qquad 1\le k\le n. \] As an ingredient in the proof of the rank bound, we use the case $\kappa=0$ of the following quantitative smallest singular value estimate: \[ \mathbf P_{A,\Xi}\{s_n(A\circ\Xi)\le\kappa\} \le C\kappa\sqrt n+e^{-c'n}, \qquad \kappa\ge0, \] where $C,c'>0$ depend only on $\lambda$.