Generators and Cayley Graphs

So far we've encountered two ways to define groups. One, as all the symmetries of a figure in a space or isometries of the space itself, and the second explicitly by a group product table. In this and the next section we'll develop another very useful way of describing and investigating groups: a group presentation.

Generators

Consider the group of integers, which we'll denote Z, with the operation +. Note that we can express every element as a sum of ones and their inverses, namely negative ones; e.g. -5=-1-1-1-1-1 and 0 is the sum of 0 ones. Thus we say that the group of integers is generated by the element 1. This is also the only integer with this property; you can't express 3, for example as a sum of 2's and -2's.

On the other hand, consider the group of rotations of a regular pentagon. It consists of five elements: a rotation by 72 degree, 144, 216, 288, and finally 360, which is the identity. It too is generated by one element, namely 72 degree rotation. However, it's also generated by any of the other non-identity elements. Take for example the rotation by 144 degrees: 1*144=144, 2*144=288, 3*144=432=72, 4*144=576=216, and finally 5*144=720=0, the identity.

As you've seen in part 2 above, it's impossible to generate the dihedral group D₄ with only one element. However, it is possible to generate it with two! That is, every group element is equal to some product of two of the elements and their inverses (with each generator or inverse appearing perhaps more than once).

Some groups can't be generated using a finite number of generators. For example, the real numbers with addition or the non-zero rationals with multiplication are two such non-finitely generated groups.

Cayley Graphs

Once we figure out that a group is in fact generated by some finite collection of elements, we can construct a directed graph in which every group element corresponds to an isometry, called a Cayley graph. Here's the construction of a Cayley graph for a group G with generators {a₁, a₂,...,a_m} in 3 easy steps:

1. Draw one vertex for every group element, generator or not. (And don't forget the identity!)
2. For every generator a_j, connect vertex g to ga_j by a directed edge from g to ga_j. Label this edge with the generator.
3. Repeat step 2 for every element (i.e. vertex) g∈G.

Activity 3: The Cayley graph of David

Let's build a few Cayley graphs!

1. Draw the Cayley graph for Z₅, the group rotation symmetries of a regular pentagon, with the generator 2.
2. What does the Cayley graph for the group of integers (group operation +) and the generator 1 look like?

We can generate the group Z₆ with just one generator, namely the 60 degree rotation. However, we can also generate it with two generators: the rotations by 120 and 180 degrees. Here's what the Cayley graph looks like. (The only vertices are the labeled black dots, so while blue and red edges look like they intersect, they don't; it's just an artefact of this particular drawing.) There's a cool fact hiding here: a Cayley graph is connected (i.e. there's a path from the identity vertex to any other) if and only if the generating elements generate the whole group. Let's prove this!

3. Suppose we took only the element R₁₈₀ as a generator in the above example. What would the Cayley graph look like? Does R₁₈₀ generate Z₆?
4. Now assume you've got a group G and two elements a and b which you take to be generators. You draw the Cayley graph and notice that it's connected. Can you express an arbitrary element g∈G as a product of a, b, and their inverses? How? (Hint: follow the path.)
5. We've shown that if the graph is connected, then the assumed generators in fact generate the whole group. Let's show the other direction. Suppose a and b do generate G. Is there a path in the Cayley graph between the identity and every element g∈G?

Give each edge of a Cayley graph the length 1. This makes the graph a metric space, a space in which we can measure the distance between any two points. How? Just take the shortest length of any path in the graph connecting the two points, and call this the distance. Note that this is analogous to the usual distance in the plane: there are (infinitely) many curves connecting any two points in the plane and the distance between points is the length of the shortest such curve, a straight line. Now that we have distances we can talk about isometries, the distance preserving maps from a Cayley graph to itself.

Given a group G and it's Cayley graph Γ, pick any element g∈G. Consider the map of Γ to itself given by f_g(h)=gh, for any vertex h∈Γ, where gh is a vertex in Γ corresponding to the element gh. For a point x on the edge from h to ha_j (a_j being one of the generators), let f_g(x) be the point on the edge between gh and gha_j the same distance from gh as x was from h. Sounds a bit confusing? Worry not, it's actually very simple! Here's a picture to clarify the situation.

The usual notation for a group with specified generators is (G,S), where G is a group and S is some set of generators. Note that the set of generators S can have redundancies. For instance, the group of integers Z is generated by the element 1. It is also generated by the set {1,3}. While it may seem strange or unnecessary for S to have more generators than needed, this will prove quite useful in the next section.