The rank of random regular digraphs of constant degree
Preprint
Abstract
Let $d$ be a fixed large integer. For any $n$ larger than $d$, let $A_n$ be the adjacency matrix of the random directed $d$-regular graph on $n$ vertices, with the uniform distribution. We show that $A_n$ has rank at least $n-1$ with probability going to one as $n$ goes to infinity. The proof combines the method of simple switchings and a recent result of the authors on delocalization of eigenvectors of $A_n$.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Structure of eigenvectors of random regular digraphsTransactions of the American Mathematical Society, 2019
- The smallest singular value of a shifted d-regular random square matrixProbability Theory and Related Fields, 2018
- Invertibility of sparse non-Hermitian matricesAdvances in Mathematics, 2017
- Adjacency matrices of random digraphs: Singularity and anti-concentrationJournal of Mathematical Analysis and Applications, 2017
- Anti-concentration property for random digraphs and invertibility of their adjacency matricesComptes Rendus Mathematique, 2016
- On the singularity of adjacency matrices for random regular digraphsProbability Theory and Related Fields, 2015
- Invertibility of symmetric random matricesRandom Structures & Algorithms, 2012
- On the singularity probability of discrete random matricesJournal of Functional Analysis, 2010
- The rank of random graphsRandom Structures & Algorithms, 2008
- On the singularity probability of random Bernoulli matricesJournal of the American Mathematical Society, 2007