Permutation Diagrams

 Figure 1

In these pages, the structure of a group is sometimes shown by a "permutation diagram". This page explains how we use permutation diagrams.

Suppose a group is generated by two permutations, (a b c) and (c,d). We can illustrate this by Figure 1 to the right. The four vertices of the diagram are the four members of the set permuted (a, b, c, d). The black arcs show the action of the generator (a b c), and the red arc shows the action of the element (c,d).

The relationship between permutation diagrams and generating permutations

We can specify a group by a permutation diagram, and we can specify it by a set of permutations which generate it. Instead of Figure 1, we could have given the permutations (a,b,c), (c,d). These two ways of specifying it are equivalent.

Published works prefer to use sets of permutations, which are easier to print. I prefer permutation diagrams, which I find easier to interpret.

Crossings

 Figure 2a Figure 2b

Pemutation diagrams are best drawn without the arcs crossing, as crossings make them harder to understand. Figure 2a does not have arcs that cross, figure 2b has black arcs that cross. It is important, but I hope reasonably obvious, that the six points where black arcs cross do not represent elements that are permuted by the group – they are just artefacts of the way I have drawn the diagram in the plane.

Both figures show S4, acting on 12 points. In each figure, the outer black 4-cycle runs anticlockwise, while the two inner 4-cycles are trapezoidal and run clockwise.


Other surfaces

 Figure 3

The figures above are permutation diagrams drawn on a piece of the plane. If we don't care about the arcs crossing, any permutation diagram can be drawn on the plane. But if we want to avoid the arcs crossing, we may need to use some other surface.

How we show surfaces other than the plane is explained at representation of 2-manifolds.

Figure 3 shows a permutation diagram for Q8, drawn on a torus without the arcs crossing.


Some conventions

These pages use some convetntions regarding permutation diagrams, which are described here.

Direction of loops

 Figure 4a Figure 4b Figure 4c Figure 4d Figure 4e

A closed loop of arcs runs clockwise, unless explicitly shown to run anticlockwise.

Thus in Figure 4a, both red loops run clockwise (we can show that it does not matter which ways the black loops run). In Figure 4b, one red loop runs clockwise and the other anticlockwise, as indicated by the arrowhead. In Figure 4c one red loop runs clockwise and the other anticlockwise, as indicated by the arrowheads. In Figure 4d, one red loop runs clockwise and the other anticlockwise, as indicated by the symbol (which is in the same colour as the loop it refers to).

Figure 4e shows both red loops as running clockwise, and so is equivalent to Figure 4a.

Figures 4a and 4e both show SL23. Figures 4b, 4c, and 4d show PSL27.

Letters used to denote generators

Each colour of a permutation corresponds to a generator of the group. In the text accompanying a diagram, we may refer to the geenerator by a letter associated with the colour: r for red, g for green, b for blue, y for yellow, k for black, c for cyan, o for orange, p for purple.


Permutation diagrams and Cayley diagrams

Cayley diagrams (also known as Cayley graphs) are special cases of permutation diagrams. "Cayley diagram" can be defined as follows.

A Cayley diagram of a group G is a transitive permutation diagram of G acting on [G] points.


Permutation diagrams and group centres

 Figure 5a Figure 5b Figure 5c Figure 5d Figure 5e

If a symmetry of a permutation diagram corresponds to an element of the group for the diagram, then that element must be central in the group.

In figure 5a, the element k2 rotates the whole digram through a quarter-turn, so this order-4 element must be central. This is the modular group of order 16, with centre C4.
In figure 5b, the element k4 rotates the whole diagram through a half-turn, so this order-2 element must be central. This is the quasidihedral group of order 16, with centre C2.
In figure 5c, the element k4 rotates the whole diagram through a half-turn, though k2 does not rotate it through a quarter-turn; so this order-2 element must be central. This is again the quasidihedral group of order 16 with centre C2.
In figure 5d, the element k4 rotates the whole diagram through a half-turn, though k2 does not rotate it through a quarter-turn; so this order-2 element must be central. This is the dihedral group of order 16, with centre C2.
In figure 5e, the element k2 rotates the whole diagram through a half-turn, so this order-2 element must be central. This is the quaternion group of order 8, with centre C2.


Permutation diagrams and dihedral groups

Here we look at a simple application of permutation diagrams. All the figures in this section are permutation diagrams. The octagon and the heptagon serve as examples for all even and odd polygons.

 Figure 6a Figure 6b Figure 6c Figure 6d  Figure 6e Figure 6f Figure 6g

Consider an octagon. Its symmetry group is the dihedral group of order 16. This can be generated by a rotation (shown in black in figure 6a) and a reflection (shown in red in figure 6a). Or it can be generated by the same (black) rotation, and by a different reflection, shown in green in figure 6b.

If we combine these, then discard the black generator, we see that two reflection generate the group, as seen in figure 6c. This can then be rearranged to give figure 6d.

Alternatively, we can take figures 6a and 6e, combine them and discard the black generator to give figure 6f, and rearrange it to give figure 6g.


 Figure 7a Figure 7b Figure 7c Figure 7d

If we start with an odd-sided polygon, the heptagon, there are fewer options. Its symmetry group, the dihedral group of order 14, can be generated by a rotation (shown in black in figure 7a) and a reflection (shown in red in figure 7a). Or it can be generated by the same (black) rotation, and by a different reflection, shown in green in figure 7b. If we combine these, then discard the black generator, we see that two reflection generate the group, as seen in figure 7c. This can then be rearranged to give figure 7d.


Permutation diagrams and wreath products

are considered in a separate page: Permutation diagrams and wreath products.


Copyright N.S.Wedd 2012