MathLabs

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

第 2/7 步:工具:柯西交错定理
通俗地说

若从一个对称矩阵中删去若干行及对应的列,较小矩阵的特征值不能偏离原矩阵的特征值太远:每一个都被原矩阵的两个特征值夹在中间。特别地,任意主子矩阵的最大特征值绝不会超过整个矩阵的最大特征值,但也不会低于列表中更靠后的某个特定特征值,具体取决于删去了多少行。

A symmetric n×n, B an m×m principal submatrix  ⟹  λi(A)≥λi(B)≥λi+n−m(A)A \text{ symmetric } n\times n,\ B \text{ an } m\times m \text{ principal submatrix} \implies \lambda_i(A) \ge \lambda_i(B) \ge \lambda_{i+n-m}(A)
详细分析

黄皓的证明(2019年,第2节)依赖于线性代数中的一个经典事实:柯西交错定理。设 AA 是特征值为 λ1≥⋯≥λn\lambda_1 \ge \cdots \ge \lambda_n 的 n×nn \times n 对称矩阵,BB 是通过删去 AA 中同一组行与列得到的 m×mm \times m 主子矩阵,其特征值为 μ1≥⋯≥μm\mu_1 \ge \cdots \ge \mu_m,那么对每个 1≤i≤m1 \le i \le m 都有 λi≥μi≥λi+n−m\lambda_i \ge \mu_i \ge \lambda_{i+n-m}。黄皓将其引用为引理2.1,并指出它可由柯朗–费歇尔–外尔极小极大原理导出。

本步骤中的术语
特征值
满足 Av=λvAv = \lambda v(某个非零向量 vv)的标量 λ\lambda;对实对称矩阵而言,所有特征值都是实数,可按降序排列。
主子矩阵
从方阵 AA 中删去同一组行下标与列下标之后剩下的矩阵。
本步骤用到的知识