on interlacing families and Kadison-Singer

Overview

Marcus, Spielman, and Srivastava solved the Kadison—Singer problem by proving a finite-dimensional vector partition theorem through interlacing families and mixed characteristic polynomials (Marcus, Spielman & Srivastava, 2015). The Annals paper does not attack pure states on operator algebras directly. Instead it proves Weaver’s discrepancy formulation and an Anderson paving formulation, both known to imply Kadison—Singer through earlier reductions (Kadison & Singer, 1959; Anderson, 1979; Weaver, 2004; Casazza et al., 2006).

The central innovation is a deterministic selection principle hidden inside a random construction. A random sum of independent rank-one positive semidefinite matrices has many possible characteristic polynomials. After each leaf polynomial is multiplied by its outcome probability, MSS show that the resulting polynomials form an interlacing family; since positive scalar weights do not change roots, one outcome has largest root no larger than the largest root of the expected characteristic polynomial (Marcus, Spielman & Srivastava, 2015a). The expected polynomial is a mixed characteristic polynomial. Real stability proves it is real-rooted, and a multivariate barrier argument bounds its largest root by $(1+\sqrt{\epsilon }{)}^2$.

Kadison—Singer and Paving

Let ${\ell }_2$ be the Hilbert space of square-summable complex sequences. Let $B({\ell }_2)$ be the algebra of bounded operators on ${\ell }_2$, and let $D\subset B({\ell }_2)$ be the diagonal subalgebra with respect to the standard basis. A state on a $C^{\ast }$-algebra is a positive linear functional of norm one, and a pure state is an extreme point of the convex set of states.

The Kadison—Singer problem asks whether every pure state on $D$ has a unique extension to a state on $B({\ell }_2)$ (Kadison & Singer, 1959). This is an operator-algebraic uniqueness question, but the successful proof passes through finite-dimensional matrix paving.

For a matrix $T\in {\mathbb{C}}^{n\times n}$ and a subset $S\subset [n]$, let $P_S$ be the coordinate projection onto $\mathrm{span}\{e_i:i\in S\}$. A paving of $T$ is a partition

$$[n]=S_1\bigsqcup \cdots \bigsqcup S_r$$

for which every compressed block

$$P_{S_j}T{P}_{S_j}$$

has small operator norm. Anderson’s paving formulation says that for every $\epsilon >0$ there is an integer $r$, independent of $n$, such that every zero-diagonal self-adjoint matrix $T$ admits a partition with

$$\Vert P_{S_j}T{P}_{S_j}\Vert \le \epsilon \Vert T\Vert ,j=1,\dots ,r.$$

The crucial phrase is independent of $n$. A partition number depending on dimension would not give the infinite-dimensional consequence. Anderson proved a finite paving route to Kadison—Singer, and MSS use a related formulation due to Casazza, Edidin, Kalra, and Paulsen to obtain explicit paving bounds (Anderson, 1979; Casazza et al., 2007).

The geometric content of paving is easier to see after translating it into vectors. A zero diagonal means that no single coordinate already carries the norm of the matrix. Paving asks whether the coordinates can be colored so that each color class destroys most of the off-diagonal interaction. Weaver’s formulation makes this a statement about splitting a decomposition of the identity.

Weaver’s Vector Partition Form

For vectors $u_1,\dots ,u_m\in {\mathbb{C}}^d$, write

$$U_i=u_i{u}_i^{\ast }$$

for the rank-one positive semidefinite matrix

$$x\mapsto ⟨x,u_i⟩u_i.$$

The identity

$$\sum _{i=1}^m{u}_i{u}_i^{\ast }=I_d$$

means that the vectors form a Parseval frame. Equivalently, for every unit vector $x\in {\mathbb{C}}^d$,

$$\sum _{i=1}^m|⟨x,u_i⟩{|}^2=1.$$

Thus the vectors distribute one unit of quadratic energy in every direction.

Weaver’s ${\mathrm{KS}}_2$ conjecture is a two-color version with a normalization parameter. It asserts the existence of universal constants $\eta \ge 2$ and $\theta >0$ such that the following holds. If

$$\Vert w_i\Vert \le 1$$

and

$$\sum _{i=1}^m|⟨x,w_i⟩{|}^2=\eta$$

for every unit vector $x$, then there is a partition $[m]=S_1\bigsqcup S_2$ such that

