# Mathematical Sciences Research Institute

Home » Workshop » Schedules » The smallest singular value of a $d$-regular random square matrix

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

## Geometric functional analysis and applications November 13, 2017 - November 17, 2017

November 17, 2017 (09:30 AM PST - 10:30 AM PST)
Speaker(s): Alexander Litvak (University of Alberta)
Location: MSRI: Simons Auditorium
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC
Video

#### 17-Litvak

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\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

Supplements