On the singularity of adjacency matrices for random regular digraphs

Journal Article

© 2015, Springer-Verlag Berlin Heidelberg. 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.

Full Text

Duke Authors

Cited Authors

  • Cook, NA

Published Date

  • February 1, 2017

Published In

Volume / Issue

  • 167 / 1-2

Start / End Page

  • 143 - 200

International Standard Serial Number (ISSN)

  • 0178-8051

Digital Object Identifier (DOI)

  • 10.1007/s00440-015-0679-8

Citation Source

  • Scopus