Question about two matrices: Hadamard v. "the magical one" in the proof of the sensitivity conjecture
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 &amp; B\\ B^T &amp; 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)&gt;\sqrt{n}$, then 
$$
\sum_{i=1}^{2^{n-1}} \lambda_i(M_n)&gt;\sqrt{n}2^{n-1},\quad \sum_{i=1}^{2^{n-1}} \lambda_i(M_n)^2&gt;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.