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).

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.

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)].

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.

Lemma 4 (Wilson)

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

• Various ways to define a permutation
• Counting and listing all permutations
• Johnson-Trotter Algorithm: Listing All Permutations

Puzzles on graphs

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2012 Alexander Bogomolny