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

<p>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 <span class="math-container">$B_0 \in \{(0), (\pm 1)\}$</span> (a <span class="math-container">$1 \times 1$</span> matrix), and then a single recursive formula </p>

<p><span class="math-container">$$
B_n = \left(\begin{array}{cc}
b_{11} &amp; b_{12} \\
b_{21} &amp; b_{22} \end{array}\right)
$$</span></p>

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

<p>If one wants such a recursion to have the property that <span class="math-container">$B_n^2$</span> is proportional to <span class="math-container">$I_{2^{n}}$</span>, then one quickly finds that either <span class="math-container">$b_{11} + b_{22} = 0$</span>, or <span class="math-container">$b_{12} = b_{21}=0$</span>. In the latter case, the recursion only yield diagonal matrices, which is maybe not so interesting. So the interesting cases are those in which <span class="math-container">$b_{11} = -b_{22}$</span> (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.</p>

<p>As a last small comment, this kind of recursion automatically yields that the block entries of <span class="math-container">$B_n$</span> commute, which was the other "niceness" condition in Jason's answer.</p>

<p>I haven't yet done a systematic investigation, but given the above setup, one could investigate the finitely many possibilities (3 choices for <span class="math-container">$B_0$</span>, and technically <span class="math-container">$5^4$</span> choices for the recursion, but this can be cut down using symmetries and also from the restrictions that <span class="math-container">$B_n^2$</span> 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...</p>

CC BY-SA 4.0
2019-07-10T18:30:40.807Z
*And if not, maybe there are some other interesting ones lurking out there...* sounds quite interesting :)
Clement C.
CC BY-SA 4.0
2019-07-08T13:25:02.107Z
2019-07-08T13:25:02.107Z
Joshua Grochow
<p>Here's just a couple of observations I couldn't fit in a comment:</p>

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

<p>1) In general, the spectrum of block matrices can be very complicated and not obviously related to the spectra of the individual blocks, as <a href="https://en.wikipedia.org/wiki/Determinant#Block_matrices" rel="nofollow noreferrer">the characteristic polynomial will look awful</a>. But for a symmetric block matrix <span class="math-container">$M=\begin{pmatrix} A &amp; B\\ B^T &amp; C\end{pmatrix}$</span> that might arise via a recursive construction like the <span class="math-container">$A_n$</span> and <span class="math-container">$H_n$</span> above, where each matrix is square, one of the only simplifications occurs when <span class="math-container">$B^T$</span> and <span class="math-container">$C$</span> commute, in which case one has <span class="math-container">$\det(M)=\det(AC-BB^T)$</span>. Then the characteristic polynomial of <span class="math-container">$M$</span> will be <span class="math-container">$$\det((\lambda I-A)(\lambda I-C)-BB^T)=\det(\lambda^2I-\lambda (A+C)+AC-BB^T).$$</span>
For this to lead to nice recursive formulas for the eigenvalues, one basically needs <span class="math-container">$C=-A$</span> to kill the linear <span class="math-container">$\lambda$</span> term. If further <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are symmetric and commute, we get
<span class="math-container">$$
\det(\lambda I-M)=\det(\lambda^2 I-(A^2+B^2)),
$$</span>
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 <span class="math-container">$-A$</span> and hope that lower left and upper right blocks are symmetric and commute with <span class="math-container">$A$</span>, which is the case for the <span class="math-container">$A_n$</span> (with <span class="math-container">$B=I$</span>) and <span class="math-container">$H_n$</span> matrices (with <span class="math-container">$B=H_{n-1}=A$</span>).</p>

<p>2) On the random sign question: the signing of the adjacency matrix given in the paper is optimal in the sense of maximizing <span class="math-container">$\lambda_{2^{n-1}}$</span>, which is needed for the lower bound via Cauchy interlacing, and can be seen from elementary means. For an arbitrary signing <span class="math-container">$M_n$</span> of the adjacency matrix of the <span class="math-container">$n$</span>-dimensional hypercube, one immediately gets
<span class="math-container">$$
\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,
$$</span>
where <span class="math-container">$\lambda_1(M_n)\geq \lambda_2(M_n)\geq\ldots\geq \lambda_{2^n}(M_n)$</span>. If for some signing <span class="math-container">$M_n$</span> one has <span class="math-container">$\lambda_{2^{n-1}}(M_n)&gt;\sqrt{n}$</span>, then 
<span class="math-container">$$
\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}.
$$</span>
One can then see it is not possible to satisfy the trace equalities above: the negative eigenvalues must sum to strictly more than <span class="math-container">$\sqrt{n}2^{n-1}$</span> (in absolute value), and their squares must sum to strictly less than <span class="math-container">$n2^{n-1}$</span>. 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 <span class="math-container">$\lambda_{2^{n-1}}(M_n)\leq \sqrt{n}$</span> without knowing the magic signing in the paper, where equality holds iff the values are <span class="math-container">$\sqrt{n},\ldots,\sqrt{n},-\sqrt{n},\ldots,-\sqrt{n}$</span>. That there actually exists such a signing attaining it is pretty amazing. The eigenvalues of the normal adjacency matrix are <span class="math-container">$-n, -n+2,\ldots,n-2,n$</span>, where the <span class="math-container">$i$</span>th eigenvalue has multiplicity <span class="math-container">${n\choose i }$</span>, so it's very interesting (to me, anyway) how the all-<span class="math-container">$+1$</span> signing maximizes <span class="math-container">$\lambda_1$</span>, while this signing maximizes <span class="math-container">$\lambda_{2^{n-1}}$</span>.</p>

