Hypercube Eigenvalues from Tensor Products

From a Product Graph to a Sum of Matrices

The \(d\)-dimensional hypercube has \(2^d\) vertices, so its adjacency matrix grows quickly even for moderate \(d\). Its recursive structure gives a more efficient route to its spectrum: build the graph one coordinate at a time, and express its adjacency matrix using Kronecker products. The resulting matrix is a Kronecker sum. The eigenvalues of that sum come from adding eigenvalues of the one-coordinate factors.

All graphs in this tutorial are finite and simple. For an integer \(d\ge 0\), let \(Q_d\) have as vertices the binary strings of length \(d\). Two strings are adjacent exactly when they differ in one coordinate. For \(d=0\), there is one vertex, the empty string, and no edges. For \(d\ge 1\), this condition specifies the edge set completely.

Write \(A(G)\) for the adjacency matrix of a graph \(G\), and write \(I_n\) for the \(n\times n\) identity matrix. The adjacency matrix of \(K_2\), in vertex order \(0,1\), is \(B=\begin{pmatrix}0&1\\1&0\end{pmatrix}\). To describe the matrix of \(Q_d\), order its vertices by the pair \((x,b)\), with \(x\) a binary string of length \(d-1\) and \(b\in\{0,1\}\).

In \(Q_d\), an edge either changes one of the first \(d-1\) coordinates and leaves \(b\) fixed, or leaves \(x\) fixed and changes \(b\). These two types of edges are represented, respectively, by \(A(Q_{d-1})\otimes I_2\) and \(I_{2^{d-1}}\otimes B\). Therefore

Why Eigenvalues Add

The key calculation is the action of a Kronecker product on a tensor product of vectors. If \(Mx=\lambda x\) and \(Ny=\mu y\), then

This calculation produces eigenvectors and their eigenvalues. To conclude that it gives the whole spectrum, the vectors being used must form a basis. The following result states the required fact and justifies that step.

Proof. For each \(i,j\), the displayed action calculation gives \((M\otimes I_s+I_r\otimes N)(x_i\otimes y_j)=(\lambda_i+\mu_j)(x_i\otimes y_j)\). It remains to show that these \(rs\) vectors form a basis. Let \(X\) be the invertible matrix with columns \(x_1,\ldots,x_r\), and let \(Y\) be the invertible matrix with columns \(y_1,\ldots,y_s\). The columns of \(X\otimes Y\), in the product ordering, are exactly the vectors \(x_i\otimes y_j\). The identity \((X\otimes Y)(X^{-1}\otimes Y^{-1})=I_r\otimes I_s\) follows by multiplying blocks, or from the definition of the Kronecker product. Since \(I_r\otimes I_s\) is the identity matrix of order \(rs\), \(X\otimes Y\) is invertible. Its columns form a basis, as required. \(\square\)

The Hypercube Eigenvalue Values

The one-coordinate graph \(K_2\) has two eigenvectors: \((1,1)^{\mathsf T}\), with eigenvalue \(1\), and \((1,-1)^{\mathsf T}\), with eigenvalue \(-1\). They form a basis of \(\mathbb{R}^2\), since the matrix with these columns has determinant \(-2\ne0\).

Proof. For \(d=0\), \(Q_0\) has adjacency matrix \([0]\), whose only eigenvalue is \(0=0-2\cdot0\). Now take \(d\ge1\). Applying the proposition repeatedly to the recurrence for \(A(Q_d)\) shows that tensor products of \(d\) eigenvectors of \(B\) form an eigenvector basis of \(A(Q_d)\). Each factor contributes either \(1\) or \(-1\) to the eigenvalue sum. If exactly \(k\) of the \(d\) factors contribute \(-1\), the sum is \((d-k)-k=d-2k\). Every integer \(k\) from \(0\) through \(d\) can occur, by choosing that many factors with eigenvalue \(-1\). Conversely, every tensor in the basis has some such number \(k\) of those factors, so no other eigenvalue can occur. The basis accounts for the entire matrix, and the asserted list of distinct values follows. \(\square\)

This result identifies the eigenvalue values; it does not give a separate formula for how often each value occurs. The tensor basis also gives a way to count those occurrences, but the focus here is the Kronecker-sum derivation of the values.

Worked Calculations

Common Pitfall: Adding or Multiplying?

A Kronecker sum adds eigenvalues; a Kronecker product multiplies them. For example, when building \(Q_2\), the two factor eigenvalues \(1\) and \(-1\) combine by addition. They produce \(1+1=2\), \(1+(-1)=0\), \((-1)+1=0\), and \((-1)+(-1)=-2\). A common wrong calculation is to multiply instead, obtaining \(1\cdot1=1\) and products equal to \(-1\). Those are not the eigenvalues of \(Q_2\): the recurrence contains a sum of matrices, and the action on a tensor eigenvector gives a sum of scalars.

The advantage of this method is that the dimension changes while the one-coordinate matrix stays \(2\times2\). The theorem follows from the graph’s Cartesian-product structure and the eigenvector-basis calculation, rather than a determinant expansion whose size doubles at each step. Keep the distinction between the set of distinct eigenvalue values and their multiplicities in mind: listing the values does not itself state how many times each value appears.