Permutation groups

Last time, we looked at how graphs are represented in the Haskell for Maths library. What we're heading for is to look at symmetries of graphs. But first, we need to talk about permutation groups.

Given a finite set, a permutation is an arrangement of its elements into a sequence. For example, here are three permutations of the numbers 1 to 5:
[1,2,3,4,5]
[1,5,4,3,2]
[2,1,3,4,5]

Where it gets interesting is if the set we are permuting is the underlying set of some mathematical object - such as the vertex set of a graph. For example, we saw last time that we can label the vertices of the cyclic graph c 5 (the pentagon) with the numbers 1 to 5. In that case, the permutations above correspond to the following diagrams.

The permutation [1,2,3,4,5] - the diagram on the left - can be thought of as the starting position. (So the convention is that we read the numbers clockwise from the top.)
The permutation [1,5,4,3,2] - the diagram in the middle - is a reflection of the starting position in the vertical axis.
The permutation [2,1,3,4,5] - on the right - just swaps the 1 and 2 vertices.

When we write a permutation as a list of vertices, we're taking a static view of it. But we can also take a dynamic view, where we think not about where the vertices end up, but about what we had to do to get them there (from the starting position).

For example, for the reflection [1,5,4,3,2], what we had to do was swap the 2 and 5 vertices, and swap the 3 and 4 vertices. (As a hint of what's to come, we will end up writing this as [[2,5],[3,4]].)

In this view, the permutation is not the end position, but the function or map that we used to get there from the starting position. Hence, in the module Math.Algebra.Group.PermutationGroup, permutations are defined as follows

import qualified Data.Map as M

newtype Permutation a = P (M.Map a a) deriving (Eq,Ord)

Notice that, as for our Graph datatype, although we will often consider permutations as acting on integers, we have left ourselves the option of acting on other things too. Again, this will prove to be extremely useful.

The library provides three ways to construct permutations:


> :load Math.Algebra.Group.PermutationGroup
> fromList [1,5,4,3,2]
[[2,5],[3,4]]
> fromPairs [(1,1),(2,5),(3,4),(4,3),(5,2)]
[[2,5],[3,4]]
> fromCycles [[2,5],[3,4]]
[[2,5],[3,4]]


Notice that permutations are always shown in cycle notation. Once you get used to it, this is the most natural way to think about permutations. For this reason "p" is provided as a shorthand for "fromCycles", as this is how we will most often construct permutations.

Given a permutation, we can ask what is its action on a vertex, or on an edge:

> 2 .^ p [[2,5],[3,4]]
5
> [1,2] -^ p [[2,5],[3,4]]
[1,5]

This says that our reflection sends the vertex 2 to 5, and the edge [1,2] to [1,5].

Finally, if a permutation is something you do, then we can ask what happens if you do g then h, or how to undo g:

> p [[2,5],[3,4]] * p [[2,5],[3,4]]
[]
> p [[2,5],[3,4]] ^-1
[[2,5],[3,4]]

This says that if you do our reflection, and then do it again, you end up back at the starting position; and that if you want to undo our reflection, just do it again.

Exercise: Write implementations of the (.^), (-^), (*), and (^-) operators shown above, and compare with the library implementations.

There's quite a lot more in Math.Algebra.Group.PermutationGroup, which I hope to talk about at some point. But for now, that's all we need. (Although, if you want to keep following, it would be a good idea to play around and make sure you've got the hang of cycle notation.)

Next time, graph symmetries (hopefully).