Permutations in Practice

In the introduction we defined a group abstractly. This chapter introduces the kind of group we spend the rest of these notes with — a permutation group — and shows how to compute with one in GAP. The running example throughout will be the ball puzzle from the previous chapter.

Permutations and cycle notation

A permutation of a finite set \(\{1, \ldots, n\}\) is a bijection from the set to itself. Two permutations can be composed (apply one after the other), every permutation has an inverse, and “do nothing” is the identity, so the set of all permutations on \(\{1, \ldots, n\}\) forms a group. This is the symmetric group \(S_n\), and it has \(n!\) elements.

A permutation group is any group whose elements are permutations. Every finite group can be written as a permutation group (this is Cayley’s theorem), so restricting to permutation groups isn’t losing any generality.

The most compact way to write a permutation is cycle notation. The expression \((1,2,5,4)\) means “1 goes to 2, 2 goes to 5, 5 goes to 4, and 4 goes back to 1”. Any point not listed is fixed. Longer permutations are written as a product of cycles — for example \((1,3)(2,5,4)\) swaps 1 and 3, and separately cycles \(2 \to 5 \to 4 \to 2\).

The identity permutation, which fixes everything, is written ().

The ball puzzle as a permutation group

Here is the puzzle from the introduction, so you can play along.

Let’s write the puzzle moves as permutations. Rotate Left cycles the balls around the red circle. From the starting position, it takes the ball at position 1 to position 2, position 2 to position 5, position 5 to position 4, and position 4 back to position 1. In cycle notation:

\[L = (1,2,5,4).\]

Rotate Right cycles balls around the blue circle:

\[R = (2,3,6,5).\]

What happens when we press Rotate Left then Rotate Right? We compose the permutations. In GAP, we write this as \(L \ast R\) and read it left-to-right: first apply \(L\), then apply \(R\). Tracking where each position ends up:

1 → (under \(L\)) 2 → (under \(R\)) 3. So \(1 \mapsto 3\).
2 → 5 → 2. So \(2 \mapsto 2\).
3 → 3 → 6. So \(3 \mapsto 6\).
4 → 1 → 1. So \(4 \mapsto 1\).
5 → 4 → 4. So \(5 \mapsto 4\).
6 → 6 → 5. So \(6 \mapsto 5\).

Collecting this into cycle notation gives \(L \cdot R = (1,3,6,5,4)\).

The inverse of a permutation reverses every cycle. So \(L^{-1} = (1,4,5,2)\) — which matches the fact that rotating left three times undoes a single left rotation.

Computing with the ball group in GAP

GAP uses the same cycle notation we just introduced. Let’s define our generators and ask for the size of the group they generate.

L := (1,2,5,4);;
R := (2,3,6,5);;
G := Group(L, R);;
Size(G);

Composition uses *, the inverse uses ^-1, and Order returns the smallest positive integer \(k\) such that \(g^k\) is the identity.

L * R;

(1,3,6,5,4)

L^-1;

(1,4,5,2)

Order(L);

\(L\) has order 4 because rotating left four times brings every ball back to where it started.

Generators

We never had to tell GAP every element of our group. Instead, we gave it two permutations and said “take the group generated by these”. The Group function does exactly this: it takes a list of permutations and returns the smallest group containing them.

The word generator recurs throughout these notes. A generating set for a group \(G\) is a set \(S \subseteq G\) such that every element of \(G\) can be written as a product of elements of \(S\) and their inverses. A group may have many different generating sets; two generators is typical for the kind of groups we will study.

For our ball group, every one of the 120 elements is expressible as a product of \(L\)s and \(R\)s (and their inverses). The intro chapter gave an explicit such product for the permutation \((1,4)(2,5)(3,6)\).

Orbits

Suppose we can only press Rotate Left, never Rotate Right. Which balls can reach which positions? Ball 1 can reach positions 2, 5, 4, and back to 1. Balls 3 and 6 can’t move at all, because they aren’t on the red circle. So under \(\langle L \rangle\) (the group generated by \(L\) alone) the positions split into three classes: \(\{1, 2, 4, 5\}\), \(\{3\}\), and \(\{6\}\).

Each such class is called an orbit. Formally, the orbit of a point \(x\) in a group \(G\) is the set

\[x^G = \{x^g : g \in G\}.\]

GAP computes orbits with Orbit and Orbits.

Orbit(G, 1);

[ 1, 4, 5, 2, 6, 3 ]

Orbits(G, [1..6]);

[ [ 1, 2, 5, 3, 4, 6 ] ]

# With only Rotate Left, the orbits split into three pieces.
Orbits(Group(L), [1..6]);

[ [ 1, 2, 5, 4 ], [ 3 ], [ 6 ] ]

# And with only Rotate Right.
Orbits(Group(R), [1..6]);

[ [ 1 ], [ 2, 3, 6, 5 ], [ 4 ] ]

When a group has a single orbit on the set it acts on, we say it acts transitively. Our full ball group \(G\) is transitive on the six positions, but neither \(\langle L \rangle\) nor \(\langle R \rangle\) alone is.

Stabilisers

Suppose we want to end up with ball 1 back in its starting position. Which moves are allowed? The subgroup of \(G\) which fixes a given point \(x\) is the stabiliser of \(x\) in \(G\), written \(G_x\). Stabilisers are the central building block of the next chapter.

Stabilizer(G, 1);

Group([ (2,3,6,5), (3,5,4,6) ])

Size(Stabilizer(G, 1));

Of the 120 moves in \(G\), exactly 20 keep ball 1 in place. This is no coincidence: the orbit–stabiliser theorem says the orbit size always divides the group size, with the stabiliser size as the quotient. Here the orbit of 1 has 6 elements, and \(120 / 6 = 20\).

This is the whole group of moves fixing ball 1, not just the moves that never touch ball 1. That distinction matters. If we only insisted on never-touching ball 1, we could only press Rotate Right (since a single Rotate Left would move it). Pressing only Rotate Right also never moves ball 4, since ball 4 isn’t on the blue circle — so you might guess ball 4 can’t move while ball 1 is fixed.

Except — it can. The stabiliser contains any sequence of \(L\)s and \(R\)s whose overall effect leaves ball 1 in place, even if individual moves don’t. For instance, press \(L\) three times, then \(R\) twice, then \(L\) once. Ball 1 takes a tour through positions 2, 5, 4, 1, 1, 1, 1 and ends up back where it started, while the remaining balls are shuffled into 1 2 4 on top and 3 6 5 on the bottom — so ball 4 is now in the top-right position.

1^(L^3 * R^2 * L);

4^(L^3 * R^2 * L);

Looking at the orbits of the stabiliser confirms this:

Orbits(Stabilizer(G, 1), [1..6]);

[ [ 1 ], [ 2, 3, 6, 5, 4 ] ]

Ball 1 is in its own orbit of size 1 (as it must be). Every other ball shares a single orbit of size 5 — meaning each of them can reach any of the other four positions without ever displacing ball 1. The naive guess — “if ball 1 is fixed, ball 4 can’t move” — was wrong by a lot.

With this vocabulary in hand — permutations, cycle notation, generators, orbits, stabilisers — we are ready to meet the data structure that makes computing with permutation groups efficient: the stabiliser chain.