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

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. More precisely, let $C_1<d<c_{1}n/{\log }^{2}n$ and let ${\mathcal{M}}_{n,d}$ be the set of all $0/1$-valued square $n\times n$ matrices such that each row and each column of a matrix $M\in {\mathcal{M}}_{n,d}$ has exactly $d$ ones. Let $M$ be uniformly distributed on ${\mathcal{M}}_{n,d}$. Then the smallest singular value $s_n(M)$ of $M$ is greater than $c_2{n}^{-6}$ with probability at least $1-C_2{\log }^{2}d/\sqrt{d}$, where $c_1$, $c_2$, $C_1$, and $C_2$ are absolute positive constants independent of any other parameters.

References in corpus (1)

• Lower bounds on the smallest eigenvalue of a sample covariance matrix

Cited by in corpus (2)

• On the second eigenvalue of random bipartite biregular graphs
• An upper bound on the smallest singular value of dense random combinatorial matrices