The matrix corresponds to the 2-dimensional hypercube using a normal binary ordering (indexing included only to show nodes, this is a $2^2 \times 2^2$ matrix)

$A_2= \begin{pmatrix} & 00 & 01 & 10 & 11 \\ 00 & 0 & 1 & 1 & 0 \\ 01 & 1 & 0 & 0 & 1 \\ 10 & 1 & 0 & 0 & 1 \\ 11 & 0 & 1 & 1 & 0 \end{pmatrix}$

We can use this matrix inductively. Adding one extra symbol, hence a $2^3 \times 2^3$ matrix will look like

$A_3 = \begin{pmatrix} A_2 & Y \\ Y & A_2 \end{pmatrix}$

$Y$ will only have entries which differ by one from the entries in $A_2$. Clearly, this can only be the identity matrix! We note that we have identity matrices in these positions also in $A_2$.

More general, for a $k$-dimensional hypercube, we have that

$A_k = \begin{pmatrix} A_{k-1} & I_{k-1} \\ I_{k-1} & A_{k-1} \end{pmatrix}, \quad k > 1,\ A_1 = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}.$

Why is this the case? We can take two hypercubes of two dimensions and put together to obtain a three dimensional hypercube (well, a cube). Each vertex in the first hypercube is connected with another vertex (in the corresponding position) in the second hypercube. Of course this is the case for any dimension.

The recursive nature and commutativity of the submatrices allows us to give a recursive formula for the characteristic polynomial.

$\det (A_{k}-\lambda I_k) = \det((A_{k-1}-\lambda I_{k-1})^2 - I_{k-1})$

$= \det((A_{k-1}-\lambda I_{k-1}) - I_{k-1})\det((A_{k-1}-\lambda I_{k-1}) + I_{k-1})$

$= \det(A_{k-1}-(\lambda+1) I_{k-1})\det(A_{k-1}-(\lambda-1) I_{k-1})$

We use a simple combinatorial argument. The $\lambda$-value can take on step up och one step down in each induction step which gives us that the eigenvalues for $A_k$ will be $\{ k-2j : |k-2j| \leq k, j \in \mathbf{Z}\}$ and their corresponding multiplicities ${k \choose j}$.

## 7 thoughts on “Hypercube adjacency matrix eigenvalues”

1. interesting article!! I saw similar thoughtsinagost version of forbes. Probably the author red it, too.

1. Actually, this is my solution to a homework question for a course I took. I decided to publish it, due to that the Wikipedia page [1] was quite inaccurate on this particular point.

1. Pedro says:

Hi,
Can you please explain the “simple combinatorial argument” at the last step that you used for conculding that the eigenvalues are k-2j with multiplicity of k choose j?

Thanks!

2. Hello Pedro,

Each eigenvalue x is replaced by x-1 and x+1, this is given above. Trying the first few steps gives:

x — x-1,x+1 — x-2,x,x,x-2
— x-3,x-1,x-1,x-1,x+1,x+1,x+1,x+3 — …

This is exactly the set given by k-2j with the multiplicities k choose j. Try another step if you are not convinced.

An easy way to look at k-2j is to assume that x is even or odd. Lets assume even. When we replace x with x-1 and x+1 all new values are odd. Then next time, all values will be even, and so on.

Hope this helps!

All the best,
Carl

2. Roni says:

Hi Carl,
This is a beautiful prrof, I really liket it. I have a problem with the ‘multiplicities k choose j’ I just can’t proove it in a normal way. I can understand the intution behind it, but I can’t think of a formal proof.
do you have any?

Thanks!!

1. Given the recursion of the eigenvalues, you know that any ‘target’ eigenvalue m is the value of k recursion steps. Since the recursion takes one step up or one step down (+1,-1), how many paths to the eigenvalue m are there? Assume that m = k – 2*j for some j. This means that you need exactly j steps down (-1) out of k steps. Since you can order them in several ways, you get k choose j.

All the best,
Carl

1. Roni says:

Cool! Thanks!