Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem

Abstract

We use the method of interlacing families of polynomials introduced to prove two theorems known to imply a positive solution to the Kadison--Singer problem. The first is Weaver's conjecture $K{S}_2$ \cite{weaver}, which is known to imply Kadison--Singer via a projection paving conjecture of Akemann and Anderson. The second is a formulation due to Casazza, et al., of Anderson's original paving conjecture(s), for which we are able to compute explicit paving bounds. The proof involves an analysis of the largest roots of a family of polynomials that we call the "mixed characteristic polynomials" of a collection of matrices.

This is the version that has been submitted

References in corpus (1)

• Polynomials, roots, and interlacing

Cited by in corpus (16)

• ${\ell }_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
• Ramanujan Graphs and the Solution of the Kadison-Singer Problem
• The Kadison-Singer Problem for Strongly Rayleigh Measures and Applications to Asymmetric TSP
• A Lyapunov type theorem from Kadison-Singer
• An Efficient Algorithm for Unweighted Spectral Graph Sparsification
• Exponential frames for unbounded sets
• Towards Constructing Ramanujan Graphs Using Shift Lifts
• Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
• A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees
• Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP
• Constant Arboricity Spectral Sparsifiers
• Exponential bases on triangular domains
• A note on the discrepancy of matrices with bounded row and column sums
• Median eigenvalues of bipartite graphs
• Worst possible sub-directions in high-dimensional models
• On the Markus-Spielman-Srivastava inequality for sums of rank-one matrices