eigenvectors for hypercube graphs

Question

Consider a set of size $n$ like $\Omega =\lbrace 1,2,\cdots ,n\rbrace $, where $n$ is a positive integer. For every $x\in P(\Omega )$, define the function $f^x:P(\Omega )\rightarrow \lbrace \pm 1 \rbrace$ as follows: $$f^x (z) = (-1)^{\vert z-x \vert}$$ where $z-x$ is the difference of $z$ and $x$ in set theory. Show that each $f^x$ is an eigenvector of the adjacency matrix of the hypercube graph $H_n$, with the eigenvalue $-n + 2\vert x\vert$.

Answer 1

Basic definition chasing suffices. Denote by $A$ the adjacent matrix of $H$ such that $$A(y,z) = \begin{cases}1 & \text{if }|y \Delta z| = 1,\\ 0&\text{otherwise},\end{cases}$$ where $y, z\in\mathcal{P}([n])$ and $\Delta$ is the symmetric difference of two sets.

Observe $$(Af^x)(y) = \sum_z A(y,z)f^x(z) = \sum_{z:|y\Delta z|=1}(-1)^{|z\setminus x|}.$$ Note that for all $z$ that $|y\Delta z| = 1$, there exists a unique $a\in[n]$ such that $z = \{a\}\Delta y$. Therefore the above is equal to $$\sum_{a\in[n]}(-1)^{\left|(\{a\}\Delta y)\setminus x\right|} = f^x(y)\sum_{a\in[n]}(-1)^{\left|(\{a\}\Delta y)\setminus x\right| - |y\setminus x|}.$$ Note that $$\left|(\{a\}\Delta y)\setminus x\right| - |y\setminus x| = \begin{cases}0 & \text{if }a\in x, \\ \pm 1 & \text{if }a\notin x.\end{cases}$$ Therefore $$(Af^x)(y)=(|x|-(n-|x|))f^x(y) = (2|x|-n)f^x(y).$$