MathLabs

解法:黄皓用带符号超立方体邻接矩阵证明敏感度猜想(2019年)

第 4/7 步:一般事实:行和限制特征值
通俗地说

对任意图而言,无论边上如何标记 +1+1 与 −1-1 的符号,所得矩阵的最大特征值都不会超过任一顶点所连边数的最大值。直观地说,特征向量方程在每个坐标处都强制一种加权平衡,而这种平衡不可能超过参与其中的邻居数目。

Δ(H)≥λ1:=λ1(A)\Delta(H) \ge \lambda_1 := \lambda_1(A)
详细分析

黄皓(2019年,引理2.3)证明了一个简单但关键的事实:若 HH 是 mm 个顶点的图,AA 是元素属于 {−1,0,1}\{-1,0,1\}、非零模式与 HH 的边一致的任意对称矩阵,那么 Δ(H)≥λ1:=λ1(A)\Delta(H) \ge \lambda_1 := \lambda_1(A)。证明取最大特征值对应的特征向量 vv,并考察绝对值最大的坐标 v1v_1:由于 ∣λ1v1∣=∣(Av)1∣=∣∑j∼1A1,jvj∣≤Δ(H)∣v1∣|\lambda_1 v_1| = |(Av)_1| = \left|\sum_{j \sim 1} A_{1,j} v_j\right| \le \Delta(H)|v_1|,两边除以 ∣v1∣|v_1| 即得 λ1(A)≤Δ(H)\lambda_1(A) \le \Delta(H)。

本步骤中的术语
特征向量
满足 Av=λvAv = \lambda v(对应特征值 λ\lambda)的非零向量 vv;矩阵 AA 只改变 vv 的长度而不改变其方向。
本步骤用到的知识