# Math 202C: Lecture 9

We begin with a brief recap of the main result from Lecture 8. Let

$\chi_\sigma = \sum\limits_{\pi \in \mathrm{B}(k)} \chi_\sigma(\pi) \pi, \quad \sigma \in \mathrm{B}(k)$

be the characters of the rank $k$-hypercube group

$\mathrm{B}(k) = \langle (1\ 2), (3\ 4), \dots, (2k-1\ k) \rangle.$

Definition 1: The orthogonal idempotents in the group algebra $\mathbb{C}\mathrm{B}(k)$ are defined as the characters of $\mathrm{B}(k)$ normalized by the order of $\mathrm{B}(k)$:

$\tilde{\chi}_\sigma = \frac{1}{2^k} \chi_\sigma, \quad \sigma \in \mathrm{B}(k).$

The reason for the name is the following key property of these elements:

$\tilde{\chi}_\rho \tilde{\chi}_\sigma = \tilde{\chi}_\rho [\rho = \sigma], \quad \rho,\sigma \in \mathrm{B}(k).$

This is quite valuable, since expanding elements $a \in \mathbb{C}\mathrm{B}(k)$ in the group algebra relative to the basis of orthogonal idempotents essentially makes multiplication in the group algebra trivial, which translates into the “Fourier coefficients of a product are products of Fourier coefficients” fact that we saw last Lecture. Note also that the behavior of orthogonal idempotents in the group algebra is formally identical to the behavior of orthogonal projections in Hilbert space — you perhaps know from Math 202B that this is not a coincidence, and if you don’t know this don’t worry, because we will discuss it.

The main result for today is the following.

Theorem 1: The class of multiplication operators in $\mathrm{End}\mathbb{C}\mathrm{B}(k)$ coincides with the class of operators that are diagonal in the character basis of $\mathbb{C}\mathrm{B}(k).$

Proof: Let $b \in \mathbb{C}\mathrm{B}(k)$ be an element of the group algebra, and let $R_b \in \mathrm{End} \mathbb{C}\mathrm{B}(k)$ be the corresponding multiplication operator. Consider the character expansion of $b,$

$b = 2^{-k} \sum\limits_{\pi \in \mathrm{B}(k)} \langle \chi_\pi,b\rangle \chi_\pi .$

Now let $\chi_\sigma \in \mathbb{C}\mathrm{B}(k)$ be another character. We have

$R_b\chi_\sigma = 2^{-k}\sum\limits_{\pi \in \mathrm{B}(k)} \langle \chi_\pi,b\rangle \chi_\sigma\chi_\pi = 2^{-k}\langle \chi_\sigma,b\rangle 2^k \chi_\sigma = \langle \chi_\sigma,b\rangle\chi_\sigma.$

So, $\chi_\sigma$ is an eigenvector of $R_b,$ with eigenvalue the Fourier coefficient $\langle \chi_\sigma,b\rangle.$

Conversely, suppose that $R \in \mathrm{End}\mathbb{C}\mathrm{B}(k)$ acts diagonally in the character basis:

$R \chi_\pi = \lambda_\pi \chi_\pi, \quad \pi \in \mathrm{B}(k).$

Then the action of $R$ on an arbitrary $a \in \mathbb{C}\mathrm{B}(k)$ is

$Ma = M 2^{-k}\sum\limits_{\pi \in \mathrm{B}(k)} \langle \chi_\pi,a \rangle \chi_\pi = 2^{-k}\sum\limits_{\pi \in \mathrm{B}(k)} \langle \chi_\pi,a \rangle \lambda_\pi\chi_\pi = \left( 2^{-k}\sum\limits_{\pi \in \mathrm{B}(k)} \langle \chi_\pi,a \rangle \chi_\pi \right) \left(2^{-k}\sum\limits_{\sigma \in \mathrm{B}(k)} \lambda_\sigma \chi_\sigma \right),$

so that $M=R_b$ with

$b= 2^{-k}\sum\limits_{\sigma \in \mathrm{B}(k)} \lambda_\sigma \chi_\sigma.$

— Q.E.D.

With Theorem 1 in hand, we can immediately compute the the eigenvalues and eigenvectors of the Cayley graph of $\mathrm{B}(k).$ Indeed, the adjacency operator of the Cayley graph of $\mathrm{B}(k)$ is just the multiplication operators

$R_{\sum_{i=1}^k \tau_i},$

so by Theorem 1 we immediately have that

$R_{\sum_{i=1}^k \tau_i} \chi_\sigma = \langle \chi_\sigma,\sum\limits_{i=1}^k \tau_i \rangle \chi_\sigma, \quad \sigma \in \mathrm{B}(k).$

Now, we have that the resulting eigenvalue is

$\langle \chi_\sigma,\sum\limits_{i=1}^k \tau_i \rangle = \sum\limits_{i=1}^k \langle \chi_\sigma,\tau_i \rangle,$

and this is a sum we can explicitly evaluate, because we explicitly computed the characters of $\mathrm{B}(k)$ back in Lecture 7. In particular, what we know is that

$\langle \chi_\sigma,\tau_i \rangle =\chi_\sigma(\tau_i)$

is equal to $-1$ if $\tau_i$ is a factor of $\sigma,$ and is equal to $+1$ if $\tau_i$ is not a factor of $\sigma.$ Since we compute this scalar product for each and every generator $\tau_i$ of $\mathrm{B}(k),$ the sum has $|\sigma|$ terms equal to $-1,$ and $k - |\sigma|$ terms equal to $+1,$ where $|\sigma|$ is the word norm of $\sigma,$ or equivalently its distance to the identity permutation in the Cayley graph. So we get

$\sum\limits_{i=1}^k \langle \chi_\sigma,\tau_i \rangle = k-2|\sigma|$

as our explicit eigenvalue of the character $\chi_\sigma$ under the action of the adjacency operator. Moreover, the number of elements $\sigma \in \mathrm{B}(k)$ such that $|\sigma|=j$ for a given $0 \leq j \leq k$ is simply ${k \choose j},$ since this just amounts to choosing $j$ of the generators $\tau_1,\dots,\tau_k$ of $\mathrm{B}(k).$ So we can summarize our results as follows.

Theorem 2: The eigenvalues of Cayley graph of $\mathrm{B}(k)$ are the numbers

$k-2j, \quad j=0,\dots,k,$

and the dimension of the eigenspace corresponding to $k-2j$ is ${k \choose j}.$

Since all eigenvalues of the Cayley graph of $\mathrm{B}(k)$ are given explicitly by Theorem 2, we are in a position to explicitly enumerate walks on this graph, using the spectral approach to counting walks discussed previously.

Problem 9.1: Show that the number $W^r(\rho,\sigma)$ of $r$-step walks on $\mathrm{B}(k)$ from $\rho$ to $\sigma$ is

$W^r(\rho,\sigma) = \frac{1}{2^k} \sum\limits_{i=0}^k \sum\limits_{j=0}^{|\rho\sigma|} (-1)^j {|\rho\sigma| \choose j} {k-|\rho\sigma| \choose i-j} (k-2i)^r.$

This material, and problem 9.1, have applications in coding theory which you might find interesting to look into.