On the singularity of adjacency matrices for random regular digraphs

详细信息    查看全文

• 作者：Nicholas A. Cook
• 关键词：Random matrices ; Random regular digraphs ; Singularity probability ; Discrepancy property
• 刊名：Probability Theory and Related Fields
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：167
• 期：1-2
• 页码：143-200
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Probability Theory and Stochastic Processes; Theoretical, Mathematical and Computational Physics; Quantitative Finance; Mathematical and Computational Biology; Statistics for Business/Economics/Mathem
• 出版者：Springer Berlin Heidelberg
• ISSN：1432-2064
• 卷排序：167

文摘

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)\ge C\log ^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 \(\varSigma {{\mathrm{\circ }}}\varXi \), where \(\varXi \) is a matrix of iid uniform \(\pm 1\) signs, and \(\varSigma \) is a 0/1 matrix whose associated digraph satisfies certain “expansion” properties.