## Permutations (Pt. III Orbits and Cycles cont.)

**Point of post: **This post is a literal continuation of this post in the sense that if it weren’t for size constraints these two posts would be one. So, think of this as just the “next page” of that post.

*Motivation *

Recall from the last post that for any we have that can be partitioned into orbits . Notice though that each of these orbits induces an element of namely each induces given by

Permutations of this kind are going to be the archetype for the sought class of permutations we have been searching for (see the motivation of the last post if your confused). These are going to be the archetypes of *cycles.* Which we will now rigorously define.

*Cycles*

We call a *cycle *if at most of the orbits induced by has cardinality greater than one. For example given by

is a cycle since and only one of these has cardinality greater than one. Evidently cycles, in general, take a relatively simple form.

For a cycle writing the entire representation, as in , is superfluous. Instead we may write a cycle as

which is to be understood as meaning

and . Or, said differently

It’s obvious from this definition that

Thus, taking our example of as in above we see see that

*Remark: *Note that it is impossible to tell given for which we intend to view as as being a cycle in.

We say that a cycle has *length *. And we say that two cycles are *disjoint* if . With these definitions we are able to state and prove our first theorem

**Theorem: ***Let be disjoint cycles. Then,*

**Proof: **To prove the case when it suffices to show that for all . So, by assumption we have that and where . So, if for some we see that

if for some then

If then

and since all are of one of these three forms, it follows that for all , and thus .

Now, assume the result holds for . We then note that

where the last step is via the induction hypothesis since . The conclusion follows.

**Corollary: ***Using this and some real mathematical elbow grease one can show that if are disjoint cycles and then*

We now come to the main theorem of this post, namely that the set of cycles in is precisely the class of permutations for which all other permutations can be built.

**Theorem:*** Let , then may be written as the disjoint product of cycles.*

**Proof: **Let . Let is given by

we claim that . To see this be arbitrary. Then, for some . Then, recalling that by definition for all , , and we see that

and since was arbitrary it follows that . Thus, noting that each is a cycle, since and that they are disjoint since . The conclusion follows.

We will continue this post next time with the consequences of the above theorem in relation to permutation matrices.

**References:**

1. Fraleigh, John B., and Victor J. Katz. *A First Course in Abstract Algebra*. Boston: Addison-Wesley, 2003. Print.

2. Dummit, David Steven., and Richard M. Foote. *Abstract Algebra*. Hoboken, NJ: Wiley, 2004. Print.

[…] post: This will be a relatively short post discussing a nice corollary of the last theorem in the last post relating to permutation matrices. In essence, it shows that every permutation matrix may be […]

Pingback by Permutations (Pt. IV Consequences for Permutation Matrices) « Abstract Nonsense | November 7, 2010 |

[…] cycle is called a transposition if is of length two, in other words if . Intuitively a transposition is […]

Pingback by Permutations (Pt.V Transpositions and the Sign of a Permutation) « Abstract Nonsense | November 7, 2010 |

[…] about the conjugacy classes of we must discuss the cycle type of an element of . In particular we know that every element can be written as the product of disjoint cycles, and moreover that up to a […]

Pingback by Conjugacy Classes on the Symmetric Group « Abstract Nonsense | May 10, 2011 |