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

Step 3 of 8: Real stable polynomials: a multivariable notion of "all roots are real"

In plain words

For a single-variable polynomial, having only real roots is a strong and useful property: it means the polynomial's graph only touches the $x$ -axis, never dips into complex territory. Real stability is the natural generalisation of this idea to polynomials in several variables at once, and it turns out to behave remarkably well under the operations — sums, products, substitutions, derivatives — that come up when juggling many matrices simultaneously.

This single algebraic property, built on decades of work by Borcea and Brändén on the Lee–Yang program from statistical physics, is the load-bearing wall of the whole proof: everything downstream depends on being able to certify it once and then push it through several transformations for free.

p(z_1,\ldots,z_m) \text{ real stable} \iff p(z_1,\ldots,z_m)\ne 0 \text{ whenever } \operatorname{Im}(z_i) > 0 \ \forall i

Detailed analysis

A multivariate polynomial $p(z_1,\ldots,z_m)$ with real coefficients is called real stable if $p(z_1,\ldots,z_m) \ne 0$ whenever every variable $z_i$ has strictly positive imaginary part; when $m=1$ this reduces exactly to having only real roots. Real stability was developed as a systematic theory by Julius Borcea and Petter Brändén (2008–2010), extending classical work of Lee and Yang in statistical physics and of Heilmann and Lieb on monomer–dimer polynomials.

The crucial engineering fact that makes real stability so powerful is that it is preserved by a short list of operations: setting variables equal to each other, differentiation, and certain linear substitutions all send real stable polynomials to real stable polynomials (with one fewer variable, in the first two cases). This lets one build complicated real stable polynomials out of simple building blocks and extract single-variable real-rooted polynomials from them by specialising variables — exactly the toolkit needed to define the family of polynomials from the previous step precisely.

In the next step, this machinery is applied to the specific matrices $v_iv_i^*$ arising in Weaver's $KS_2$ , producing the "mixed characteristic polynomial" that is the true protagonist of the Marcus–Spielman–Srivastava proof.

Terms in this step

Real stability: A multivariate generalisation of "having only real roots": a polynomial $p(z_1,\ldots,z_m)$ is real stable if it never vanishes when all variables are simultaneously placed in the open upper half of the complex plane.

Knowledge used in this step

Operator theory Functions of a complex variable