$$\sum _{i\in S_j}|⟨x,w_i⟩{|}^2\le \eta -\theta$$

for every unit vector $x$ and for $j=1,2$ (Weaver, 2004). In operator form this says

$$\Vert \sum _{i\in S_j}{w}_i{w}_i^{\ast }\Vert \le \eta -\theta .$$

This is a discrepancy statement, but not scalar discrepancy. Each vector contributes a rank-one matrix, and the goal is to split the matrix sum without allowing either color to retain almost all of the mass in any direction. The small norm assumption prevents a single vector from being an unavoidable obstruction.

MSS prove a stronger $r$-part version. If

$$\sum _{i=1}^m{u}_i{u}_i^{\ast }=I_d,\Vert u_i{\Vert }^2\le \delta ,$$

then for every positive integer $r$ there is a partition

$$[m]=S_1\bigsqcup \cdots \bigsqcup S_r$$

such that

$$\Vert \sum _{i\in S_j}{u}_i{u}_i^{\ast }\Vert \le {\left(\frac{1}{\sqrt{r}}+\sqrt{\delta }\right)}^2,j=1,\dots ,r.$$

This is the vector partition theorem that drives the paper (Marcus, Spielman & Srivastava, 2015b).

The constants in Weaver’s conjecture follow by setting $r=2$ and $u_i=w_i/\sqrt{\eta }$. Then

$$\sum _i{u}_i{u}_i^{\ast }=I,\Vert u_i{\Vert }^2\le \frac{1}{\eta }.$$

Choosing $\eta =18$ gives $\delta =1/18$, and

$${\left(\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{18}}\right)}^2=\frac{16}{18}.$$

Multiplying back by $\eta =18$ yields the bound $16=18-2$. Hence Weaver’s conjecture holds with

$$\eta =18,\theta =2.$$

Random Vectors and Deterministic Partitions

The partition theorem is deduced from a random-vector statement. Let $v_1,\dots ,v_m$ be independent random vectors in ${\mathbb{C}}^d$, each with finite support. Assume

$$\sum _{i=1}^m\mathbb{E}{v}_i{v}_i^{\ast }=I_d$$

and

$$\mathbb{E}\Vert v_i{\Vert }^2\le \epsilon \text{for every }i.$$

Then MSS prove

$$\mathbb{P}\left(\Vert \sum _{i=1}^m{v}_i{v}_i^{\ast }\Vert \le (1+\sqrt{\epsilon }{)}^2\right)>0.$$

The conclusion is intentionally only positive probability. Matrix Chernoff inequalities give high-probability norm bounds for random sums of positive semidefinite matrices, but the usual statements pay dimension-dependent or logarithmic losses in regimes relevant to Kadison—Singer (Tropp, 2012). MSS instead prove that at least one outcome is excellent, uniformly in dimension.

The reduction from this random-vector theorem to the partition theorem is useful because it exposes the role of the direct sum. Given $u_1,\dots ,u_m\in {\mathbb{C}}^d$, define $w_{i,k}\in {\mathbb{C}}^{rd}$ by placing $u_i$ in the $k$th block and zeros in the other $r-1$ blocks:

$$w_{i,k}=(0,\dots ,0,u_i,0,\dots ,0).$$

Let $v_i$ choose one of the $r$ vectors

$$\sqrt{r}{w}_{i,1},\dots ,\sqrt{r}{w}_{i,r}$$

uniformly at random. Then

$$\mathbb{E}{v}_i{v}_i^{\ast }=\mathrm{diag}(u_i{u}_i^{\ast },\dots ,u_i{u}_i^{\ast })$$

and therefore

$$\sum _i\mathbb{E}{v}_i{v}_i^{\ast }=I_{rd}.$$

Moreover

$$\mathbb{E}\Vert v_i{\Vert }^2=r\Vert u_i{\Vert }^2\le r\delta .$$

The random-vector theorem gives one assignment with

$$\Vert \sum _i{v}_i{v}_i^{\ast }\Vert \le (1+\sqrt{r\delta }{)}^2.$$

But for a fixed assignment, the sum is block diagonal. If $S_k$ is the set of indices assigned to block $k$, then the $k$th diagonal block is

$$r\sum _{i\in S_k}{u}_i{u}_i^{\ast }.$$

Dividing by $r$ gives

$$\Vert \sum _{i\in S_k}{u}_i{u}_i^{\ast }\Vert \le \frac{(1+\sqrt{r\delta }{)}^2}{r}={\left(\frac{1}{\sqrt{r}}+\sqrt{\delta }\right)}^2.$$

Thus a deterministic partition is extracted from an existence statement about a random block construction.

Characteristic Polynomials as Spectral Certificates

For a Hermitian matrix $M$, write

$${\chi }_M(x)=\det (xI-M).$$

The largest eigenvalue of $M$ is the largest root of ${\chi }_M$. Since each matrix

$$\sum _i{v}_i{v}_i^{\ast }$$

is positive semidefinite, controlling its operator norm is exactly controlling the largest root of its characteristic polynomial.

The challenge is that the random sum has many possible outcomes. A direct estimate of

$$\mathbb{E}\Vert \sum _i{v}_i{v}_i^{\ast }\Vert$$

would be too crude. MSS instead study the polynomial

$$\mathbb{E}{\chi }_{{\sum }_i{v}_i{v}_i^{\ast }}(x).$$

This expected characteristic polynomial is not the characteristic polynomial of the expected matrix. In general,

$$\mathbb{E}\det (xI-M)\ne \det (xI-\mathbb{E}M).$$

The expectation keeps track of higher-order spectral information.

The decisive selection principle is this: under the MSS hypotheses, one possible outcome has largest eigenvalue no larger than the largest root of the expected characteristic polynomial. This is false for arbitrary families of polynomials. The reason it holds here is that the probability-weighted outcome polynomials form an interlacing family; the weights are needed for the sums, but they do not affect the roots of individual outcomes.

Interlacing Families

Let $f_1,\dots ,f_k$ be real-rooted polynomials of the same degree with positive leading coefficients. They have a common interlacing if there is a real-rooted polynomial $g$ whose roots alternate with the roots of each $f_i$. The elementary consequence is that if

$$f_{\varnothing }=f_1+\cdots +f_k,$$

then at least one $f_i$ has largest root at most the largest root of $f_{\varnothing }$ (Marcus, Spielman & Srivastava, 2015a).

The intuition is that common interlacing imposes a one-dimensional order on the roots. When the polynomials are averaged, the largest root of the sum cannot lie strictly below the largest root of every summand. Therefore one summand is at least as good as the average from the perspective of the largest root.

The paper needs this lemma repeatedly. Suppose the possible outcomes are indexed by a Cartesian product

$$S_1\times \cdots \times S_m,$$

and let

$$f_{s_1,\dots ,s_m}(x)$$

be the characteristic polynomial of the leaf outcome. For a partial assignment $(s_1,\dots ,s_k)$ define

$$f_{s_1,\dots ,s_k}=\sum _{s_{k+1},\dots ,s_m}{f}_{s_1,\dots ,s_m}.$$

The family is an interlacing family if, at every node, the child polynomials have a common interlacing. Iterating the one-step lemma gives a leaf such that

$${\lambda }_{\max }(f_{s_1,\dots ,s_m})\le {\lambda }_{\max }(f_{\varnothing }),$$

where ${\lambda }_{\max }(f)$ denotes the largest root.

A useful criterion connects common interlacing to real-rootedness: polynomials $f_1,\dots ,f_k$ of the same degree and positive leading coefficient have a common interlacing if and only if every convex combination

$$\sum _{i=1}^k{\alpha }_i{f}_i,{\alpha }_i\ge 0,\sum _i{\alpha }_i=1,$$

is real-rooted (Dedieu, 1992; Fell, 1980; Chudnovsky & Seymour, 2007). Thus the problem becomes proving real-rootedness for many partial averages of characteristic polynomials.

Mixed Characteristic Polynomials

Let $v_1,\dots ,v_m$ be independent finite-support random column vectors in ${\mathbb{C}}^d$, and set

$$A_i=\mathbb{E}{v}_i{v}_i^{\ast }.$$

MSS prove the identity

$$\mathbb{E}{\chi }_{{\sum }_{i=1}^m{v}_i{v}_i^{\ast }}(x)={\prod _{i=1}^m(1-{\partial }_{z_i})\det \left(xI+\sum _{i=1}^m{z}_i{A}_i\right)|}_{z_1=\cdots =z_m=0}.$$

The right side depends only on the covariance matrices $A_i$, not on the full distributions of the $v_i$. It is called the mixed characteristic polynomial and is denoted

