解法:黄皓用带符号超立方体邻接矩阵证明敏感度猜想(2019年)
通俗地说对任意图而言,无论边上如何标记 +1 与 −1 的符号,所得矩阵的最大特征值都不会超过任一顶点所连边数的最大值。直观地说,特征向量方程在每个坐标处都强制一种加权平衡,而这种平衡不可能超过参与其中的邻居数目。
详细分析黄皓(2019年,引理2.3)证明了一个简单但关键的事实:若 H 是 m 个顶点的图,A 是元素属于 {−1,0,1}、非零模式与 H 的边一致的任意对称矩阵,那么 Δ(H)≥λ1:=λ1(A)。证明取最大特征值对应的特征向量 v,并考察绝对值最大的坐标 v1:由于 ∣λ1v1∣=∣(Av)1∣=∑j∼1A1,jvj≤Δ(H)∣v1∣,两边除以 ∣v1∣ 即得 λ1(A)≤Δ(H)。
本步骤中的术语- 特征向量
- 满足 Av=λv(对应特征值 λ)的非零向量 v;矩阵 A 只改变 v 的长度而不改变其方向。
本步骤用到的知识