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

Frequently asked questions

If the average polynomial has a small root, why doesn't that immediately give a good sign assignment?

Determinants do not commute with averaging: $\mathbb{E}[\det(xI-M_\varepsilon)]$ can have a small root even if every individual $\det(xI-M_\varepsilon)$ has a large one, in the same way an average height can be moderate even though every single person is either very short or very tall. A genuinely new argument is needed to rule this out, which is exactly the role of interlacing families in the later steps.

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 2 of 8: Turning the partition into a coin flip: the expected characteristic polynomial

Previous step Next step

In plain words

Instead of trying to design a good partition by hand, let each index independently contribute either the zero vector or the rescaled vector $\sqrt{2}\,v_i$ , with equal probability. The resulting random positive semidefinite matrix is a random partial sum, and its covariance data are exactly the matrices $v_iv_i^*$ . A good outcome will be selected by the interlacing argument; the two-block partition is obtained by the standard $r=2$ direct-sum lift at the conclusion.

w_i \in \{0,\sqrt{2}\,v_i\}\text{ independently with equal probabilities}, \qquad \mathbb{E}[w_iw_i^*]=v_iv_i^*

Detailed analysis

For each index choose an independent random vector $w_i\in\{0,\sqrt{2}\,v_i\}$ with equal probabilities and form the random matrix $\sum_i w_iw_i^*$ . Its expected characteristic polynomial is $p(x)=\mathbb{E}\big[\det(xI-\sum_i w_iw_i^*)\big]$ . The covariance of $w_i$ is $v_iv_i^*$ , so the mixed-characteristic-polynomial machinery applies. The later direct-sum lift, rather than a sign identity, is what produces a partition controlling both blocks.

Terms in this step

Characteristic polynomial: For a square matrix $A$ , the polynomial $\det(xI-A)$ ; its roots are exactly the eigenvalues of $A$ , so bounding the largest root bounds the matrix's largest eigenvalue.
Operator norm: For a Hermitian matrix $A$ , its operator norm $\|A\|$ equals the largest absolute value among its eigenvalues; it measures the largest amount $A$ can stretch any unit vector.

Knowledge used in this step

Operator theory