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 ₁ < d< cn/ log ² 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 ₁ , and C ₂ 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.