$$\mu [A_1,\dots ,A_m](x)={\prod _{i=1}^m(1-{\partial }_{z_i})\det \left(xI+\sum _{i=1}^m{z}_i{A}_i\right)|}_{z=0}.$$

The proof rests on a rank-one determinant identity. For any square matrix $A$ and random vector $v$,

$$\mathbb{E}\det (A-v{v}^{\ast })={(1-{\partial }_t)\det (A+t\mathbb{E}v{v}^{\ast })|}_{t=0}.$$

When $A$ is invertible, the matrix determinant lemma gives

$$\det (A-v{v}^{\ast })=\det (A)(1-v^{\ast }{A}^{-1}v).$$

Taking expectation and using

$$\mathbb{E}{v}^{\ast }{A}^{-1}v=\mathrm{tr}(A^{-1}\mathbb{E}v{v}^{\ast })$$

produces exactly the derivative of $\det (A+t\mathbb{E}v{v}^{\ast })$ at $t=0$. Singular $A$ follows by continuity. Applying this identity one random vector at a time yields the mixed characteristic polynomial formula.

This identity is the algebraic bridge of the proof. It says that random rank-one updates of characteristic polynomials can be averaged by applying differential operators to a deterministic determinant.

Real Stability

A polynomial $p(z_1,\dots ,z_m)\in \mathbb{C}[z_1,\dots ,z_m]$ is stable if

$$p(z_1,\dots ,z_m)\ne 0$$

whenever every $z_i$ has positive imaginary part. It is real stable if its coefficients are real. In one variable, real stability is exactly real-rootedness.

The determinant

$$\det \left(xI+\sum _{i=1}^m{z}_i{A}_i\right)$$

is real stable when the matrices $A_i$ are positive semidefinite Hermitian. This observation belongs to the Borcea—Branden theory of stable polynomials and mixed determinants (Borcea & Brändén, 2008; Borcea & Brändén, 2010). Stability is then preserved by the operators needed in the MSS proof:

• specializing a variable to a real value,
• differentiating with respect to a variable,
• applying operators of the form $1-{\partial }_{z_i}$ in the relevant stable setting.

Consequently

$$\mu [A_1,\dots ,A_m](x)$$

is real-rooted for positive semidefinite $A_i$.

This real-rootedness does two jobs. First, it makes the expected characteristic polynomial a legitimate object whose largest root can be bounded. Second, it proves the interlacing-family property. A partial average of the probability-weighted leaf characteristic polynomials corresponds to choosing probability weights for some of the finite-support vectors while fixing the previous choices. By the mixed characteristic polynomial identity, that partial average is again a mixed characteristic polynomial, up to a positive scalar factor. Hence it is real-rooted. The convex-combination criterion then gives common interlacings at each node.

Barrier Functions

It remains to bound the largest root of the mixed characteristic polynomial. Let $A_1,\dots ,A_m$ be positive semidefinite Hermitian matrices satisfying

$$\sum _{i=1}^m{A}_i=I_d,\mathrm{tr}{A}_i\le \epsilon .$$

MSS prove

$${\lambda }_{\max }(\mu [A_1,\dots ,A_m])\le (1+\sqrt{\epsilon }{)}^2.$$

The proof uses a multivariate analogue of the logarithmic derivative

$$\frac{p^{\prime }(x)}{p(x)}=\sum _j\frac{1}{x-{\lambda }_j}$$

for a univariate real-rooted polynomial $p(x)={\prod }_j(x-{\lambda }_j)$. This expression measures how close $x$ is to the roots; it becomes large near the largest root.

For a real stable polynomial $p(y_1,\dots ,y_m)$, say that a point $y\in {\mathbb{R}}^m$ is above the roots of $p$ if

$$p(y+t)>0$$

for every vector $t\in {\mathbb{R}}_{\ge 0}^m$. At such a point define the barrier function in direction $i$ by

$${\Phi }_p^i(y)=\frac{{\partial }_{y_i}p(y)}{p(y)}={\partial }_{y_i}\log p(y).$$

If the other coordinates are frozen, real stability gives a real-rooted univariate polynomial in $y_i$, and ${\Phi }_p^i$ is the sum of reciprocal distances to those roots.

Now set

$$P(y_1,\dots ,y_m)=\det \left(\sum _{i=1}^m{y}_i{A}_i\right).$$

Because ${\sum }_i{A}_i=I$, the point

