# Groups of Permutations

Permutation is simply scrambling or reshuffling of a given set of items. In mathematical terms, a permutation of set X is a bijection (1-1 and onto) of set X. Executing two permutations in succession results in a new permutation. Unscrambling of a permutation is itself a permutation. It's a good exercise to check that this way we get a group; a group called symmetric group on a given set. Thus S(X) is the group of permutations the permutations (symmetric group) on X. If X coincides with Nn = {x ∈ N:1≤x≤n} - a segment of the set of integers, we write Sn instead. For finite sets X, it's often convenient to identify S(X) with Sn, where n is the number of elements (cardinality) of X (n = card(X) = |X|.) Cardinality of Sn is n!:|Sn| = n!. The set of all even permutations also forms a group (a subgroup of Sn) known as the alternating group. The alternating group is denoted An (in general, A(X).) |An| = n!/2. Below I collect a few general results to be used in establishing solvability of graph puzzles (Happy 8, Blithe 12, Sliders, etc.)

If f, g ∈ Sn, consecutive execution of f and g (in this order) is denoted fg; so that we look at Sn as a multiplicative group. Accordingly, xf is a preferred notation for f(x).

### Lemma 1

Let g ∈ Sn and c = (c1 c2 ... ck), k ≤ n, be a cycle. Then g-1cg = (c1g c2g...ckg).

### Proof

If x is not one of the ci's. Then (xg)g-1cg = xcg = xg. On the other hand, (cig)g-1cg = ci+1g with an obvious modification for i = k.

### Remark

There is a Java device that helps master the operation of multiplication of permutations. It also serves as an illustration of Lemma 1.

### Lemma 2

For n > 4, then An is generated by various pairs of non-intersecting transpositions (ab)(cd), where {a,b} ∩ {c,d} = Ø.

### Proof

The Lemma is obvious since an even permutation is a product of an even number of transpositions. Thus we need only consider products (ab)(cd) of two transpositions that perhaps have common elements. If, say, b = c, choose x and y other than a, b, c, or d. Then (ab)(cd) = [(ab)(xy)][(cd)(xy)].

### Lemma 3

An is generated by all 3-cycles (abc).

Actually a stronger result holds, viz., An is generated by all 3-cycles (abc) with fixed (but arbitrary) a and b.

### Proof

Let a = 1 and b = 2 and let's prove that An is generated by the set {(12c)}. The proof is by induction on n. The result obviously holds for n = 3. Thus assume n > 3.

Let f ∩ An and nf = m. Then g = (12n)(12m)-1f is an even permutation. Also, ng = n. Therefore,we may look at g as belonging to An-1. By the inductive hypothesis g is a product of 3-cycles (12c) and so is f.

### Definition

Let S be a subgroup of S(X). S is said to be transitive if for all x, y ∈ X there is f ∈ S(X) such that xf = y. If for any x1, ..., xk, y1, ..., yk ∈ X there is f ∈ S such that xi f = yi f, for i = 1, ..., k, the group S is said to be k-transitive. 1-transitive group is transitive.

### Definition

For f ∈ S(X), support of f is defined as supp(f) = {x ∈ X: xf ≠ x}.

Support of f is the set of points not fixed by f. If supp(f)⊂Y⊂ = X, then (restricted to Y) f may be looked at as an element of S(Y). With this in mind, for a subgroup T ⊂ S(X), we write T|Y = {f ∈ T: supp(f) ⊂ Y} considered as a subgroup of S(Y).

### Lemma 4 (Wilson)

Let T be a set of 3-cycles on X, |X| = n > 2, and let <T> denote the subgroup of S(X) generated by T. Then the following are equivalent:

1. <T> = A(X).
2. <T> is transitive.

### Proof

First of all, it's clear that (i) implies (ii). To prove the reverse, assume T is given satisfying (ii). Then let Y be a subset of X such that |Y| > 2, <T>|Y = A(Y), and which is maximal with respect to these properties. We claim that Y = X (which will prove the lemma.)

If Y ≠ X, our assumption (ii) implies that either:

1. there is a 3-cycle (uvz) ∈ T with u, v ∈ Y, z∉Y; or
2. there is a 3-cycle (uvz) ∈ T with z ∈ Y, u,v∉Y.

In case (a), <T> contains (uvx), x ∈ Y-{u,v}, in addition to (uvz), so <T>|(Y∪{z}) = A(Y∪{z}) by Lemma 3.

In case (b), for each x ∈ Y, <T>|Y contains a permutation f such that z f = x. Then f -1(uvz)f = (uvx) ∩ <T>. This holds for every x ∩ Y and hence <T>|(Y ∪ {u, v}) = A(Y ∪ {u, v}) by Lemma 3. Again, the maximality of Y is contradicted.

### Lemma 5

Let S be a 2-transitive subgroup of S(X) and suppose that S contains a 3-cycle. Then A(X) ⊂ S.

### Proof

Let (uvw) ∈ S. Since S is 2-transitive, for any x,y ∈ X there exists f ∈ S such that uf = x and vf = y. From Lemma 1, g = f -1(uvw)f = (x y wf). Which means g ∈ S and xg = y. So the subgroup of S generated by 3-cycles in S is transitive. Lemma 4 completes the proof. ### References

1. J. Landin, An Introduction to Algebraic Structures, Dover, NY, 1969.
2. R. M. Wilson, Graph Puzzles, Homotopy, and the Alternating Group, J. of Combinatorial Theory, Ser B 16, 86-96 (1974). ### Permutations

• Transpositions
• Groups of Permutations
• Sliders
• Puzzles on graphs
• Equation in Permutations 