The smallest singular value of a shifted d-regular random square matrix

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

Research output: Contribution to journalArticle

Abstract

We derive a lower bound on the smallest singular value of a random d-regular matrix, that is, the adjacency matrix of a random d-regular directed graph. Specifically, let C 1 < d< cn/ log 2 n and let M n , d be the set of all n× n square matrices with 0 / 1 entries, such that each row and each column of every matrix in M n , d has exactly d ones. Let M be a random matrix uniformly distributed on M n , d . Then the smallest singular value s n (M) of M is greater than n - 6 with probability at least 1-C2log2d/d, where c, C 1 , and C 2 are absolute positive constants independent of any other parameters. Analogous estimates are obtained for matrices of the form M-zId, where Id is the identity matrix and z is a fixed complex number.

Original languageEnglish (US)
Pages (from-to)1301-1347
Number of pages47
JournalProbability Theory and Related Fields
Volume173
Issue number3-4
DOIs
StatePublished - Apr 5 2019

All Science Journal Classification (ASJC) codes

  • Analysis
  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

  • Adjacency matrices
  • Anti-concentration
  • Condition number
  • Invertibility
  • Littlewood–Offord theory
  • Random graphs
  • Random matrices
  • Regular graphs
  • Singular probability
  • Singularity
  • Smallest singular value
  • Sparse matrices

Fingerprint Dive into the research topics of 'The smallest singular value of a shifted d-regular random square matrix'. Together they form a unique fingerprint.

  • Cite this

    Litvak, A. E., Lytova, A., Tikhomirov, K., Tomczak-Jaegermann, N., & Youssef, P. (2019). The smallest singular value of a shifted d-regular random square matrix. Probability Theory and Related Fields, 173(3-4), 1301-1347. https://doi.org/10.1007/s00440-018-0852-y