IMC 2017 · Day 2 · P8

For each $n \in \mathbb{N}$, matrix $A_n$ is symmetric $2^n \times 2^n$ matrix with elements from the set $\{0, 1\}$, so that all elements on the main diagonal are equal to zero. We can write $$\tag{1} A_n = I_{2^{n-1}} \otimes A_1 + A_{n-1} \otimes I_2,$$ where $\otimes$ is binary operation over the space of matrices, defined for arbitrary $B \in \mathbb{R}^{n \times p}$ and $C \in \mathbb{R}^{m \times s}$ as $$B \otimes C := \begin{pmatrix} b_{11} C & b_{12} C & \dots & b_{1p} C \\ b_{21} C & b_{22} C & \dots & b_{2p} C \\ \vdots \\ b_{n1} C & b_{12} C & \dots & b_{np} C$$

\end{pmatrix}_{nm \times ps}. Lemma 1. If $B \in \mathbb{R}^{n \times n}$ has eigenvalues $\lambda_i$, $i = 1, \dots, n$ and $C \in \mathbb{R}^{m \times m}$ has eigenvalues $\mu_j$, $j = 1, \dots, m$, then $B \otimes C$ has eigenvalues $\lambda_i \mu_j$, $i = 1, \dots, n$, $j = 1, \dots, m$. If $B$ and $C$ are diagonalizable, then $A \otimes B$ has eigenvectors $y_i \otimes z_j$, with $(\lambda_i, y_i)$ and $(\mu_j, z_j)$ being eigenpairs of $B$ and $C$, respectively.

Proof 1. Let $(\lambda, y)$ be an eigenpair of $B$ and $(\mu, z)$ an eigenpar of $C$. Then $$(B \otimes C)(y \otimes z) = B y \otimes C z = \lambda y \otimes \mu z = \lambda \mu (y \otimes z).$$

If we take $(\lambda, y)$ to be an eigenpair of $A_1$ and $(\mu, z)$ to be an eigenpair of $A_{n-1}$, then from (1) and Lemma 1 we get $$\begin{align*} A_n (z \otimes y) &= (I_{2^{n-1}} \otimes A_1 + A_{n-1} \otimes I_2)(z \otimes y) \\ &= (I_{2^{n-1}} \otimes A_1)(z \otimes y) + (A_{n-1} \otimes I_2)(z \otimes y) \\ &= (\lambda + \mu)(z \otimes y). \end{align*}$$ So the entire spectrum of $A_n$ can be obtained from eigenvalues of $A_{n-1}$ and $A_1$: just sum up each eigenvalue of $A_{n-1}$ with each eigenvalue of $A_1$. Since the spectrum of $A_1$ is $\sigma(A_1) = \{-1, 1\}$, we get $$\begin{gather*} \sigma(A_2) = \{-1+(-1), -1+1, 1+(-1), 1+1\} = \{-2, 0^{(2)}, 2\} \\ \sigma(A_3) = \{-1+(-2), -1+0, -1+0, -1+2, 1+(-2), 1+0, 1+0, 1+2\} = \{-3, (-1)^{(3)}, 1^{(3)}, 3\} \\ \begin{aligned} \sigma(A_4) &= \{-1+(-3), -1+(-1^{(3)}), -1+1^{(3)}, -1+3, 1+(-3), 1+(-1^{(3)}), 1+1^{(3)}, 1+3\} \\ &= \{-4, (-2)^{(4)}, 0^{(3)}, 2^{(4)}, 4\}.$$

\end{aligned} \end{gather*} Inductively, $A_n$ has $n + 1$ distinct integer eigenvalues $-n, -n+2, -n+4, \dots, n-4, n-2, n$ with multiplicities $\binom{n}{0}, \binom{n}{1}, \binom{n}{2}, \dots, \binom{n}{n}$, respectively.