Return to Colloquia & Seminar listing

### The norm of the inverse of a random matrix

**Colloquium**

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 R^{n}to R^{n}.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.