MathLabs

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

第 3/7 步:平方近乎神奇的带符号邻接矩阵
通俗地说

QnQ_n 通常的邻接矩阵在两个顶点相邻处记为 11,否则记为 00。黄皓则把其中一部分 11 的符号翻转,每一步递归地把矩阵规模翻倍,使得所得的 AnA_n 仍然编码 QnQ_n 完全相同的边,但其平方却是单位矩阵一个惊人简单的倍数。

An=(An−1II−An−1)A_n = \begin{pmatrix} A_{n-1} & I \\ I & -A_{n-1} \end{pmatrix}
详细分析

黄皓(2019年,引理2.2)递归地定义一列 2n×2n2^n \times 2^n 对称矩阵:A1=(0110)A_1 = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix},且当 n≥2n \ge 2 时 An=(An−1II−An−1)A_n = \begin{pmatrix} A_{n-1} & I \\ I & -A_{n-1} \end{pmatrix},其中 II 是相应大小的单位矩阵。AnA_n 的每个元素都属于 {−1,0,1}\{-1,0,1\},非零元素的位置恰好就是超立方体 QnQ_n 的边(通常邻接矩阵中的部分 11 被替换成了 −1-1)。

本步骤中的术语
带符号邻接矩阵
与普通邻接矩阵一样,非零元素标记图的边,但其中一部分元素是 −1-1 而非 11。
本步骤用到的知识