Question about two matrices: Hadamard v. "the magical one" in the proof of the sensitivity conjecture

Question

The recent and incredibly slick proof of the sensitivity conjecture relies on the explicit* construction of a matrix $A_n\in\{-1,0,1\}^{2^n\times 2^n}$, defined recursively as follows: $$A_1 = \begin{pmatrix} 0&1\\1&0\end{pmatrix}$$ and, for $n\geq 2$, $$A_{n} = \begin{pmatrix} A_{n-1}&I_{n-1}\\I_{n-1}&-A_{n-1}\end{pmatrix}$$ In particular, it is easy to see that $A_n^2 = n I_n$ for all $n\geq 1$.

Now, maybe I am reading too much into this, but this looks at least syntactically related to another famous family of matrices, the Hadamard matrices, which is also such that $H_n^2 \propto I_n$ and has 'similar' spectrum: $$H_1 = \begin{pmatrix} 1&1\\1&-1\end{pmatrix}$$ and, for $n\geq 2$, $$H_{n} = \begin{pmatrix} H_{n-1}&H_{n-1}\\H_{n-1}&-H_{n-1}\end{pmatrix}$$

Is there any formal connection, possibly useful, between the two, except that "they look vaguely similar"?

For instance, $A_n$ seen as the signed adjacency matrix of the hypercube $\{0,1\}^n$ has a nice interpretation (the sign of an edge $(x,b,x')\in\{0,1\}^n$ is the parity of the prefix $x$). Is there an analogue for $H_n$? (this may be obvious?)

$^*$ I am also wondering if a non-explicit construction, e.g., a uniformly random $\pm1$ matrix, would have the desired spectral properties, but that'd probably have to wait for another question.

Answer 1

An observation too long for a comment (and which also fits well with Jason Gaitonde's observation-too-long-for-comment):

As hinted at in the OQ, both of these can in fact be realized by a very simple kind of recursive construction. Namely, we specify $B_0 \in \{(0), (\pm 1)\}$ (a $1 \times 1$ matrix), and then a single recursive formula

$$ B_n = \left(\begin{array}{cc} b_{11} & b_{12} \\ b_{21} & b_{22} \end{array}\right) $$

where each $b_{ij}$ is one of $\{0, \pm 1, \pm x\}$ (where here "1" denotes the identity of the appropriate size, namely $2^{n-1} \times 2^{n-1}$, and similarly "0" denotes the zero matrix of the appropriate size, and $x$ denotes $B_{n-1}$). For the Huang matrices, we actually have $A_0 = (0)$ and the recursive formula is $\begin{bmatrix} x & 1 \\ 1 & -x \end{bmatrix}$, while for the Hadamard matrices we have $H_0 = (1)$ and the recursive formula is $\begin{bmatrix} x & x \\ x & -x \end{bmatrix}$.

If one wants such a recursion to have the property that $B_n^2$ is proportional to $I_{2^{n}}$, then one quickly finds that either $b_{11} + b_{22} = 0$, or $b_{12} = b_{21}=0$. In the latter case, the recursion only yield diagonal matrices, which is maybe not so interesting. So the interesting cases are those in which $b_{11} = -b_{22}$ (which is one of the "niceness" conditions in Jason's answer). This can also be seen as a common explanation for why both sequences of matrices are traceless.

As a last small comment, this kind of recursion automatically yields that the block entries of $B_n$ commute, which was the other "niceness" condition in Jason's answer.

I haven't yet done a systematic investigation, but given the above setup, one could investigate the finitely many possibilities (3 choices for $B_0$, and technically $5^4$ choices for the recursion, but this can be cut down using symmetries and also from the restrictions that $B_n^2$ is proportional to the identity). It would be very pleasing to learn that the Hadamard and the Huang matrices are somehow, up to equivalence, the only two nontrivial ones :). And if not, maybe there are some other interesting ones lurking out there...

Answer 2

Here's just a couple of observations I couldn't fit in a comment:

0) Added because the first answer was deleted: there is an interpretation of $H_n$, namely, indexing the rows and columns by $\{0,1\}^n$, the entry corresponding to $(x,y)$ is $1$ if the Hadamard product $x\odot y=(x_1y_1,\ldots,x_n y_n)$ has even parity, and $-1$ if it has odd parity.

1) In general, the spectrum of block matrices can be very complicated and not obviously related to the spectra of the individual blocks, as the characteristic polynomial will look awful. But for a symmetric block matrix $M=\begin{pmatrix} A & B\\ B^T & C\end{pmatrix}$ that might arise via a recursive construction like the $A_n$ and $H_n$ above, where each matrix is square, one of the only simplifications occurs when $B^T$ and $C$ commute, in which case one has $\det(M)=\det(AC-BB^T)$. Then the characteristic polynomial of $M$ will be $$\det((\lambda I-A)(\lambda I-C)-BB^T)=\det(\lambda^2I-\lambda (A+C)+AC-BB^T).$$ For this to lead to nice recursive formulas for the eigenvalues, one basically needs $C=-A$ to kill the linear $\lambda$ term. If further $A$ and $B$ are symmetric and commute, we get $$ \det(\lambda I-M)=\det(\lambda^2 I-(A^2+B^2)), $$ from which one easily reads off the eigenvalues using the fact symmetric commuting matrices admit a common eigenbasis. This might be obvious, but all of this is to say that as far as getting good, recursive formulas for the eigenvalues, it is basically essential to require the lower right block to be $-A$ and hope that lower left and upper right blocks are symmetric and commute with $A$, which is the case for the $A_n$ (with $B=I$) and $H_n$ matrices (with $B=H_{n-1}=A$).

2) On the random sign question: the signing of the adjacency matrix given in the paper is optimal in the sense of maximizing $\lambda_{2^{n-1}}$, which is needed for the lower bound via Cauchy interlacing, and can be seen from elementary means. For an arbitrary signing $M_n$ of the adjacency matrix of the $n$-dimensional hypercube, one immediately gets $$ \text{Tr}(M_n)=\sum_{i=1}^{2^n} \lambda_i(M_n)=0,\quad \text{Tr}(M_n^2)=\sum_{i=1}^{2^n} \lambda_i(M_n)^2=\|M_n\|_F^2=n2^n, $$ where $\lambda_1(M_n)\geq \lambda_2(M_n)\geq\ldots\geq \lambda_{2^n}(M_n)$. If for some signing $M_n$ one has $\lambda_{2^{n-1}}(M_n)>\sqrt{n}$, then $$ \sum_{i=1}^{2^{n-1}} \lambda_i(M_n)>\sqrt{n}2^{n-1},\quad \sum_{i=1}^{2^{n-1}} \lambda_i(M_n)^2>n2^{n-1}. $$ One can then see it is not possible to satisfy the trace equalities above: the negative eigenvalues must sum to strictly more than $\sqrt{n}2^{n-1}$ (in absolute value), and their squares must sum to strictly less than $n2^{n-1}$. Minimizing the sum of squares while keeping the sum constant happens when they are all equal, but in this case will make the sum of squares too large anyway. So for any signing, one can see via elementary means that $\lambda_{2^{n-1}}(M_n)\leq \sqrt{n}$ without knowing the magic signing in the paper, where equality holds iff the values are $\sqrt{n},\ldots,\sqrt{n},-\sqrt{n},\ldots,-\sqrt{n}$. That there actually exists such a signing attaining it is pretty amazing. The eigenvalues of the normal adjacency matrix are $-n, -n+2,\ldots,n-2,n$, where the $i$th eigenvalue has multiplicity ${n\choose i }$, so it's very interesting (to me, anyway) how the all-$+1$ signing maximizes $\lambda_1$, while this signing maximizes $\lambda_{2^{n-1}}$.

As far as would a random signing work, it's harder to say because I think most non-asymptotic bounds on eigenvalues focus on spectral norm. One expects random signings to smooth out the extreme usual eigenvalues, and indeed, using the noncommutative Khintchine inequality and/or recent tighter bounds like in here, a uniformly random signing has $\mathbb{E}[\|M_n\|_2]=\Theta(\sqrt{n})$. It's hard for me to imagine the middle eigenvalues would be on a similar polynomial order as the leading one in expectation (and asymptotic results like the semi-circular law for different matrix ensembles suggest similarly, I think), but maybe it's possible.