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

Frequently asked questions

Isn't it circular to build a real-rooted polynomial and then just claim it equals the polynomial we wanted?

No — the equality $\mu[v_1v_1^*,\ldots,v_mv_m^*](x)=p(x)$ is itself a theorem that Marcus, Spielman and Srivastava prove by direct computation with the differential operator $\prod_i(1-\partial_{z_i})$ , independent of real stability; real stability is a separate structural fact about the intermediate object $\det(xI+\sum_i z_iA_i)$ . The two facts are proved by different arguments and only combined at the end.

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 4 of 8: The mixed characteristic polynomial: a real-rooted average, built to order

Previous step Next step

In plain words

Marcus, Spielman and Srivastava define the mixed characteristic polynomial $\mu[A_1,\ldots,A_m]$ for covariance matrices $A_i=\mathbb{E}[w_iw_i^*]$ . Their differential-operator recipe is engineered so that this polynomial is exactly the expected characteristic polynomial of the sum of independent random rank-one matrices $\sum_i w_iw_i^*$ , while real stability guarantees that all its roots are real.

\mu[A_1,\ldots,A_m](x) := \prod_{i=1}^m\Big(1-\partial_{z_i}\Big)\det\Big(xI+\sum_i z_i A_i\Big)\Big|_{z=0},\qquad A_i=\mathbb{E}[w_iw_i^*]

Detailed analysis

For positive semidefinite covariance matrices $A_1,\ldots,A_m$ , define $\mu[A_1,\ldots,A_m](x) := \prod_{i=1}^m(1-\partial_{z_i})\det\big(xI+\sum_i z_iA_i\big)\big|_{z=0}$ . The starting determinant is real stable, and the differential operators and real specialization preserve real stability. Theorem 4.1 of the paper identifies this polynomial with $\mathbb{E}[\det(xI-\sum_i w_iw_i^*)]$ for independent random vectors having covariances $A_i$ , so it is real-rooted and is the correct average for the interlacing argument.

Terms in this step

Positive semidefinite matrix: A Hermitian matrix all of whose eigenvalues are non-negative; matrices of the form $v v^*$ built from a single vector $v$ are always positive semidefinite.

Knowledge used in this step

Operator theory