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

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

    Copyright © 1996-2017 Alexander Bogomolny

  •  62645494

    Search by google: