How to find the spectrum of the hypercube?

Question

I want to find the proof of the spectrum of the hypercube

Answer 1

This is just a data point:

Computing characteristic polynomials of their adjacency matrices, one finds the roots for the $d$-dimensional hypercube are $d$, $d-2$, $d-4$, $\dots$, $-d$, with multiplicities $\binom{d}{0}$, $\binom{d}{1}$, $\binom{d}{2}$, $\dots$, $\binom{d}{d}$.

Since this is extraordinarily regular, it suggests that one find a recursive formula. If $A_n$ is the adjacency matrix of hypercube on $2^{n-1}$ vertices, then $A_n=\begin{pmatrix}A_{n-1}&I_{2^{n-2}}\\I_{2^{n-2}}&A_{n-1}\end{pmatrix}$ so we have what to work with.

Answer 2

There is a proof here: http://www.cs.yale.edu/homes/spielman/eigs/lect12.ps

Or you can look up eigenvalues of Cartesian products and then follow Marion's hint.

Answer 3

This is not an independent answer but filling in what Mariano didn't bother to prove.

Start with Mariano's hint: $$A_{n+1}=\begin{pmatrix}A_{n}&I_{2^{n-1}}\\I_{2^{n-1}}&A_{n}\end{pmatrix}$$ Let $\chi_n(\lambda) = \det(\lambda I_{2^{n}} - A_{n+1})$ be the characteristic polynomial of the $n$-dim hypercube.

Notice for any $2m \times 2m$ matrix $X(A)$ of the form $\begin{pmatrix}A & I_m\\I_m & A\end{pmatrix}$. When $A$ is invertible, we have:

$$\begin{pmatrix}A & I_m\\I_m & A\end{pmatrix}\begin{pmatrix}I_m&-A^{-1}\\0&I_m\end{pmatrix} = \begin{pmatrix}A&0\\I_m&A-A^{-1}\end{pmatrix}$$ This implies $$\det X(A) = \det(A)\det(A - A^{-1}) = \det(A^2 - I_{2m}) = \det(A - I_{2m})\det(A + I_{2m})$$ Since both side of this identity are polynomials in entries of $A$, this identity is true even when $A$ is not invertible.

Apply this to $A_{n+1} - \lambda I_{2^n}$, we immediately obtain:

$$\chi_n(\lambda) = \chi_{n-1}(\lambda+1)\chi_{n-1}(\lambda-1)$$ So if the roots for the $(n-1)$-dim hypercube are n-1, n-3, ..., -(n-1) with multiplicities $$\binom{n-1}{0}, \binom{n-1}{1}, \binom{n-1}{2}, \ldots$$ then the roots for the $n$-dim hypercube are n = (n-1)+1, n-2 = (n-3)+1 = (n-1)-1, ... , -n with multiplicities $$1 = \binom{n}{0}, \binom{n}{1} = \binom{n-1}{0} + \binom{n-1}{1}, \binom{n}{2} = \binom{n-1}{1} + \binom{n-1}{2}, \ldots$$