every permutation has a cycle decomposition

In this entry, we shall show that every permutationMathworldPlanetmath of a finite setMathworldPlanetmath can be factored into a productMathworldPlanetmathPlanetmath of disjoint cycles. To accomplish this, we shall proceed in two steps.

We begin by showing that, if f is a non-trivial permutation of a set {xi1in}, then there exists a cycle (y1,ym) where


and a permutation g of {xi1in} such that f=(y1,ym)g and g(yi)=yi.

Since the permutation is not trivial, there exists z such that f(z)z. Define a sequence inductively as follows:

z1 =z
zk+1 =f(zk)

Note that we cannot have zk+1=zk for any k. This follows from a simple inductionMathworldPlanetmath argument. By definition f(z1)=f(z)z=z1. Suppose that f(zk)zk but that f(zk+1)=zk+1. By definition, f(zk)=zk+1. Since f is a permutation, f(zk)=zk+1 and f(zk+1)=zk+1 imply that zk=zk+1, so zk=f(zk), which contradicts a hypothesisMathworldPlanetmath. Hence, if f(zk)zk, then f(zk+1)zk+1 so, by induction, f(zk)zk for all k.

By the pigeonhole principleMathworldPlanetmath, there must exist p and q such that p<q but f(zp)=f(zq). Let m be the least integer such that f(zp)=f(zp+m) but f(zp)f(sp+k) when k<m. Set yk=zk+p. Then we have that (y1,ym) is a cycle.

Since f is a permutation and {yi1im} is closed underPlanetmathPlanetmath f, it follows that


is also closed under f. Define g as follows:


Then it is easily verified that f=(y1,ym)g.

We are now in a position to finish the proof that every permutation can be decomposed into cycles. Trivially, a permutation of a set with one element can be decomposed into cycles because the only permutation of a set with one element is the identityPlanetmathPlanetmathPlanetmathPlanetmath permutation, which requires no cycles to decompose. Next, suppose that any set with less than n elements can be decomposed into cycles. Let f be a permutation on a set with n elements. Then, by what we have shown, f can be written as the product of a cycle and a permutation g which fixes the elements of the cycle. The restrictionPlanetmathPlanetmathPlanetmathPlanetmath of g to those elements z such that g(z)z is a permutation on less than n elements and hence, by our supposition, can be decomposed into cycles. Thus, f can also be decomposed into cycles. By induction, we conclude that any permutation of a finite set can be decomposed into cycles.

Title every permutation has a cycle decomposition
Canonical name EveryPermutationHasACycleDecomposition
Date of creation 2013-03-22 16:48:39
Last modified on 2013-03-22 16:48:39
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 10
Author rspuzio (6075)
Entry type Proof
Classification msc 03-00
Classification msc 05A05
Classification msc 20F55