On the singularity of adjacency matrices for random regular digraphs

• 成果类型: Article
• 署名作者: Cook, Nicholas A.
• 署名单位: University of California System; University of California Los Angeles
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-015-0679-8
• 发表日期: 2017
• 页码: 143-200
• 关键词: random discrete matrices; asymptotic enumeration; condition number; circular law; column sums; equal row; INVERTIBILITY; eigenvectors; probability

摘要

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 for a sufficiently large constant . 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. 2014). We also apply our general approach to prove asymptotically almost surely invertibility of Hadamard products , where is a matrix of iid uniform signs, and is a 0/1 matrix whose associated digraph satisfies certain expansion properties.