We will discuss two problems in quantitative linear algebra: (1) the existence of finite graphs with spectral gap matching that of their universal cover (2) Bourgain and Tzafriri's restricted invertibility theorem, an analytic version of the fact that the number of linearly independent columns in a matrix is equal to its rank.
In both cases, positive results can be proven by considering the zeros of the expected characteristic polynomials of certain random matrices and appealing to interlacing arguments. Remarkably, and somewhat mysteriously, these results turn out to be optimal because the same polynomials can be related to (infinite) limiting objects which show that the bounds they yield cannot be improved. We will examine this phenomenon and also mention connections to other fields such as free probability and operator algebras.
Back to Quantitative Linear Algebra Tutorials