On the singularity of adjacency matrices for random regular digraphs (Q510262): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: 1411.0243 / rank | |||
Normal rank |
Revision as of 14:31, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the singularity of adjacency matrices for random regular digraphs |
scientific article |
Statements
On the singularity of adjacency matrices for random regular digraphs (English)
0 references
17 February 2017
0 references
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\).
0 references
random digraphs
0 references
random matrices
0 references
singularity probability
0 references
discrepancy property
0 references