Question

This is probably well-known, but... Define the $n$-dimensional hypercube graph $H_n$ as having for vertices the integers between 0 and $2^n-1$, and edges between integers differing by a power of 2. The characteristic polynomial of $H_n$ is then $\prod_{k=0}^n(x-n+2k)^{\frac {n!}{k!(n-k)!}}$, i.e. $(x-3)(x-1)^3(x+1)^3(x+3)$ for a cube, $(x-4)(x-2)^4x^6(x+2)^4(x+4)$ for a tesseract, etc. Is there a graph-theoretic proof of this result?

Answer 1

View the vertices as elements of $\mathbb{Z}^n$. If $a\in\mathbb{Z}^n$, define a function $f_a$ on the vertices by $$ f_a(x) = (-1)^{a^Tx}. $$ This function is an eigenvectors and if $a$ has weight $w$, the eigenvalue is $n-2w$. I can make this look more combinatorial by viewing vertices (and $a$) as subsets of ${1,\ldots,n}$ and noting that $f_a(x)$ is determined by the parity of $a \cap x$ (abusing notation). Different choices of $a$ give linearly independent eigenvectors, so we get the multiplicities as well as the eigenvalues.

The actual difficulty with this question is in deciding what you mean by a "graph theoretical proof". From where I write, linear algebra is a standard and fundamental tool in graph theory.

Comment response: (too long for a comment box). OK. The $n$-cube is the Cartesian product of $n$ copies of $K_2$. The eigenvalues of the Cartesian product of two graphs $G$ and $H$ are the sums of the eigenvalues of $G$ with the eigenvalues of $H$. (The simplest way to see this is to note that the eigenvectors of the product are the Kronecker products of the eigenvectors of the factors.) Applying this $n$ times to $K_2$ gives the desired result.

There are formulas for the effect on the characteristic polynomial adding edges or vertices, but they are not all simple, and I cannot see how to use them to get the eigenvalues of the $n$-cube.

Answer 2

The hypercube graph is a Cayley graph. The Hamming graph $H(n,r)$ is the Cayley graph $Cay(\Bbb Z_r^n,S)$ where $S$ is the set of all elements of $\Bbb Z_r^n$ with exactly one nozero coordinate. In particular, the Hamming graph $H(n,2)$ is the familiar $n$-dimensional hypercube.

Since $\Bbb Z_r^n$ is abelian, $\sum_{s\in S}\chi(s)$ where $\chi$ is an irreducible representation of $\Bbb Z_r^n$ is an eigenvalue of $H(n,r)$. The eigenvectors of the adjacency matrix $A$ of $H(n,r)$ are the vectors ${u_x}$, $x\in\Bbb Z_r^n$, where its $y$th coordinate is $\omega_r^{-\sum_{i=1}^nx_iy_i}$, $y\in\Bbb Z_r^n$ and $\omega_r=e^{\frac{2\pi i}{r}}$. Let $\lambda_x$ be the corresponding eigenvalue of $u_x$. If we dnote by $\omega_H(x)$ the number of nonzero coordinates in $x$, we have $\lambda_x=(r-1)n-r\omega_H(x)$. Now it is enough to put $r=2$. For more details on the spectrum of Cayley graphs see "Spectra of Cayley graphs, L. Babai, Journal of Combinatorial Theory, Series B 27, (1979) 180-189.

Answer 3

It is interesting, worthwhile, and not very difficult to understand the situation for the Cartesian product of two or more arbitrary graphs. However here is a simplified answer which applies to this case: Let $G$ be a graph with $n$ vertices and $H$ the $2n$ vertex graph made by taking two copies of $G$ and joining corresponding vertices with an edge. If the (possibly not distinct) eigenvelaues of $G$ are $\theta_1,\theta_2,\cdots,\theta_n$ then the $2n$ eigenvalues of $H$ are $\theta_1\pm 1,\theta_2\pm 1,\cdots,\theta_n\pm 1.$ (Note that $H$ is just the Cartesian product $G \times K_2$.) Here is why: Let $A$ be the adjacency matrix of $G$ and $\mathbf{x}_1,\cdots,\mathbf{x}_n$ a basis of eigenvectors with $A\mathbf{x}_i=\theta_i\mathbf{x}_i.$ Then the $2n \times 2n$ adjacency matrix of $H$ is $\left( \begin{array}{cc} A & I \\ I & A \\ \end{array}\right)$ and it is easy to confirm that $\left( \begin{array}{c}\mathbf{x}_i \\ \mathbf{x}_i \\ \end{array}\right)$ and $\left( \begin{array}{c}\mathbf{x}_i \\ -\mathbf{x}_i \\ \end{array}\right)$ are eigenvectors for $\theta_i+1$ and $\theta_i-1.$