In which we look at the representation theory of Abelian groups and at the discrete Fourier transform, we completely understand the eigenvalues and eigenvectors of the Cayley graph of an Abelian group, and we apply this powerful theory to prove that the cycle is a connected graph.
When we talked about group representations, we saw how to map each element of a group into a matrix in such a way that group addition becomes matrix multiplication.
In general, if is a finite group, then an n-dimensional representation of is a map
such that is a group homomorphism between and the group of matrices . That is, we have that is an invertible matrix for every , , and .
(Scott will be delighted to know that the theory need not stop at finite matrices, and one may also look at representations mapping group elements into invertible linear transformations over an infinite-dimensional Hilbert space. To study finite groups, however, finite-dimensional representations are good enough.)
Note that need not be injective, and so, for every group, we can always define the 1-dimensional representation for every . Perhaps unsurprisingly, this is usually called the trivial representation. The precise statement of a theorem of Frobenius that we mentioned earlier is that every non-trivial representation of has dimension at least .
In an Abelian group, however, there are plenty of 1-dimensional representations, and, in fact, all the information about the group is “encoded” in the set of its 1-dimensional representations. We will call a 1-dimensional representation a character of the group. (This equivalence holds only for finite groups, otherwise we need an extra condition.) Hence a character of a group is a mapping
such that for every , , and . In a finite group , we always have the property that if we add an element to itself times we get 0; from this we can deduce that, if is a character, then must be a -th root of 1, that is, it must be a number of the form for some . In particular, for every .
(For general groups, we say that is a character if it is a 1-dimensional representation and it has the property that for every . While the latter property is a consequence of the former for finite groups and, more generally, for torsion groups, this is not the case for other groups. For example, is a 1-dimensional representation for but it is not a character.)
At first sight, it might look like a finite group might have an infinite number of characters (or at least that’s what I thought when I first saw the definition). There is however a simple argument that shows that a finite group cannot have more than characters.
Consider the set of all functions of the form ; we can think of it as a -dimensional vector space over . We have that the characters of are linearly independent, and so there cannot be more than of them. In fact, even more is true: the characters of are orthogonal to each other. For two functions , define their inner product as
Then, if and are two different characters, we have
The normalization in the definition of inner product is convenient because then we also have if is a character. (We will not prove these claims, but the proofs are very simple.)
We will now show that the cyclic group has indeed distinct characters . This means that this set of characters forms an orthonormal basis for the set of functions , and that each such function can be written as a linear combination
where the coefficients can be computed as the inner product
(The equation (*) is the Fourier expansion of , and the function is called the Fourier transform of .)
Here is how to define the characters : for each , define . It is immediate to verify that each such function is a character, and that, for we are, indeed, defining different functions. By the previously mentioned results, there is no other function.
Let’s see one more example: consider , that is, with the operation of bit-wise XOR. For each , define the function
We can again verify that all these functions are distinct, that each of them is a character, and so that they include all the characters of . The reader should be able to see the pattern and to reconstruct the characters of the group
thus having a complete understanding of the set of characters of any given finite Abelian group.
At long last, we can get to the subject of expansion.
Let be a finite Abelian group, and be a set of generators such that if then . Definite the Cayley graph where every element of is a vertex and where is an edge if . This is clearly an -regular undirected graph. Let be the set of characters of . Think of each character as an -dimensional vector. (The vector that has the value in the -th coordinate.) Then these vectors are orthogonal to each other. We claim that they are also eigenvectors for the adjacency matrix of .
Note a surprising fact here: the graph depends on the group and on the choice of generators . The eigenvectors of the adjacency matrix, however, depend on alone. (The eigenvalues, of course, will depend on .)
The proof of the claim is immediate. Let be the adjacency matrix of , then the -th entry of the vector is
We are done! The vector is indeed an eigenvector, of eigenvalue . Since we have eigenvectors, and they are linearly independent, we have found all eigenvalues, with multiplicities.
Let’s look at the cycle with vertices. It is the Cayley graph of with generators . We have eigenvalues, one for each , and we have
this may seem to contradict our earlier claim that all eigenvalues were going to be real. But two lines of trigonometry show that, in fact,
As expected in a 2-regular graph, the largest eigenvalue is . The second largest eigenvalue, however, is , which is . This means that the expansion of the cycle is at least and, in particular, the cycle is a connected graph!
(After we are done having a good laugh at the expense of algebraic graph theory, I should add that this calculation, plus some relatively easy facts, implies that a random walk on the cycle mixes in steps. Not only this is the right bound, but it is also something that does not have a completely straightforward alternative proof.)
We do a little better with the hypercube. The hypercube is the Cayley graph of the group with the generator set that contains all the vectors that have precisely one 1. Now we have one eigenvalue for each choice of , and the corresponding eigenvalue is
The largest eigenvalue, when all the are zero, is , as expected in an -regular graph. The second largest eigenvalue, however, is at most . This means that the expansion of the hypercube is at least 1. (As it happens, it is precisely 1, as shown by a dimension cut.)