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

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 < c n / 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 an...

Full description

Saved in:
Bibliographic Details
Published in:Probability theory and related fields 2019-04, Vol.173 (3-4), p.1301-1347
Main Authors: Litvak, Alexander E., Lytova, Anna, Tikhomirov, Konstantin, Tomczak-Jaegermann, Nicole, Youssef, Pierre
Format: Article
Language:English
Subjects:
Economics
Finance
Graph theory
Insurance
Lower bounds
Management
Mathematical and Computational Biology
Mathematical and Computational Physics
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Parameter estimation
Probability
Probability Theory and Stochastic Processes
Quantitative Finance
Statistics for Business
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 < c n / 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 - C 2 log 2 d / 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 - z Id , where Id is the identity matrix and z is a fixed complex number.
ISSN:0178-8051
1432-2064
DOI:10.1007/s00440-018-0852-y