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 N_n = {x ∈ N:1≤x≤n} - a segment of the set of integers, we write S_n instead. For finite sets X, it's often convenient to identify S(X) with S_n, where n is the number of elements (cardinality) of X (n = card(X) = |X|.) Cardinality of S_n is n!:|S_n| = n!. The set of all even permutations also forms a group (a subgroup of S_n) known as the alternating group. The alternating group is denoted A_n (in general, A(X).) |A_n| = 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 ∈ S_n, consecutive execution of f and g (in this order) is denoted fg; so that we look at S_n as a multiplicative group. Accordingly, xf is a preferred notation for f(x).

Lemma 1

Let g ∈ S_n and c = (c₁ c₂ ... c_k), k ≤ n, be a cycle. Then g^-1cg = (c₁g c₂g...c_kg).

Proof

If x is not one of the c_i's. Then (xg)g^-1cg = xcg = xg. On the other hand, (c_ig)g^-1cg = c_i+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 A_n 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

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

Actually a stronger result holds, viz., A_n 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 A_n 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 ∩ A_n and nf = m. Then g = (12n)(12m)^-1f is an even permutation. Also, ng = n. Therefore,we may look at g as belonging to A_n-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 x₁, ..., x_k, y₁, ..., y_k ∈ X there is f ∈ S such that x_i f = y_i 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:

<T> = A(X).
<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:

there is a 3-cycle (uvz) ∈ T with u, v ∈ Y, z∉Y; or
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

J. Landin, An Introduction to Algebraic Structures, Dover, NY, 1969.
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

71536800