Group representation

(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 $n$ elements of the group can be obtained by a sum of $O(log n)$ terms chosen, with repetitions, from a set of $O(1)$ generators; this means that a constant root of the $n^{O(1)}$ 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 $N$ elements $Z_N$ with the operation of addition (or $Z/NZ$ as mathematicians write). One can visualize this group as $N$ points equally spaced along a circle in the plane, with element $a$ forming an angle of $2\pi a/ N$ with the $x$ axis. If we want to add an element that forms an angle $\alpha$ to an element that forms an angle $\beta$, that's the same as putting the "two angles next to each other" and we get a point that forms an angle $\alpha+\beta$. More algebraically, we identify an element $a$ with the complex number $e^{2\pi a i/n}$ 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 $a$ as the operation that takes a point on the cycle and moves it by an angle of $2\pi a/N$. Addition of group elements now corresponds to "composition," that is, corresponds to applying one rotation after the other.

In this view, element $a$ is now the function that maps complex number $x$ into complex number $x\cdot e^{2\pi a i/N}$.

Suppose now that our group is a product $Z_{N_1} \times \cdots \times Z_{N_k}$ of cyclic groups. This means that a group elements if a $k$-tuple of the form $(a_1,\ldots,a_d)$, and that

$(a_1,\ldots,a_d) + (b_1,\ldots,b_d) = (a_1+b_1 \bmod N_1,\ldots,a_k+b_k \bmod N_k)$

It now makes sense to view a group element $(a_1,\ldots,a_d)$ as a "high-dimensional rotation" operation that takes in input $k$ complex numbers $(x_1,\ldots,x_k)$ and outputs the $k$ complex numbers

$(x_1 \cdot e^{2\pi a_1 i /N_1},\ldots, x_k \cdot e^{2\pi a_k i /N_k})$

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 $x$ times a diagonal matrix that has diagonal

$(e^{2\pi a_1 i /N_1},\ldots, e^{2\pi a_k i /N_k})$

Notice, also, that if $f$ is a function of the form $f(x) = A\cdot x$, where $A$ is a matrix, and $g$ is a function of the form $B\cdot x$ where $B$ is a matrix, then $f(g(x))= A\cdot B\cdot x$. That is, for linear functions, function composition is the same as matrix multiplication.

To summarize, we have started from the group $Z_{N_1} \times \cdots \times Z_{N_k}$, 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 $Z_{N_1} \times \cdots \times Z_{N_k}$, so this type of representation via diagonal matrices is possible for every finite Abelian group.

What about more general groups? If $G$ 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 $p$ be a prime (it could also be a prime power) and let us consider $2 \times 2$ matrices whose entries are integers $\bmod p$. Let us restrict ourselves to matrices whose determinant is 1 modulo $p$, and consider the operation of matrix multiplication (where, also, all operations are mod $p$). 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 $SL(2,p)$. The group $SL(2,p)$ contains the tiny subgroup of two elements $\{ I,-I\}$; in the representation of $SL(2,p)$ this shows up as a block of size 1. If we take the quotient of $SL(2,p)$ by $\{ I,-I \}$ then we get another group, which is called $PSL(2,p)$.

It is now a theorem of Frobenius that every representation of $PSL(2,p)$ has dimension at least $(p-1)/2$. This is really large compared to the size of $PSL(2,p)$: the group $SL(2,p)$ has $p(p-1)^2$ elements, and so $PSL(2,p)$ has $p(p-1)^2/2$ 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 $SL(2,p)$ and $PSL(2,p)$ 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 $\{ a, b, a+b\}$, Gowers shows that every dense Cayley graph constructed on $PSL(2,p)$ has constant edge expansion. (By dense, we mean that the degree is $\Omega(n)$, where $n$ 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 $PGL(2,p)$, which is the same as $PSL(2,p)$ 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.