# 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} = {x ∈ N:1≤x≤n}_{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 _{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).) _{n}| = n!/2.

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, x*f* is a preferred notation for *f(*x*)*.

### Lemma 1

Let *g* ∈ S_{n} and *c* = (c_{1} c_{2} ... c_{k}), *g ^{-1}cg* = (c

_{1}

*g*c

_{2}

*g*...c

_{k}

*g*).

### Proof

If x is not one of the c_{i}'s. Then *g*)*g ^{-1}cg* = x

*cg*= x

*g*.

_{i}

*g*)

*g*

^{-1}

*cg*= c

_{i+1}

*g*

*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

### 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,

### 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

Let *f* ∩ A_{n} and *f* = m.*g* = (12n)(12m)^{-1}*f**g* = n._{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 *f* ∈ S(X)*f* = y._{1}, ..., x_{k}, y_{1}, ..., y_{k} ∈ X*f* ∈ S_{i} *f* = y_{i} *f*,*k-transitive*. 1-transitive group is transitive.

### Definition

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

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

### Lemma 4 (Wilson)

- <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} = A(Y),

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 *f* = x.*f ^{-1}*(uvz)

*f*= (uvx) ∩ <T>.

_{(Y ∪ {u, v})}= A(Y ∪ {u, v})

### Lemma 5

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

### Proof

Let (uvw) ∈ S. Since S is 2-transitive, for any x,y ∈ X there exists *f* ∈ S*f* = x*f* = y.*g* = *f* ^{-1}(uvw)*f* = (x y w*f*).*g* ∈ S*g* = y.

### 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

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

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

Copyright © 1996-2017 Alexander Bogomolny

61197072 |