Worked solution: Marcus–Spielman–Srivastava proof via interlacing families (2013)

Frequently asked questions

Why can real vectors be added one at a time when the polynomial construction used derivatives with respect to all variables at once?

The multivariate real stable polynomial and its derivatives are a bookkeeping device that is fully determined once all the $v_i$ are fixed; the barrier argument re-examines this same finished construction step by step, in the order the vectors were listed, purely as a proof technique for bounding the final root — it does not require literally re-deriving a new polynomial at each step.

Source

Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava, 2013

Interlacing Families II: Mixed Characteristic Polynomials and The Kadison–Singer Problem

arXiv:1306.3969v1

Condensed summary

Step 6 of 8: The barrier function: computing the root bound by hand

Previous step Next step

In plain words

Knowing a polynomial is real-rooted tells you its roots exist and behave nicely, but not how large they actually are. To pin down the actual number, Marcus, Spielman and Srivastava reuse a technique originally invented by Batson, Spielman and Srivastava (2012) for building sparse approximations of graphs: a "barrier function" that acts like a fence just to the right of the largest root, whose value blows up to infinity as you approach a root from above.

The strategy is to show that adding one more vector's contribution to the running sum never pushes this fence past a fixed position, so after adding all $m$ vectors the largest root is still trapped below that fixed position — like proving a stack of boxes never tips over by checking that no single box added ever shifts the centre of gravity too far.

\Phi^u(A) := \operatorname{tr}(uI-A)^{-1}, \qquad \text{roots of } p(x) \le \max\{u : \Phi^u \text{ stays below a fixed threshold}\}

Detailed analysis

The multivariate barrier function argument tracks, at each step of building up $A = \sum_{i \le k} v_iv_i^*$ one vector at a time, a potential $\Phi^u(A) = \operatorname{tr}(uI-A)^{-1}$ for a chosen threshold $u$ : this quantity is finite as long as $u$ exceeds every eigenvalue of $A$ , and it grows without bound as $u$ approaches the largest eigenvalue from above. Batson, Spielman and Srivastava's original (single-matrix) barrier method (2012) shows that adding one rank-one term $vv^*$ with $\|v\|^2$ small enough moves the barrier by only a controlled, small amount, as long as $\Phi^u(A)$ started below a fixed bound.

Marcus, Spielman and Srivastava extend this to the multivariate real stable setting: since the mixed characteristic polynomial can be built up one vector at a time (adding one $v_iv_i^*$ at a time corresponds to differentiating with respect to one more $z_i$ ), the same potential-function bookkeeping shows the largest root of $p(x)$ stays below $u^* = (1+\sqrt{2\delta})^2/2$ throughout the whole construction, for $\delta = \max_i \|v_i\|^2$ ; this is precisely Weaver's conjectured constant from $KS_2$ .

This is the most computational step in the whole proof: it is where the abstract machinery of real stability and interlacing families gets converted into an honest, checkable numerical inequality, closing the gap between "the roots are real" and "the roots are provably at most this specific number".

Terms in this step

Barrier function / potential function: A real-valued function of a matrix, such as the trace of $(uI-A)^{-1}$ , that stays small while $u$ is comfortably above all eigenvalues of $A$ and blows up as $u$ approaches the largest eigenvalue; tracking it gives quantitative control on how much an operation can move the largest eigenvalue.

Knowledge used in this step

Operator theory