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
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.