解法:马库斯–斯皮尔曼–斯里瓦斯塔瓦利用交错族给出的证明(2013年)
通俗地说与其手动设计一个好的划分,不如让每个下标独立地以相等概率贡献零向量或缩放后的向量 2vi。所得的随机半正定矩阵是一个随机部分和,其协方差数据恰好是矩阵 vivi∗。交错论证会选出一个好结果;在结论处用标准的 r=2 直和提升得到两块划分。
详细分析对每个下标,以相等概率独立选择 wi∈{0,2vi} 中的一个随机向量,并构造随机矩阵 ∑iwiwi∗。其期望特征多项式是 p(x)=E[det(xI−∑iwiwi∗)]。wi 的协方差为 vivi∗,因此可以应用混合特征多项式机制。产生同时控制两组的划分依靠后面的直和提升,而不是关于符号的恒等式。
本步骤中的术语- 特征多项式
- 对方阵 A 而言,多项式 det(xI−A);它的根恰好就是 A 的特征值,因此界定最大根就是界定该矩阵最大的特征值。
- 算子范数
- 对厄米矩阵 A 而言,其算子范数 ∥A∥ 等于其特征值绝对值中的最大者;它衡量的是 A 能把任意单位向量拉伸的最大幅度。
本步骤用到的知识