The smallest singular value of a $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. 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\times 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}$, where $c_1$,  $c_2$, $C_1$, and $C_2$ are absolute positive constants. This is a joint work with A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, and P. Youssef

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.