TY - JOUR
T1 - The smallest singular value of a shifted d-regular random square matrix
AU - Litvak, Alexander E.
AU - Lytova, Anna
AU - Tikhomirov, Konstantin
AU - Tomczak-Jaegermann, Nicole
AU - Youssef, Pierre
N1 - Funding Information:
We are grateful to an anonymous referee for careful reading the first draft of the manuscript and many valuable suggestions, which helped us to improve presentation. The second and the third named authors would like to thank University of Alberta for excellent working conditions in January–August 2016, when a significant part of this work was done.
Publisher Copyright:
© 2018, Springer-Verlag GmbH Germany, part of Springer Nature.
PY - 2019/4/5
Y1 - 2019/4/5
N2 - 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.
AB - 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.
KW - Adjacency matrices
KW - Anti-concentration
KW - Condition number
KW - Invertibility
KW - Littlewood–Offord theory
KW - Random graphs
KW - Random matrices
KW - Regular graphs
KW - Singular probability
KW - Singularity
KW - Smallest singular value
KW - Sparse matrices
UR - http://www.scopus.com/inward/record.url?scp=85048835375&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85048835375&partnerID=8YFLogxK
U2 - 10.1007/s00440-018-0852-y
DO - 10.1007/s00440-018-0852-y
M3 - Article
AN - SCOPUS:85048835375
SN - 0178-8051
VL - 173
SP - 1301
EP - 1347
JO - Probability Theory and Related Fields
JF - Probability Theory and Related Fields
IS - 3-4
ER -