$$t1,t=\sqrt{\epsilon }+\epsilon ,$$

is above the roots of $P$. Jacobi’s formula for the derivative of the determinant gives

$${\Phi }_P^i(y)=\mathrm{tr}\left({\left(\sum _{j=1}^m{y}_j{A}_j\right)}^{-1}{A}_i\right).$$

At $y=t1$ this becomes

$${\Phi }_P^i(t1)=\frac{\mathrm{tr}{A}_i}{t}\le \frac{\epsilon }{\sqrt{\epsilon }+\epsilon }.$$

Write

$$\varphi =\frac{\epsilon }{\sqrt{\epsilon }+\epsilon }$$

and choose

$$\Delta =\frac{1}{1-\varphi }=1+\sqrt{\epsilon }.$$

The mixed characteristic polynomial can be expressed in the homogeneous form

$$\mu [A_1,\dots ,A_m](x)={\prod _{i=1}^m(1-{\partial }_{y_i})P(y)|}_{y_1=\cdots =y_m=x}.$$

The task is therefore to apply the operators $1-{\partial }_{y_i}$ one by one without letting a root cross the final diagonal point.

The barrier lemma says, schematically, that if $y$ is above the roots of a real stable polynomial $p$ and the $j$th barrier is safely below $1$, then shifting in the $j$th coordinate by $\Delta$ keeps the new point above the roots of

$$p-{\partial }_{y_j}p$$

and does not increase the other barriers. The proof uses the monotonicity and convexity of barrier functions above the roots, together with stability-preserving properties of differentiation (Marcus, Spielman & Srivastava, 2015b; Marcus & Srivastava, 2017).

Define

$$P_k(y)=\prod _{i=1}^k(1-{\partial }_{y_i})P(y)$$

and let $x^k\in {\mathbb{R}}^m$ have its first $k$ coordinates equal to $t+\Delta$ and its remaining coordinates equal to $t$. Induction gives:

• $x^k$ is above the roots of $P_k$,
• every barrier ${\Phi }_{P_k}^i(x^k)$ is at most $\varphi$.

After all $m$ operators have been applied, the point

$$(t+\Delta )1$$

is above the roots of $P_m$. Therefore the largest root of the diagonal polynomial

$$P_m(x,\dots ,x)=\mu [A_1,\dots ,A_m](x)$$

is at most

$$t+\Delta =(\sqrt{\epsilon }+\epsilon )+(1+\sqrt{\epsilon })=(1+\sqrt{\epsilon }{)}^2.$$

This calculation is the quantitative heart of the paper. The trace bound $\mathrm{tr}{A}_i\le \epsilon$ controls the initial barriers. The shift $1+\sqrt{\epsilon }$ is precisely the margin needed so that each differential operator can be applied without losing control of the remaining directions.

Assembly of the Proof

The random-vector theorem follows by combining the preceding mechanisms.

Let

$$A_i=\mathbb{E}{v}_i{v}_i^{\ast }.$$

Then

$$\mathrm{tr}{A}_i=\mathbb{E}\mathrm{tr}(v_i{v}_i^{\ast })=\mathbb{E}\Vert v_i{\Vert }^2\le \epsilon ,$$

and

$$\sum _i{A}_i=I.$$

The barrier theorem gives

$${\lambda }_{\max }(\mu [A_1,\dots ,A_m])\le (1+\sqrt{\epsilon }{)}^2.$$

By the mixed characteristic polynomial identity,

$$\mu [A_1,\dots ,A_m](x)=\mathbb{E}{\chi }_{{\sum }_i{v}_i{v}_i^{\ast }}(x).$$

By real stability, all partial averages of the probability-weighted leaf characteristic polynomials are real-rooted, so these weighted leaf polynomials form an interlacing family. The interlacing selection theorem then gives one outcome $(v_1,\dots ,v_m)$ whose characteristic polynomial has largest root at most the largest root of the expected polynomial. Therefore

$$\Vert \sum _i{v}_i{v}_i^{\ast }\Vert \le (1+\sqrt{\epsilon }{)}^2.$$

Because the random variables have finite support, this outcome has positive probability. The vector partition theorem and Weaver’s ${\mathrm{KS}}_2$ follow from the block-assignment reduction described above.

Paving Consequences

The same vector partition theorem gives Anderson paving. MSS prove that every zero-diagonal self-adjoint matrix $T$ can be paved with

$$r=(6/\epsilon {)}^4$$

