Friday, January 29, 2016 (3:00 p.m. in Yost 306)

Title: Non-Asymptotic Approach in Random Matrix Theory

Speaker: Mark Rudelson (Professor, Department of Mathematics, University of Michigan-Ann Arbor)

Hosted by Elisabeth Werner

Abstract: Random matrices arise naturally in various contexts ranging from theoretical physics to computer science. In a large part of these problems, it is important to know the behavior of the spectral characteristics of a random matrix of a large but fixed size.

We will discuss a recent progress in this area illustrating it by problems coming from different directions:

Condition number of “full” and sparse random matrices. Consider a system of linear equationsAx=b where the right hand side is known only approximately. In the process of solving this system, the error in vector b gets magnified by the condition number of the matrix A. A conjecture of von Neumann that with high probability, the condition number of an n x n random matrix with independent entries is O(n) has been proven several years ago. We will discuss this result as well as the possibility of its extension to sparse matrices.

The Single Ring Phenomenon. It was observed by physicists, that the eigenvalues of a large random matrix with a prescribed distribution of the singular values densely fill a single ring in the complex plane even if the distribution of the singular values has gaps. This phenomenon has been rigorously verified recently.

Random matrices in combinatorics. A perfect matching in a graph with an even number of vertices is a pairing of vertices connected by edges of the graph. Evaluating or even estimating the number of perfect matchings in a given graph deterministically may be computationally expensive. We will discuss an application of the random matrix theory to estimating the number of perfect matchings in a deterministic graph.