Poorly Conditioned Minors of Random Matrices

Combinatorics Seminar
Friday, January 30, 2009 - 15:00
1 hour (actually 50 minutes)
Skiles 255
School of Mathematics, Georgia Tech
Part of Spielman and Teng's smoothed analysis of the Simplex algorithm relied on showing that most minors of a typical random rectangular matrix are well conditioned (do not have any singular values too close to zero). Motivated by this, Vershynin asked the question as to whether it was typically true that ALL minors of a random rectangular matrix are well conditioned. Here I will explain why that the answer to this question is in fact no: Even an n by 2n matrix will typically have n by n minors which have singular values exponentially close to zero.