On the singularity of adjacency matrices for random regular digraphs

Nicholas A. Cook

Published 2014-11-02Version 1

We prove that the (non-symmetric) adjacency matrix of a uniform random $d$-regular directed graph on $n$ vertices is asymptotically almost surely invertible, assuming $\min(d,n-d)=\omega(\log^2n)$. This improves an earlier result of the author, which was limited to the dense case $\min(d,n-d)=\Omega(n)$. The proof makes use of a coupling of random regular digraphs formed by "shuffling" the neighborhood of a pair of vertices, as well as concentration results for the distribution of edges. We also apply our general approach to prove a.a.s.\ invertibility of Hadamard products $M\odot \Xi$, where $\Xi$ is a matrix of iid uniform $\pm1$ signs, and $M$ is a 0/1 matrix whose associated digraph satisfies certain "expansion" properties.