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 ? c2) that of the area of the convex hull of the roots of p. © The Author(s) 2018. Published by Oxford University Press. All rights reserved. For permissions