Principal Submatrices, Restricted Invertibility, and a Quantitative Gauss-Lucas Theorem

Abstract

We apply the techniques developed by Marcus, Spielman, and Srivastava, working with principal submatrices in place of rank-1 decompositions to give an alternate proof of their results on restricted invertibility. This approach recovers results of theirs' concerning the existence of well-conditioned column submatrices all the way up to the so-called modified stable rank. All constructions are algorithmic. The main novelty of this approach is that it leads to a new quantitative version of the classical Gauss-Lucas theorem on the critical points of complex polynomials. We show that for any degree n polynomial p and any c >= 1/2, the area of the convex hull of the roots of p(([cn])) is at most 4(c - c(2)) that of the area of the convex hull of the roots of p.