MathLabs

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

第 2/8 步:把划分变成抛硬币:期望特征多项式
通俗地说

与其手动设计一个好的划分,不如让每个下标独立地以相等概率贡献零向量或缩放后的向量 2 vi\sqrt{2}\,v_i。所得的随机半正定矩阵是一个随机部分和,其协方差数据恰好是矩阵 vivi∗v_iv_i^*。交错论证会选出一个好结果;在结论处用标准的 r=2r=2 直和提升得到两块划分。

wi∈{0,2 vi} independently with equal probabilities,E[wiwi∗]=vivi∗w_i \in \{0,\sqrt{2}\,v_i\}\text{ independently with equal probabilities}, \qquad \mathbb{E}[w_iw_i^*]=v_iv_i^*
详细分析

对每个下标,以相等概率独立选择 wi∈{0,2 vi}w_i\in\{0,\sqrt{2}\,v_i\} 中的一个随机向量,并构造随机矩阵 ∑iwiwi∗\sum_i w_iw_i^*。其期望特征多项式是 p(x)=E[det⁡(xI−∑iwiwi∗)]p(x)=\mathbb{E}\big[\det(xI-\sum_i w_iw_i^*)\big]。wiw_i 的协方差为 vivi∗v_iv_i^*,因此可以应用混合特征多项式机制。产生同时控制两组的划分依靠后面的直和提升,而不是关于符号的恒等式。

本步骤中的术语
特征多项式
对方阵 AA 而言,多项式 det⁡(xI−A)\det(xI-A);它的根恰好就是 AA 的特征值,因此界定最大根就是界定该矩阵最大的特征值。
算子范数
对厄米矩阵 AA 而言,其算子范数 ∥A∥\|A\| 等于其特征值绝对值中的最大者;它衡量的是 AA 能把任意单位向量拉伸的最大幅度。
本步骤用到的知识