Structure of eigenvectors of random regular digraphs

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

Research output: Contribution to journalArticle

Abstract

Let d and n be integers satisfying C ≤ d ≤ exp(Formula Presented) for some universal constants c, C > 0, and let z ∈ C. Denote by M the adjacency matrix of a random d-regular directed graph on n vertices. In this paper, we study the structure of the kernel of submatrices of M - z Id, formed by removing a subset of rows. We show that with large probability the kernel consists of two nonintersecting types of vectors, which we call very steep and gradual with many levels. As a corollary, we show, in particular, that every eigenvector of M, except for constant multiples of (1, 1,..., 1), possesses a weak delocalization property: Its level sets have cardinality less than Cn ln2 d/ ln n. For a large constant d, this provides principally new structural information on eigenvectors, implying that the number of their level sets grows to infinity with n. As a key technical ingredient of our proofs, we introduce a decomposition of Cn into vectors of different degrees of “structuredness”, which is an alternative to the decomposition based on the least common denominator in the regime when the underlying random matrix is very sparse.

Original languageEnglish (US)
Pages (from-to)8097-8172
Number of pages76
JournalTransactions of the American Mathematical Society
Volume371
Issue number11
DOIs
StatePublished - 2019

Keywords

  • Delocalization of eigenvectors
  • Littlewood-Offord theory
  • Random graphs
  • Random matrices
  • Regular graphs
  • Sparse matrices
  • Structure of the kernel

ASJC Scopus subject areas

  • Mathematics(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Structure of eigenvectors of random regular digraphs'. Together they form a unique fingerprint.

  • Cite this

    Litvak, A. E., Lytova, A., Tikhomirov, K., Tomczak-Jaegermann, N., & Youssef, P. (2019). Structure of eigenvectors of random regular digraphs. Transactions of the American Mathematical Society, 371(11), 8097-8172. https://doi.org/10.1090/tran/7742