Are all n-dimensional hypercube graphs circulant and if so what is their circulant adjacency matrix?

Question

Usually the adjacency matrix representation of the n-dimensional hypercube, $Q_n$, is given as $$Q_n=\begin{bmatrix}Q_{n-1} & I \\ I & Q_{n-1} \end{bmatrix}$$ where $Q_1$ is the adjacency matrix of $K_2$. Since the $1$-dimensional hypercube is $K_2$ and the $2$-dimensional hypercube is $C_4$ which are also circulant graphs I was wondering if all $n$-dimensional hypercubes are circulant graphs and if so what is the circulant matrix representation of their adjacency matrix.

Answer 1

The $d$-cube is not a circulant if $d\ge3$. In fact something stronger is true.

Suppose $G$ is an abelian group acting regularly as a group of automorphisms of the $d$-cube $Q_d$. Then $Q_d$is a Cayley graph for $G$, with connection set $C$ (say).

Define two elements $g$ and $h$ of $G$ to be equivalent if they generate the same subgroup of $G$. It is known that if the eigenvalues of a Cayley graph for an abelian group are integers, $C$ must be a union of equivalence classes. (Bridges and Mena "Rational G-matrices with rational eigenvalues", JCT A, 32 (1982), 264-280.)

Assume now that the exponent of $G$ is $2^m$, where $m\ge3$. Since the $d$-cube is connected, $C$ must be a generating set for $G$ and hence it contains an element of order $2^m$, and hence $C$ contains all $2^{m-1}$ generators of some subgroup of order $2^m$. It follows that the $d$-cube must have an induced subgraph isomorphic to $K_{2^{m-1},2^{m-1}}$ and, in particular contains a copy of $K_{3,3}$.

To complete the argument we show by induction on $d$ that $Q_d$ does not contains an induced subgraph isomorphic to $K_{3,3}$. The key is that we cannot disconnect $K_{3,3}$ by deleting the edges of a perfect matching (exercise: note that all perfect matchings are equivalent under the automorhism group). But the $d$-cube consists of two copies of the $Q_{d-1}$-cube joined by a perfect matching, and so any copy of $K_{3,3}$ must lie in one of the copies of $Q_{d-1}$, which leads to a contradiction.

So the $d$-cube cannot be a Cayley group for an abelian group of exponent greater than four. Note that if $d=2e$, then it is a Cayley graph for $\mathbb{Z}_4^e$.