<p>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 <a href="https://arxiv.org/abs/1408.6185" rel="nofollow noreferrer">here</a>, a uniformly random signing has <span class="math-container">$\mathbb{E}[\|M_n\|_2]=\Theta(\sqrt{n})$</span>. 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.</p>

CC BY-SA 4.0
2019-07-08T04:41:30.890Z
2019-07-09T04:23:07.170Z
2019-07-09T04:23:07.170Z
Jason Gaitonde
<p>The recent and incredibly slick <a href="https://arxiv.org/abs/1907.00847" rel="noreferrer">proof of the sensitivity conjecture</a> relies on the explicit* construction of a matrix <span class="math-container">$A_n\in\{-1,0,1\}^{2^n\times 2^n}$</span>, defined recursively as follows:
<span class="math-container">$$A_1 = \begin{pmatrix} 0&amp;1\\1&amp;0\end{pmatrix}$$</span>
and, for <span class="math-container">$n\geq 2$</span>, 
<span class="math-container">$$A_{n} = \begin{pmatrix} A_{n-1}&amp;I_{n-1}\\I_{n-1}&amp;-A_{n-1}\end{pmatrix}$$</span>
In particular, it is easy to see that <span class="math-container">$A_n^2 = n I_n$</span> for all <span class="math-container">$n\geq 1$</span>.</p>

<p>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 <span class="math-container">$H_n^2 \propto I_n$</span> and has 'similar' spectrum:
<span class="math-container">$$H_1 = \begin{pmatrix} 1&amp;1\\1&amp;-1\end{pmatrix}$$</span>
and, for <span class="math-container">$n\geq 2$</span>, 
<span class="math-container">$$H_{n} = \begin{pmatrix} H_{n-1}&amp;H_{n-1}\\H_{n-1}&amp;-H_{n-1}\end{pmatrix}$$</span></p>

<blockquote>
  <p>Is there any formal connection, possibly useful, between the two, except that "they look vaguely similar"?</p>
</blockquote>

<p>For instance, <span class="math-container">$A_n$</span> seen as the signed adjacency matrix of the hypercube <span class="math-container">$\{0,1\}^n$</span> has a nice interpretation (the sign of an edge <span class="math-container">$(x,b,x')\in\{0,1\}^n$</span> is the parity of the prefix <span class="math-container">$x$</span>). Is there an analogue for <span class="math-container">$H_n$</span>? <em>(this may be obvious?)</em></p>

<p><em><span class="math-container">$^*$</span> I am also wondering if a non-explicit construction, e.g., a uniformly random <span class="math-container">$\pm1$</span> matrix, would have the desired spectral properties, but that'd probably have to wait for another question.</em></p>

<boolean-functions><matrices><boolean-matrix>
Question about two matrices: Hadamard v. "the magical one" in the proof of the sensitivity conjecture
Clement C.
# Question about two matrices: Hadamard v. "the magical one" in the proof of the sensitivity conjecture

(Asked by: username_0 on 2019-07-03)

The recent and incredibly slick [proof of the sensitivity conjecture](https://arxiv.org/abs/1907.00847) 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.*

**Tags:** boolean-functions, matrices, boolean-matrix


---

## 2 answers

### Answer by username_1 on 2019-07-08. Score: 9

An observation too long for a comment (and which also fits well with username_2'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...

> **Comments:**
> **username_0**: *And if not, maybe there are some other interesting ones lurking out there...* sounds quite interesting :)  

---

### Answer by username_2 on 2019-07-08. Score: 9

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](https://en.wikipedia.org/wiki/Determinant#Block_matrices). 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](https://arxiv.org/abs/1408.6185), 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.


---

