Conjugacy classes, part 1

(New release: HaskellForMaths 0.1.5 is available here, or here.)

Over the last few weeks, we've been looking at the HaskellForMaths code for specifying graphs, and then finding generators for their automorphism groups. However, in our hurry, we haven't really stopped to take a good look at those automorphisms (symmetries) themselves.

For example, consider our old favourite, the pentagon c 5.

> :load Math.Combinatorics.GraphAuts
> mapM_ print $ elts $ graphAuts2 $ c 5
[]
[[1,2],[3,5]]
[[1,2,3,4,5]]
[[1,3,5,2,4]]
[[1,3],[4,5]]
[[1,4],[2,3]]
[[1,4,2,5,3]]
[[1,5,4,3,2]]
[[1,5],[2,4]]
[[2,5],[3,4]]

We can divide the symmetries of c 5 into four different classes:

• The identity permutation, [] or 1, which leaves c 5 as it is
• Five reflections, which reflect everything in the axis joining a vertex and the midpoint of the opposite edge. For example, [[2,5],[3,4]] is the reflection in the vertical axis.
  
• Two 1/5 rotations [[1,2,3,4,5]] and [[1,5,4,3,2]]
  
• Two 2/5 rotations [[1,3,5,2,4]] and [[1,4,2,5,3]]

Within each of these four classes, the symmetries are in some sense the same symmetry, just viewed from a different angle. What I see as the reflection in the vertical axis looks just like the reflection in one of the diagonal axes to someone sitting at a different chair around the table. What I see as the clockwise 1/5 rotation looks like an anti-clockwise 1/5 rotation to someone looking from behind the glass.

So the intuition we're trying to capture is that among the symmetries of a given graph, there are several different classes, but within each class, the symmetries are somehow the same, just viewed from a different angle. In group theory, these are called conjugacy classes, and that's what I want to explore this week.

Let's look at an example in more detail. What does it mean to say that the reflection [[2,5],[3,4]] in the vertical axis, and the reflection [[1,2],[3,5]] in the 36 degree axis are somehow the same. Well I think of it like this.

Suppose that I'm sitting at the bottom of the table (between the 3 and the 4), with a camera, and I take a short movie of the [[2,5],[3,4]] reflection as it takes place. Now, suppose that instead, I go and sit between the 1 and the 2, and then take a movie of the [[1,2],[3,5]] reflection. The two movies are both going to look like reflection in the vertical axis - because from the camera viewpoint, that's what they both were.

Next, suppose that instead of me moving to another chair to get my view, we move the table back round to me. So I rotate the table (and the graph) by a 2/5 clockwise turn, so that the 1 and 2 are either side of me. Then I perform the [[2,5],[3,4]] reflection in the vertical axis, and take my movie of it. Then I move the table back by a 2/5 anti-clockwise turn. So I still get a movie of a reflection in the vertical axis. But the overall effect on the graph is actually the [[1,2],[3,5]] reflection.

Now, the key point is that when I moved the table at the beginning, I was doing a graph symmetry (2/5 clockwise turn). And when I moved the table back again at the end, I was just undoing the symmetry.

We will say that symmetries g1 and g2 are somehow the same if there is a symmetry h such that:
doing h, then doing g1, then undoing h is the same as doing g2.
In our example:
doing [[1,3,5,2,4]], then [[2,5],[3,4]], then undoing [[1,3,5,2,4]] is the same as doing [[1,2],[3,5]].

Or, in the language of group theory, we will say that g1 and g2 are conjugate if there is an h such that:
h * g1 * h^-1 = g2
In our example:
> p [[1,3,5,2,4]] * p [[2,5],[3,4]] * p [[1,3,5,2,4]] ^-1 == p [[1,2],[3,5]]
True

In HaskellForMaths, the conjugate of g by h is defined as follows:
g ~^ h = h^-1 * g * h
(Note that we now put the h^-1 in front and the h behind the g, as is customary in the literature. Clearly this makes no real difference to what's going on.)

Conjugacy is an equivalence relation. That is:

• It is reflexive - g is conjugate to itself (taking h = 1)
• It is symmetric - if g1 is conjugate to g2 then g2 is conjugate to g1 (replacing h by h^-1)
• It is transitive - if g1 is conjugate to g2 (by h), and g2 is conjugate to g3 (by k), then g1 is conjugate to g3 (by h*k)
  

Perhaps at this point, it's worth mentioning the mnemonic for some of these symbolic operators we've seen. Suppose that we have a vertex v, and edge e, and permutations g and h. Then:

• v .^ g means the image of the vertex v when acted on by g. The dot is meant to represent a vertex.
• e -^ g means the image of the edge e when acted on by g. The dash is meant to represent an edge.
• g ~^ h means the conjugate of g by h. The tilde is meant to remind you of conjugacy because tilde is the customary symbol for an equivalence relation.
  

Next, we would like to be able to find the conjugacy classes of a group. To do this, we first introduce a very useful auxiliary function:

import qualified Data.Set as S

closure xs fs = closure' S.empty (S.fromList xs) where
    closure' interior boundary
        | S.null boundary = S.toList interior
        | otherwise =
            let interior' = S.union interior boundary
                boundary' = S.fromList [f x | x <- S.toList boundary, f <- fs] S.\\ interior'
            in closure' interior' boundary' 

What closure is doing is, starting with a set xs, it is repeatedly growing the set by adding new elements f x, by applying the functions fs - until we get to the point where the set is closed, meaning that for every x in the set, f x is also already in the set.

We've already been using this. The "elts" function that we've been using to list all elements of the group generated by gs, can be defined as follows:

elts gs = closure [1] [ *g | g <- gs]

It is now straightforward to calculate the conjugacy class of an element h in the group generated by gs:

conjClass gs h = closure [h] [ ~^ g | g <- gs]

For example:

> conjClass (graphAuts2 $ c 5) (p [[1,2,3,4,5]])
[[[1,2,3,4,5]],[[1,5,4,3,2]]]

Now, given a group of graph automorphisms, what we would like to do is find all the conjugacy classes, so that we can understand the different types of symmetry that the graph has. However, we don't really need to list all the elements of each conjugacy class - it will be sufficient to have a single representative of each class, and perhaps also to know how many elements are in that class.

conjClassReps gs = conjClassReps' (elts gs) where
    conjClassReps' (h:hs) =
        let cc = conjClass gs h in (h, length cc) : conjClassReps' (hs \\ cc)
    conjClassReps' [] = []

Okay, so let's test it out.

> mapM_ print $ conjClassReps $ graphAuts2 $ c 5
([],1)
([[1,2],[3,5]],5)
([[1,2,3,4,5]],2)
([[1,3,5,2,4]],2)

These are the four classes that we identified at the beginning.

To summarise, conjugacy classes give us a way to investigate the different types of symmetries that a graph has. (Later on, we'll use groups and conjugacy classes to study the symmetries of other objects besides graphs.)

That's it for now. Next time, we'll look at a few more examples.

Exercise: Investigate the conjugacy classes of symmetries of the cube, q 3. Describe the different classes.
Hint: Start by typing:
> mapM_ print $ conjClassReps $ graphAuts2 $ q 3