parts so that

$$\Vert P_{j}T{P}_j\Vert \le \epsilon \Vert T\Vert$$

for every block $j$ (Marcus, Spielman & Srivastava, 2015b). The reduction passes through projection paving: a zero-diagonal self-adjoint matrix is encoded into projections whose diagonal entries are controlled, and the vector partition theorem bounds the compressed pieces. The relevant finite-dimensional projection-paving formulation is due to Casazza, Edidin, Kalra, and Paulsen (Casazza et al., 2007).

For non-self-adjoint zero-diagonal matrices, one decomposes

$$T=A+iB$$

with $A$ and $B$ self-adjoint and zero diagonal. Paving $A$ and $B$ separately and refining the two partitions gives a paving for $T$, with a corresponding change in the number of parts. Thus the self-adjoint theorem supplies the general complex paving statement.

The operator-algebraic conclusion is inherited from the established equivalences. Kadison and Singer connected their uniqueness problem to paving phenomena, Anderson proved finite paving reductions, and Weaver’s vector discrepancy conjecture was known to imply the needed projection paving statement (Kadison & Singer, 1959; Anderson, 1979; Akemann & Anderson, 1991; Weaver, 2004). The contribution of MSS is the finite-dimensional polynomial method that proves the required vector and paving estimates.

Examples and Interpretation

The theorem is dimension-free because it measures the size of each summand by

$$\mathrm{tr}{A}_i=\mathbb{E}\Vert v_i{\Vert }^2,$$

not by the ambient dimension. This is the correct parameter for a rank-one positive semidefinite matrix: the trace equals its only nonzero eigenvalue.

A simple diagonal example illustrates the distinction between existence and typicality. Suppose many vectors point in coordinate directions, scaled so that

$$\sum _i{u}_i{u}_i^{\ast }=I.$$

A uniformly random partition can leave a coordinate overloaded, especially when the multiplicities are uneven. A carefully chosen partition can distribute repeated coordinate vectors almost evenly. MSS does not prove that the random partition usually succeeds; it proves that the space of all assignments contains one good leaf, certified by the roots of an average polynomial.

In contrast, for genuinely isotropic random vectors with no coordinate structure, concentration inequalities often do show that random assignments are good with high probability. Those results are powerful, but their constants and logarithmic factors are not the right tool for Kadison—Singer. The MSS method is closer to a refined probabilistic method: randomness generates a finite family, the expected characteristic polynomial summarizes the family, and interlacing selects a deterministic member.

Scope and Limitations

The argument is specialized to sums of independent rank-one positive semidefinite matrices. The rank-one determinant identity is what makes the expected characteristic polynomial depend only on the covariance matrices $A_i$. Higher-rank analogues require additional ideas and do not follow formally from the same proof.

The result is also existential in the Annals paper. The interlacing theorem proves that a good leaf exists, but it does not by itself give an efficient algorithm for finding the partition. Later work and related algorithmic questions study how to search such families, but the original Kadison—Singer breakthrough is a dimension-free existence proof.

Finally, the proof should not be interpreted as a general concentration theorem. It gives positive probability of an optimal-scale event under finite support and rank-one hypotheses. That is exactly what the paving and vector partition applications need, but it is different from a high-probability tail bound.

Transferable Mechanisms

• Interlacing can turn an average spectral certificate into a deterministic choice. This mechanism is explicit in the Ramanujan-graph paper and is reused in the Kadison—Singer paper (Marcus, Spielman & Srivastava, 2015a; Marcus, Spielman & Srivastava, 2015b). It is useful whenever the objects to be selected have characteristic polynomials whose partial averages remain real-rooted.

• Real stability is a robust invariant for preserving real-rootedness under multivariate operations. The MSS proof relies on Borcea—Branden stability theory, and Wagner’s survey explains the broader combinatorial role of stable polynomials (Borcea & Brändén, 2008; Borcea & Brändén, 2010; Wagner, 2011).

• Differential operators can encode rank-one random updates of determinants. The identity

$$\mathbb{E}\det (A-v{v}^{\ast })={(1-{\partial }_t)\det (A+t\mathbb{E}v{v}^{\ast })|}_{t=0}$$

shows how distributional averaging becomes algebraic manipulation of a determinant (Marcus, Spielman & Srivastava, 2015b). This idea is a useful template for problems where the random object enters through low-rank updates.

