every permutation has a cycle decomposition
We begin by showing that, if is a non-trivial permutation of a set , then there exists a cycle where
and a permutation of such that and .
Note that we cannot have for any . This follows from a simple induction argument. By definition . Suppose that but that . By definition, . Since is a permutation, and imply that , so , which contradicts a hypothesis. Hence, if , then so, by induction, for all .
By the pigeonhole principle, there must exist and such that but . Let be the least integer such that but when . Set . Then we have that is a cycle.
Since is a permutation and is closed under , it follows that
is also closed under . Define as follows:
Then it is easily verified that .
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 identity permutation, which requires no cycles to decompose. Next, suppose that any set with less than elements can be decomposed into cycles. Let be a permutation on a set with elements. Then, by what we have shown, can be written as the product of a cycle and a permutation which fixes the elements of the cycle. The restriction of to those elements such that is a permutation on less than elements and hence, by our supposition, can be decomposed into cycles. Thus, 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|
|Date of creation||2013-03-22 16:48:39|
|Last modified on||2013-03-22 16:48:39|
|Last modified by||rspuzio (6075)|