On the singularity of adjacency matrices for random regular digraphs

DOI10.1007/S00440-015-0679-8zbMATH Open1365.05260arXiv1411.0243OpenAlexW2270656976MaRDI QIDQ510262FDOQ510262

Authors: Nicholas A. Cook 

Publication date: 17 February 2017

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Abstract: 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)geClo{g}^{2}n$ 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 recently obtained by the author (arXiv:1410.5595). We also apply our general approach to prove a.a.s. invertibility of Hadamard products $SigmacircXi$, where $Xi$ is a matrix of iid uniform $pm1$ signs, and $Sigma$ is a 0/1 matrix whose associated digraph satisfies certain "expansion" properties.

Full work available at URL: https://arxiv.org/abs/1411.0243

Recommendations

• Adjacency matrices of random digraphs: singularity and anti-concentration
• Invertibility of adjacency matrices for random \(d\)-regular graphs
• Anti-concentration property for random digraphs and invertibility of their adjacency matrices
• The rank of random regular digraphs of constant degree
• The circular law for random regular digraphs

zbMATH Keywords

random matricesrandom digraphsdiscrepancy propertysingularity probability

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20)

Cites Work

• Random matrices: universality of ESDs and the circular law
• Title not available (Why is that?)
• Random graphs with a given degree sequence
• Title not available (Why is that?)
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• The Littlewood-Offord problem and invertibility of random matrices
• Around the circular law
• Invertibility of random matrices: Unitary and orthogonal perturbations
• The single ring theorem
• Limiting spectral distribution of sum of unitary and orthogonal matrices
• Sparse random graphs: eigenvalues and eigenvectors
• Sparse regular random graphs: spectral density and eigenvectors
• On the singularity probability of discrete random matrices
• On the singularity probability of random Bernoulli matrices
• Title not available (Why is that?)
• On the Probability That a Random ± 1-Matrix Is Singular
• On the singularity of random combinatorial matrices
• Title not available (Why is that?)
• On a lemma of Littlewood and Offord
• Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
• Circular law theorem for random Markov matrices
• Smooth analysis of the condition number and the least singular value
• On factors in random graphs
• Lower estimates for the singular values of random matrices
• Stein's method for concentration inequalities
• Title not available (Why is that?)
• Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums
• Asymptotic enumeration of integer matrices with large equal row and column sums
• Local law for eigenvalues of random regular bipartite graphs
• Circular law for random discrete matrices of given row sum
• Random doubly stochastic matrices: the circular law
• The Marčenko-Pastur law for sparse random bipartite biregular graphs
• Circular law for random matrices with exchangeable entries
• Circular law for random matrices with unconditional log-concave distribution

Cited In (31)

• Singularity of the \(k\)-core of a random graph
• On the structure of the adjacency matrix of the line digraph of a regular digraph
• Structure of eigenvectors of random regular digraphs
• The spectral gap of dense random regular graphs
• Spectrum of random d‐regular graphs up to the edge
• Singularity of sparse Bernoulli matrices
• The circular law for random regular digraphs with random edge weights
• Local Kesten-McKay law for random regular graphs
• The rank of random regular digraphs of constant degree
• Discrepancy properties for random regular digraphs
• Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
• A note on the singularity probability of random directed \(d\)-regular graphs
• Adjacency matrices of random digraphs: singularity and anti-concentration
• The circular law for random regular digraphs
• Anti-concentration property for random digraphs and invertibility of their adjacency matrices
• Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices
• Recent progress in combinatorial random matrix theory
• The smallest singular value of a shifted $d$-regular random square matrix
• Circular law for sparse random regular digraphs
• Edge rigidity and universality of random regular graphs of intermediate degree
• Title not available (Why is that?)
• On the second eigenvalue of random bipartite biregular graphs
• On sparse random combinatorial matrices
• Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs
• Invertibility of adjacency matrices for random \(d\)-regular graphs
• The Smallest Singular Value of Dense Random Regular Digraphs
• Size biased couplings and the spectral gap for random regular graphs
• Möbius Inversion of Random Acyclic Directed Graphs
• Quantitative invertibility of non-Hermitian random matrices
• On the counting problem in inverse Littlewood-Offord theory
• Polynomial threshold functions, hyperplane arrangements, and random tensors

This page was built for publication: On the singularity of adjacency matrices for random regular digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q510262)