Anna Lytova: On the smallest singular value of a d-regular random square matrix

Speaker: Anna Lytova

Title: On the smallest singular value of a 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 M be uniformly distributed on the set of all 0/1-valued n x n matrices such that each row and each column of a matrix has exactly d ones. 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}. This is a joint work with A. Litvak, K. Tikhomirov, N. Tomczak-Jaegermann, and P. Youssef