The rank of random regular digraphs of constant degree

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

doi:10.1016/j.jco.2018.05.004

The rank of random regular digraphs of constant degree

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

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

Let d be a (large) integer. Given n≥2d, let A_n be the adjacency matrix of a random directed d-regular graph on n vertices, with the uniform distribution. We show that the rank of A_n 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 A_n.

Original language	English (US)
Pages (from-to)	103-110
Number of pages	8
Journal	Journal of Complexity
Volume	48
DOIs	https://doi.org/10.1016/j.jco.2018.05.004
State	Published - Oct 2018

Keywords

Random matrices
Random regular graphs
Rank
Singularity probability

ASJC Scopus subject areas

Algebra and Number Theory
Statistics and Probability
Numerical Analysis
General Mathematics
Control and Optimization
Applied Mathematics

Access to Document

10.1016/j.jco.2018.05.004

Cite this

@article{1909d3a1561b4473849ad2fdd4653ba9,

title = "The rank of random regular digraphs of constant degree",

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.",

keywords = "Random matrices, Random regular graphs, Rank, Singularity probability",

author = "Litvak, {Alexander E.} and Anna Lytova and Konstantin Tikhomirov and Nicole Tomczak-Jaegermann and Pierre Youssef",

note = "Funding Information: P.Y. was supported by grant ANR - 16-CE40-0024-01 . A significant part of this work was completed while the last three named authors were in residence at the Mathematical Sciences Research Institute in Berkeley, California, supported by NSF grant DMS-1440140 , and the first two named authors visited the institute. The hospitality of MSRI and of the organizers of the program on Geometric Functional Analysis and Applications is gratefully acknowledged. Funding Information: P.Y. was supported by grant ANR-16-CE40-0024-01. A significant part of this work was completed while the last three named authors were in residence at the Mathematical Sciences Research Institute in Berkeley, California, supported by NSF grant DMS-1440140, and the first two named authors visited the institute. The hospitality of MSRI and of the organizers of the program on Geometric Functional Analysis and Applications is gratefully acknowledged. Publisher Copyright: {\textcopyright} 2018 Elsevier Inc.",

year = "2018",

month = oct,

doi = "10.1016/j.jco.2018.05.004",

language = "English (US)",

volume = "48",

pages = "103--110",

journal = "Journal of Complexity",

issn = "0885-064X",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - The rank of random regular digraphs of constant degree

AU - Litvak, Alexander E.

AU - Lytova, Anna

AU - Tikhomirov, Konstantin

AU - Tomczak-Jaegermann, Nicole

AU - Youssef, Pierre

N1 - Funding Information: P.Y. was supported by grant ANR - 16-CE40-0024-01 . A significant part of this work was completed while the last three named authors were in residence at the Mathematical Sciences Research Institute in Berkeley, California, supported by NSF grant DMS-1440140 , and the first two named authors visited the institute. The hospitality of MSRI and of the organizers of the program on Geometric Functional Analysis and Applications is gratefully acknowledged. Funding Information: P.Y. was supported by grant ANR-16-CE40-0024-01. A significant part of this work was completed while the last three named authors were in residence at the Mathematical Sciences Research Institute in Berkeley, California, supported by NSF grant DMS-1440140, and the first two named authors visited the institute. The hospitality of MSRI and of the organizers of the program on Geometric Functional Analysis and Applications is gratefully acknowledged. Publisher Copyright: © 2018 Elsevier Inc.

PY - 2018/10

Y1 - 2018/10

N2 - 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.

AB - 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.

KW - Random matrices

KW - Random regular graphs

KW - Rank

KW - Singularity probability

UR - http://www.scopus.com/inward/record.url?scp=85047378427&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85047378427&partnerID=8YFLogxK

U2 - 10.1016/j.jco.2018.05.004

DO - 10.1016/j.jco.2018.05.004

M3 - Article

AN - SCOPUS:85047378427

SN - 0885-064X

VL - 48

SP - 103

EP - 110

JO - Journal of Complexity

JF - Journal of Complexity

ER -

The rank of random regular digraphs of constant degree

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this