On the singularity of adjacency matrices for random regular digraphs
On the singularity of adjacency matrices for random regular digraphs
复制标题
关于随机正则有向图邻接矩阵的奇异性
DOI：
10.1007/s00440-015-0679-8
复制
发表时间：
2014
影响因子：
2
通讯作者：
Nicholas A. Cook
中科院分区：
文献类型：
--
作者：
Nicholas A. Cook
我们证明了n点均匀随机d-正则有向图的(非对称)邻接矩阵几乎必然可逆，假设≥Clog2n对足够大的常数$$C>；0$$C>；0$$C>；0$C>；0。该证明利用了随机规则有向图的耦合，该有向图是通过对两个顶点的邻域进行“洗牌”而形成的，以及在Cook(随机结构算法)中证明的边分布的集中结果。Arxiv：1410.5595,2014年)。我们还利用我们的一般方法证明了Hadamard乘积$$\varSigma{{\mathrm{\cic}\varxi$$Σ∘Ξ几乎必然是渐近可逆的，其中$$\varxi$$Ξ是由iID一致的$$\pm 1$$±1符号组成的矩阵，而$$\varSigma$$Σ是一个0/1矩阵，它的相关有向图满足某些“扩展”性质。
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$$min(d,n-d)≥Clog2n for a sufficiently large constant $$C>0$$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$$±1 signs, and $$\varSigma $$Σ is a 0/1 matrix whose associated digraph satisfies certain “expansion” properties.