Worked solution: Huang's signed hypercube adjacency matrix proof of the sensitivity conjecture (2019)

Step 3 of 7: A signed adjacency matrix with an almost magical square

In plain words

The usual adjacency matrix of $Q_n$ records a $1$ wherever two vertices are neighbours and a $0$ otherwise. Huang instead flips the sign of some of those $1$ 's, recursively doubling the matrix at each step, so that the resulting $A_n$ still encodes exactly the same edges of $Q_n$ but squares to a strikingly simple multiple of the identity.

A_n = \begin{pmatrix} A_{n-1} & I \\ I & -A_{n-1} \end{pmatrix}

Detailed analysis

Huang (2019, Lemma 2.2) defines a sequence of $2^n \times 2^n$ symmetric matrices recursively: $A_1 = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ and, for $n \ge 2$ , $A_n = \begin{pmatrix} A_{n-1} & I \\ I & -A_{n-1} \end{pmatrix}$ , where $I$ is the identity matrix of the appropriate size. Every entry of $A_n$ is in $\{-1,0,1\}$ , and the positions of the nonzero entries are exactly the edges of the hypercube $Q_n$ (only some of the $1$ 's of the usual adjacency matrix have been replaced by $-1$ 's).

Terms in this step

Signed adjacency matrix: A matrix whose nonzero entries mark the edges of a graph, as in an ordinary adjacency matrix, but where some of the entries are $-1$ instead of $1$ .

Knowledge used in this step

Matrices and determinants