解法：马库斯–斯皮尔曼–斯里瓦斯塔瓦利用交错族给出的证明(2013年)

常见问题

先构造一个实根多项式,然后只是断言它等于我们想要的多项式,这难道不是循环论证吗?

不是——等式 $\mu[v_1v_1^*,\ldots,v_mv_m^*](x)=p(x)$ 本身就是 Marcus、Spielman 与 Srivastava 通过对微分算子 $\prod_i(1-\partial_{z_i})$ 直接计算而证明的一个定理,与实稳定性无关;实稳定性是关于中间对象 $\det(xI+\sum_i z_iA_i)$ 的另一项独立的结构性事实。这两个事实由不同的论证分别证明,只是在最后才结合在一起。

来源

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

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

arXiv:1306.3969v1

精简版

第 4/8 步：混合特征多项式:量身定制的实根平均

上一步下一步

通俗地说

Marcus、Spielman 与 Srivastava 对协方差矩阵 $A_i=\mathbb{E}[w_iw_i^*]$ 定义混合特征多项式 $\mu[A_1,\ldots,A_m]$ 。这个微分算子配方经过设计,使该多项式恰好等于独立随机秩一矩阵之和 $\sum_i w_iw_i^*$ 的期望特征多项式,而实稳定性保证其所有根都为实数。

\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^*]

详细分析

对于半正定协方差矩阵 $A_1,\ldots,A_m$ ,定义 $\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}$ 。起始行列式是实稳定的,微分算子与实数特化都保持实稳定性。论文定理4.1把这个多项式与协方差为 $A_i$ 的独立随机向量所给出的 $\mathbb{E}[\det(xI-\sum_i w_iw_i^*)]$ 等同,因此它有实根,也是交错论证所需的正确平均多项式。

本步骤中的术语

半正定矩阵: 所有特征值都非负的厄米矩阵;由单个向量 $v$ 构造出的 $v v^*$ 形式的矩阵总是半正定的。

本步骤用到的知识

算子理论