The rank of random regular digraphs of constant degree

Alexander E. Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, Pierre Youssef

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

Let d be a (large) integer. Given n≥2d, let An be the adjacency matrix of a random directed d-regular graph on n vertices, with the uniform distribution. We show that the rank of An is at least n−1 with probability going to one as n grows to infinity. The proof combines the well known method of simple switchings and a recent result of the authors on delocalization of eigenvectors of An.

Original languageEnglish (US)
Pages (from-to)103-110
Number of pages8
JournalJournal of Complexity
Volume48
DOIs
StatePublished - Oct 2018

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • Mathematics(all)
  • Control and Optimization
  • Applied Mathematics

Keywords

  • Random matrices
  • Random regular graphs
  • Rank
  • Singularity probability

Fingerprint Dive into the research topics of 'The rank of random regular digraphs of constant degree'. Together they form a unique fingerprint.

  • Cite this

    Litvak, A. E., Lytova, A., Tikhomirov, K., Tomczak-Jaegermann, N., & Youssef, P. (2018). The rank of random regular digraphs of constant degree. Journal of Complexity, 48, 103-110. https://doi.org/10.1016/j.jco.2018.05.004