Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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 θⁿ 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ⁿ to Rⁿ.

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.