解法:马库斯–斯皮尔曼–斯里瓦斯塔瓦利用交错族给出的证明(2013年)
通俗地说
知道一个多项式是实根的,只能告诉我们根存在且性质良好,却不能告诉我们它们究竟有多大。为了确定具体数值,Marcus、Spielman 与 Srivastava 重新利用了 Batson、Spielman 与 Srivastava(2012年)最初为构造图的稀疏近似而发明的一种技术:一个「势垒函数」,它像是紧贴在最大根右侧的一道栅栏,当从上方逼近某个根时,其值会趋向无穷大。
策略是证明:每往运行中的和里再加入一个向量的贡献,都绝不会把这道栅栏推过某个固定位置,因此在加入全部 个向量之后,最大根仍被困在该固定位置之下——这就好比证明一摞箱子永远不会倒,只需检验每加入一个箱子时,重心的移动都不会太远。
详细分析
多变量势垒函数论证在逐个向量构造 的每一步都追踪一个势函数 (选定阈值 ):只要 超过 的所有特征值,这个量就是有限的,而当 从上方逼近最大特征值时,它会无界增长。Batson、Spielman 与 Srivastava 最初(针对单个矩阵)的势垒方法(2012年)表明,只要 一开始就低于某个固定的界,那么加入一个 足够小的秩一项 ,只会使势垒移动一个受控的小量。
Marcus、Spielman 与 Srivastava 把这一方法推广到多变量实稳定的场景:由于混合特征多项式可以逐个向量地构造(每加入一个 就对应于再对一个 求导),同样的势函数记账方式表明,在整个构造过程中, 的最大根始终保持在 之下,其中 ;这正是 Weaver 在 中猜想的常数。
这是整个证明中计算最密集的一步:正是在这里,实稳定性与交错族这套抽象机制被转化为一个诚实、可验证的数值不等式,弥合了「根是实数」与「根被证明至多为这个具体数值」之间的鸿沟。
- 势垒函数/势函数
- 一个关于矩阵的实值函数,例如 的迹,在 明显大于 的所有特征值时保持较小,而当 逼近最大特征值时会急剧增大;追踪这个量能定量控制某个操作能把最大特征值移动多少。