解法:黄皓用带符号超立方体邻接矩阵证明敏感度猜想(2019年)
通俗地说Qn 通常的邻接矩阵在两个顶点相邻处记为 1,否则记为 0。黄皓则把其中一部分 1 的符号翻转,每一步递归地把矩阵规模翻倍,使得所得的 An 仍然编码 Qn 完全相同的边,但其平方却是单位矩阵一个惊人简单的倍数。
详细分析黄皓(2019年,引理2.2)递归地定义一列 2n×2n 对称矩阵:A1=(0110),且当 n≥2 时 An=(An−1II−An−1),其中 I 是相应大小的单位矩阵。An 的每个元素都属于 {−1,0,1},非零元素的位置恰好就是超立方体 Qn 的边(通常邻接矩阵中的部分 1 被替换成了 −1)。
本步骤中的术语- 带符号邻接矩阵
- 与普通邻接矩阵一样,非零元素标记图的边,但其中一部分元素是 −1 而非 1。
本步骤用到的知识