Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The norm of the inverse of a random matrix


Speaker: Mark Rudelson, University of Missouri-Columbia
Location: 1147 MSB
Start time: Tue, Oct 17 2006, 5:15PM

Let A be an n by n random matrix, whose entries are centered i.i.d. subgaussian random variables. This class includes, in particular, random matrices, whose entries are independent random variables taking values +-1 with probability 1/2. Estimating the probability that such matrix is singular is a highly non-trivial problem even for such matrices. Komlós proved that this probability is o(1) as n → ∞. This result was improved by Kahn, Komlós and Szemerédi, and later by Tao and Vu, who showed that this probability is bounded above by θn where θ=3/4+o(1) (the conjectured value is θ=1/2+o(1)). However, these results do not address the quantitative characterization of invertibility, namely bounds for the norm of the inverse matrix, considered as an operator from Rn to Rn.

We show that with high probability, a subgaussian random matrix will be non-singular, and the norm of its inverse is polynomially bounded in terms of n.

Note that the colloquium is moved an hour and five minutes later because of the Rock Memorial.