On the singularity of adjacency matrices for random regular digraphs (Q510262): Difference between revisions

For \(n\geq 1\) and \(1\leq d\leq n\), let \(\mathcal{M}_{n,d}\) denote the set of \(n\times n\) matrices with entries \(0\) or \(1\) with the property that all row and column sums equal \(d\). Each matrix in \(\mathcal{M}_{n,d}\) can be interpreted as the adjacency matrix of a \(d\)-regular directed graph (digraph), where the vertex set is \(\{1,\dots,n\}\) and each vertex has exactly \(d\) in-neighbors and exactly \(d\) out-neighbors. Denote by \(M\) a uniform random element of \(\mathcal{M}_{n,d}\). The objective of this paper is to determine when \(M\) is invertible with high probability when \(n\) is large. The author proves that the adjacency matrix of a uniform random \(d\)-regular digraph on \(n\) vertices is almost surely invertible, when \(\min(d,n-d)\geq C\log^{2}n\), for a sufficiently large constant \(C\).