On the singularity of adjacency matrices for random regular digraphs
Publication
, Journal Article
Cook, NA
Published in: Probability Theory and Related Fields
February 1, 2017
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
Published In
Probability Theory and Related Fields
DOI
ISSN
0178-8051
Publication Date
February 1, 2017
Volume
167
Issue
1-2
Start / End Page
143 / 200
Related Subject Headings
- Statistics & Probability
- 4905 Statistics
- 4904 Pure mathematics
- 0104 Statistics
- 0102 Applied Mathematics
- 0101 Pure Mathematics
Citation
APA
Chicago
ICMJE
MLA
NLM
Cook, N. A. (2017). On the singularity of adjacency matrices for random regular digraphs. Probability Theory and Related Fields, 167(1–2), 143–200. https://doi.org/10.1007/s00440-015-0679-8
Cook, N. A. “On the singularity of adjacency matrices for random regular digraphs.” Probability Theory and Related Fields 167, no. 1–2 (February 1, 2017): 143–200. https://doi.org/10.1007/s00440-015-0679-8.
Cook NA. On the singularity of adjacency matrices for random regular digraphs. Probability Theory and Related Fields. 2017 Feb 1;167(1–2):143–200.
Cook, N. A. “On the singularity of adjacency matrices for random regular digraphs.” Probability Theory and Related Fields, vol. 167, no. 1–2, Feb. 2017, pp. 143–200. Scopus, doi:10.1007/s00440-015-0679-8.
Cook NA. On the singularity of adjacency matrices for random regular digraphs. Probability Theory and Related Fields. 2017 Feb 1;167(1–2):143–200.
Published In
Probability Theory and Related Fields
DOI
ISSN
0178-8051
Publication Date
February 1, 2017
Volume
167
Issue
1-2
Start / End Page
143 / 200
Related Subject Headings
- Statistics & Probability
- 4905 Statistics
- 4904 Pure mathematics
- 0104 Statistics
- 0102 Applied Mathematics
- 0101 Pure Mathematics