On the singularity of adjacency matrices for random regular digraphs

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) ≥ Clog 2n for a sufficiently large constant C> 0. 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, proved in Cook (Random Struct Algorithms. arXiv:1410.5595, 2014). We also apply our general approach to prove asymptotically almost surely invertibility of Hadamard products Σ∘ Ξ, where Ξ is a matrix of iid uniform ± 1 signs, and Σ is a 0/1 matrix whose associated digraph satisfies certain “expansion” properties.

Duke Scholars

Author Nicholas A Cook Mathematics