On the singularity of adjacency matrices for random regular digraphs

By Nicholas A. Cook. 2014

51 citations recorded by the source corpus.

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)\ge C\log ^2n$$min(d,n-d)≥Clog2n for a sufficiently large constant $$C>0$$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, proved in Cook (Random Struct Algorithms. arXiv:1410.5595, 2014). We also apply our general approach to prove asymptotically almost surely invertibility of Hadamard products $$\varSigma {{\mathrm{\circ }}}\varXi $$Σ∘Ξ, where $$\varXi $$Ξ is a matrix of iid uniform $$\pm 1$$±1 signs, and $$\varSigma $$Σ is a 0/1 matrix whose associated digraph satisfies certain “expansion” properties.

Subfields: Geometry and Topology, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/88a178bbcd1e8d1a049edfb876b8e063c72d3357

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geometry and Topology

  1. Larry Goldstein
  2. Tobias Johnson
  3. Nicholas A. Cook

In Mathematical Physics

  1. Tobias Johnson
  2. Larry Goldstein
  3. Nicholas A. Cook

In Statistics and Probability

  1. Tobias Johnson
  2. Larry Goldstein
  3. Nicholas A. Cook

Citations in the corpus