Cut the knot: learn to enjoy mathematics
A math books store at a unique math study site. Learn to enjoy mathematics.
Google
Web CTK
Best sites for teachers
Sites for teachers
Sites for parents
Terms of use
Awards

Interactive Activities
CTK Exchange
CTK Insights - a blog

Games & Puzzles
What Is What
Arithmetic/Algebra
Geometry
Probability
Outline Mathematics
Make an Identity
Book Reviews
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
Visual Illusions
My Logo
Math Poll
Cut The Knot!
MSET99 Talk
Other Math sites
Front Page
Movie shortcuts
Personal info
Reciprocal links
Privacy Policy

Guest book
News sites

Recommend this site

Best sites for teachers
Sites for teachers
Sites for parents

Education & Parenting

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

Groups of Permutations

Permutation is simply scrambling or reshuffling of a given set of items. 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 permutation (symmetric) group on X. If X coincides with Nn = {xN:1xn} - 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).) Cardinality of Sn is n!: card(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).) Card(An) = n!/2. Below I wish to collect a few general results to be used in establishing solvability of graph puzzles (Happy 8, Blithe 12, Sliders, etc.)

If f, gSn, 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 gSn and c = (c1 c2...ck), kn, 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 fAn 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,yX there exists fS(X) such that xf = y. If for any x1,...,xk,y1,...,ykX there exists fS 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 fS(X), support of f is defined as supp(f) = {xX: xfx}.

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

Lemma 4 [Wilson]

Let T be a set of 3-cycles on X, card(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 card(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 YX, our assumption (ii) implies that either:

  1. there exists a 3-cycle (uvz)T with u,vY, zY; or
  2. there exists a 3-cycle (uvz)T with zY, u,vY.

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

In case (b), for each xY, <T>|Y contains a permutation f such that z f = x. Then -1(uvz)f = (uvx)<T>. This holds for every xY 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,yX there exists fS such that uf = x and vf = y. From Lemma 1, g = f -1(uvw)f = (x y wf). Which means gS 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).


Copyright © 1996-2008 Alexander Bogomolny

28677866Page copy protected against web site content infringement by Copyscape


Search:
Keywords:


Latest on CTK Exchange
Math
Posted by Laura
2 messages
06:56 AM, Apr-15-08

Divisibility rules - Jargon buste ...
Posted by Carolyn
2 messages
08:35 AM, Apr-04-08

product of fractions
Posted by ke_45
3 messages
08:37 AM, May-06-08

Distance to the horizon
Posted by Monty
3 messages
04:38 PM, May-08-08

Mistake on the page (an aside, Be ...
Posted by Max
4 messages
10:28 AM, Feb-28-08

Nim Games - a query
Posted by Akash Kumar
1 messages
08:53 AM, Apr-15-08

A typo in
Posted by alexwajn
1 messages
11:36 PM, Apr-19-08