Walsh Eigenvectors and Hypercube Multiplicities

Characters as Hypercube Eigenvectors

The hypercube \(Q_d\) has \(2^d\) vertices, one for each binary string of length \(d\). Its adjacency operation changes one coordinate at a time. The tensor-product construction of hypercube eigenvalues gives the values \(d-2k\); here we construct corresponding eigenvectors directly and show why their multiplicities are binomial coefficients. The construction also produces a full basis, so it accounts for every eigenvalue.

Write a vertex as \(x=(x_1,\ldots,x_d)\), with each \(x_i\in\{0,1\}\). For a coordinate \(i\), let \(x^{(i)}\) denote the string obtained by changing \(x_i\) to \(1-x_i\) and leaving all other coordinates unchanged. Thus \(x^{(i)}\) is the neighbor of \(x\) reached by flipping coordinate \(i\). The adjacency matrix \(\mathbf A(Q_d)\), acting on a function \(f\) on the vertices, satisfies \((\mathbf A(Q_d)f)(x)=\sum_{i=1}^d f(x^{(i)})\).

A character takes only the values \(1\) and \(-1\). Flipping a coordinate outside \(S\) leaves its value unchanged; flipping a coordinate in \(S\) changes its sign. The adjacency eigenvalue follows by summing these contributions.

Why the Eigenvalue Is \(d-2|S|\)

Fix a vertex \(x\) and a subset \(S\). Among the \(d\) neighbors \(x^{(i)}\), exactly \(|S|\) result from flipping a coordinate in \(S\). Their character values are \(-\chi_S(x)\). The other \(d-|S|\) neighbors have character value \(\chi_S(x)\). Therefore \[ (\mathbf A(Q_d)\chi_S)(x) =(d-|S|)\chi_S(x)-|S|\chi_S(x) =(d-2|S|)\chi_S(x). \] This holds at every vertex, which proves the eigenvector equation. The number of minus signs matters: each coordinate in \(S\) replaces a contribution of \(+1\) by \(-1\), a change of \(2\).

To establish the multiplicities, we need to know that the characters are independent. Their stronger property of orthogonality makes this transparent. For real-valued functions \(f,g\) on the vertices, use the inner product \(\langle f,g\rangle=\sum_{x\in\{0,1\}^d} f(x)g(x)\).

Proof. At each string \(x\), the product \(\chi_S(x)\chi_T(x)\) equals \(\chi_{S\triangle T}(x)\), where \(S\triangle T\) consists of coordinates belonging to exactly one of \(S,T\). If \(S=T\), this product is \(1\) at every one of the \(2^d\) strings, so its sum is \(2^d\). If \(S\ne T\), choose a coordinate \(j\in S\triangle T\). Pair each string \(x\) with the string \(x^{(j)}\). This partitions all strings into pairs: flipping \(j\) twice returns to \(x\), and no string equals its flip. Within each pair, \(\chi_{S\triangle T}\) changes sign, so the two terms sum to zero. The whole inner product is therefore zero. When \(d=0\), there is only the empty subset and one empty string; only the equal-subset case applies. \(\square\)

Proof of the Theorem. The eigenvector equation was established by counting the neighbors whose character values change sign. The lemma shows that all \(2^d\) characters are nonzero and mutually orthogonal, so they are linearly independent. The space of functions on the \(2^d\) vertices has dimension \(2^d\), hence these \(2^d\) independent vectors form a basis.

There are \(\binom{d}{k}\) subsets of size \(k\), and each gives eigenvalue \(d-2k\). If \(k\ne\ell\), then \(d-2k\ne d-2\ell\), so no other subset size gives the same eigenvalue. Since the characters form a basis, every vector is a linear combination of these eigenvectors, and no further eigenvalues occur. In this eigenvector basis the adjacency matrix is diagonal, with one diagonal entry for each character. Thus the algebraic and eigenspace multiplicities of \(d-2k\) both equal \(\binom{d}{k}\). For \(d=0\), the graph has one vertex and no edges; its single character is constant and has eigenvalue \(0\), in agreement with \(\binom{0}{0}=1\). \(\square\)

Worked Examples

Common Pitfall and Why Multiplicity Matters

A frequent error is to count each coordinate in \(S\) as contributing \(-1\) without accounting for the contribution it replaces. For example, on \(Q_5\) with \(|S|=2\), this incorrect calculation would give \(5-2=3\). But there are three unchanged contributions of \(+1\) and two changed contributions of \(-1\), so the correct sum is \(3-2=1\), or \(5-2(2)=1\). The sign change reduces the total by \(2\) for each selected coordinate.

Multiplicity is not simply the number of ways to write the same eigenvector: the lemma proves that the characters are independent. It is the number of subsets of the relevant size, because every such subset supplies one independent eigenvector and different sizes supply different eigenvalues. The complete basis argument is also essential: listing eigenvectors proves that their eigenvalues occur, while showing there are \(2^d\) independent vectors proves that nothing is missing.

For \(Q_d\), the entire adjacency spectrum is therefore symmetric about zero: the eigenvalue for subset size \(k\) is \(d-2k\), while size \(d-k\) gives \(d-2(d-k)=-(d-2k)\). The corresponding multiplicities agree because \(\binom{d}{k}=\binom{d}{d-k}\). This follows directly from the character construction and subset counting.