Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

While developing algorithms for the first computers, Von Neumann and Goldstine discovered problems with ill-conditioned inputs. Matrix inversion algorithms break down for matrices with big condition number, which is the ratio of the largest to the smallest singular values. They then experimented with large square matrices with random i.i.d. entries, and came to the conclusion that the condition number of random matrices should be linear in the dimension. Von Neumann-Goldstine's prediction and its refinement by Smale was proved only for Gaussian matrices by Edelman in 1985. The simplest unsolved case has been for Bernoulli matrices, whose entries are 1 or -1 with equal probability. I will describe a recent solution of Von Neumann-Golstine conjecture. It holds for all random matrices whose independent entries have bounded fourth moment. One new probabilistic ingredient in this work is a development of Littlewood-Offord theory of anti-concentration inequalities. I will describe its connections with ergodic theory and additive combinatorics. This is a joint work with Mark Rudelson.