On the singularity of adjacency matrices for random regular digraphs

DOI10.1007/S00440-015-0679-8MaRDI QIDQ510262zbMATH OpenOpenAlexFDO

Authors Nicholas A. Cook

Publication date 17 February 2017

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

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

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)

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.

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

Cites work

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

Cited in

(31)

• On the structure of the adjacency matrix of the line digraph of a regular digraph
• Singularity of the \(k\)-core of a random graph
• Structure of eigenvectors of random regular digraphs
• The spectral gap of dense random regular graphs
• Singularity of sparse Bernoulli matrices
• Spectrum of random d‐regular graphs up to the edge
• 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
• Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
• Discrepancy properties for random regular digraphs
• Adjacency matrices of random digraphs: singularity and anti-concentration
• A note on the singularity probability of random directed \(d\)-regular graphs
• 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
• scientific article; zbMATH DE number 2157272 (Why is no real title available?)
• On sparse random combinatorial matrices
• On the second eigenvalue of random bipartite biregular graphs
• 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)