(As will become clear soon, I am totally out of my depth: Readers who find glaring mistakes, and even small ones, should note them in the comments.)
In the previous post on expanders we left off with the observation that if we want to construct an expanding Cayley graph, then we need to start from a group where all elements of the group can be obtained by a sum of terms chosen, with repetitions, from a set of generators; this means that a constant root of the ways of rearranging such sums must lead to different results. The group, then, has to be non-commutative in a very strong sense.
I will describe a way in which a group used to construct expanders is “very non-commutative.” This will not be a sufficient property for the expansion, but it is closely related and it will come up in the paper of Gowers that we will talk about later.
With this objective in mind, let’s see the notion of group representation. Let’s start from the simplest group, the cyclic group of elements with the operation of addition (or as mathematicians write). One can visualize this group as points equally spaced along a circle in the plane, with element forming an angle of with the axis. If we want to add an element that forms an angle to an element that forms an angle , that’s the same as putting the “two angles next to each other” and we get a point that forms an angle . More algebraically, we identify an element with the complex number and we realize group addition as multiplication of complex numbers. There is, however, another way of visualizing the cyclic group on a cycle. We can think of group element as the operation that takes a point on the cycle and moves it by an angle of . Addition of group elements now corresponds to “composition,” that is, corresponds to applying one rotation after the other.
In this view, element is now the function that maps complex number into complex number .
Suppose now that our group is a product of cyclic groups. This means that a group elements if a -tuple of the form , and that
It now makes sense to view a group element as a “high-dimensional rotation” operation that takes in input complex numbers and outputs the complex numbers
If we take this view, we have, again, the property that group addition becomes composition of functions. Note, also, that the function that we have associated to each group element is a very simple type of linear function: it is simply multiplication of times a diagonal matrix that has diagonal
Notice, also, that if is a function of the form , where is a matrix, and is a function of the form where is a matrix, then . That is, for linear functions, function composition is the same as matrix multiplication.
To summarize, we have started from the group , and we have found a way to associate a complex-valued diagonal matrix to each group element in such a way that group addition becomes matrix multiplication.
It is known that all finite Abelian groups can be written as , so this type of representation via diagonal matrices is possible for every finite Abelian group.
What about more general groups? If is an arbitrary finite group, it is possible to associate to each element a block-diagonal matrix in such a way that group addition becomes matrix multiplication.
(It is common to call a group operation “multiplication” when a group is not Abelian, but for consistency with the rest of the post I will keep calling it addition.)
(By the way, it is also possible to represent infinite groups by associating a linear operator to each group element, but we will only discuss finite groups here.)
If the group is Abelian, then the matrices are diagonal, that is, they are block-diagonal matrices with “block size one.” So one way of quantifying “how non-Abelian” is a group is to consider how small the blocks can be in such matrix representations. That’s the dimension of the representation.
Here is an example of a family of groups whose representations cannot be low-dimensional. Let be a prime (it could also be a prime power) and let us consider matrices whose entries are integers . Let us restrict ourselves to matrices whose determinant is 1 modulo , and consider the operation of matrix multiplication (where, also, all operations are mod ). This set of matrices forms a group, because the matrices are invertible (the determinant is non-zero) and the set contains the identity matrix and is closed under product. This group is called . The group contains the tiny subgroup of two elements ; in the representation of this shows up as a block of size 1. If we take the quotient of by then we get another group, which is called .
It is now a theorem of Frobenius that every representation of has dimension at least . This is really large compared to the size of : the group has elements, and so has elements. The dimension of the representation is thus approximately the cube root of the number of elements of the group.
Going back to representations of Abelian groups, we see that, in that case, not only each block had size one, but also that the entire matrix had size at most logarithmic in the number of elements of the group. This shows that and are, at least in this particular sense, “very non-Abelian,” and it is an encouraging sign that they may be useful in constructing expanders and other quasi-random objects.
On his way toward a question about subsets of groups not containing triples of the form , Gowers shows that every dense Cayley graph constructed on has constant edge expansion. (By dense, we mean that the degree is , where is the number of vertices.) This is a result that, assuming Frobenius theorem, has a simple proof, which I hope to understand and describe at a later point.
The celebrated Ramanujan graphs of Lubotzky, Phillips and Sarnak are constant-degree Cayley graphs constructed from , which is the same as except that we put no restriction on the determinant. Their relationship between degree and eigenvalue gap is best possible. The analysis of Lubotzky et al. is, unfortunately, completely out of reach.