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

be the characters of the rank -hypercube group

**Definition 1:** The **orthogonal idempotents** in the group algebra are defined as the characters of normalized by the order of :

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

This is quite valuable, since expanding elements 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 coincides with the class of operators that are diagonal in the character basis of

*Proof:* Let be an element of the group algebra, and let be the corresponding multiplication operator. Consider the character expansion of

Now let be another character. We have

So, is an eigenvector of with eigenvalue the Fourier coefficient

Conversely, suppose that acts diagonally in the character basis:

Then the action of on an arbitrary is

so that with

— Q.E.D.

With Theorem 1 in hand, we can immediately compute the the eigenvalues and eigenvectors of the Cayley graph of Indeed, the adjacency operator of the Cayley graph of is just the multiplication operators

so by Theorem 1 we immediately have that

Now, we have that the resulting eigenvalue is

and this is a sum we can explicitly evaluate, because we explicitly computed the characters of back in Lecture 7. In particular, what we know is that

is equal to if is a factor of and is equal to if is not a factor of Since we compute this scalar product for each and every generator of the sum has terms equal to and terms equal to where is the word norm of or equivalently its distance to the identity permutation in the Cayley graph. So we get

as our explicit eigenvalue of the character under the action of the adjacency operator. Moreover, the *number* of elements such that for a given is simply since this just amounts to choosing of the generators of So we can summarize our results as follows.

**Theorem 2: **The eigenvalues of Cayley graph of are the numbers

and the dimension of the eigenspace corresponding to is

Since all eigenvalues of the Cayley graph of 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 of -step walks on from to is

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

## 1 Comment