• Barrier functions provide a multivariate root-location method. Instead of expanding the mixed characteristic polynomial, MSS tracks reciprocal distances to roots while applying stability-preserving differential operators (Marcus, Spielman & Srivastava, 2015b; Marcus & Srivastava, 2017). This is a reusable way to convert local trace bounds into global spectral bounds.

• Small leverage scores are the correct hypothesis for dimension-free matrix partitioning. The condition $\Vert u_i{\Vert }^2\le \delta$ says no summand has excessive leverage in the identity decomposition. Related spectral sparsification work of Batson, Spielman, and Srivastava shows the same philosophy in a different form: control individual rank-one contributions, then select a sparse or balanced subcollection with spectral guarantees (Batson, Spielman & Srivastava, 2012).

See Also

• on Huang’s sensitivity conjecture proof --- Huang’s proof also turns a combinatorial problem into a sharp eigenvalue statement, but it uses Cauchy interlacing for principal submatrices rather than interlacing families of characteristic polynomials.
• on Sylvester’s determinantal identity and Schweinsian expansion --- The determinant identities there are the classical background for rank-one determinant manipulations and characteristic-polynomial calculations.
• on improved Nyström bounds --- Nyström approximation is another setting where sums and subspaces of positive semidefinite rank-one data are controlled through spectral norm estimates, although the sampling guarantees are probabilistic rather than interlacing-based.

References

🐻  Akemann, C.A. & Anderson, J. 1991. Lyapunov theorems for operator algebras, American Mathematical Society,p.

🐻  Anderson, J. 1979. Extensions, restrictions, and representations of states on C^*-algebras. Transactions of the American Mathematical Society 249(2), 303–329.

🐻  Batson, J., Spielman, D.A. & Srivastava, N. 2012. Twice-Ramanujan sparsifiers. SIAM Journal on Computing 41(6), 1704–1721.

🐻  Borcea, J. & Brändén, P. 2008. Applications of stable polynomials to mixed determinants: Johnson’s conjectures, unimodality, and symmetrized Fischer products. Duke Mathematical Journal 143(2), 205–223.

🐻  Borcea, J. & Brändén, P. 2010. Multivariate Pólya–Schur classification problems in the Weyl algebra. Proceedings of the London Mathematical Society 101(1), 73–104.

🐻  Casazza, P.G., Fickus, M., Tremain, J.C. & Weber, E. 2006. The Kadison–Singer problem in mathematics and engineering: A detailed account. In Operator Theory, Operator Algebras, and Applications, pp. 299–355. Contemporary Mathematics, American Mathematical Society.

🐻  Casazza, P.G., Edidin, D., Kalra, D. & Paulsen, V.I. 2007. Projections and the Kadison–Singer problem. Operators and Matrices 1(3), 391–408.

🐻  Chudnovsky, M. & Seymour, P. 2007. The roots of the independence polynomial of a clawfree graph. Journal of Combinatorial Theory, Series B 97(3), 350–357.

🐻  Dedieu, J.P. 1992. Obreschkoff’s theorem revisited: What convex sets are contained in the set of hyperbolic polynomials? Journal of Pure and Applied Algebra 81(3), 269–278.

🐻  Fell, H.J. 1980. Zeros of convex combinations of polynomials. Pacific Journal of Mathematics 89(1), 43–50.

🐻  Kadison, R.V. & Singer, I.M. 1959. Extensions of pure states. American Journal of Mathematics 81, 383–400.

🐻  Marcus, A.W. & Srivastava, N. 2017. A course on interlacing families. arXiv preprint arXiv:1712.08874.

🐻  Marcus, A.W., Spielman, D.A. & Srivastava, N. 2015a. Interlacing families I: Bipartite Ramanujan graphs of all degrees. Annals of Mathematics 182(1), 307–325.

🐻  Marcus, A.W., Spielman, D.A. & Srivastava, N. 2015b. Interlacing families II: Mixed characteristic polynomials and the Kadison–Singer problem. Annals of Mathematics 182(1), 327–350.

🐻  Tropp, J.A. 2012. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics 12(4), 389–434.

🐻  Wagner, D.G. 2011. Multivariate stable polynomials: Theory and applications. Bulletin of the American Mathematical Society 48(1), 53–84.

🐻  Weaver, N. 2004. The Kadison–Singer problem in discrepancy theory. Discrete Mathematics 278(1–3), 227–239.