Hypercube adjacency matrix eigenvalues

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}.

Advertisements

7 thoughts on “Hypercube adjacency matrix eigenvalues

      1. 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

  1. 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s