## Permutations (Pt. III Orbits and Cycles)

**Point of post: **In this post we continue the discussion of permutations discussed here and here in our journey to understand permutations rigorously, clearly, and fully so that we may discuss the basics of multilinear forms as is told in Halmos’s book. In it we will discuss the ideas of orbits and their ilk, cycles.

*Remark: *Because of the amount of information that will go into this “post”, I will have to break it into two smaller posts. I chose not to break orbits and cycles into separate posts unto themselves since they are inextricably linked (at least in the context we’re viewing them in).

*Motivation *

It is common place in mathematics to take concepts and try to ascertain what is the most fundamental way to describe them. For topological spaces we have subbases, for vector spaces we have bases, for groups we have generators. Permutations are no different. We are looking for some fundamental, easily described, class of permutations such that every permutation can be written as a product (compostion) of such matrices. We shall begin our discussion with a few brief conventions on notation Next we will define *orbits *which we shall see are in essence partitions induced by a permutation . From there we will use this idea of orbits to define *cycles *which shall be the fundamental types of permutation of which all permutations are composed of.

*Preliminarires*

Now that we are better acquainted with what permutations really are we discuss a convenient notational tool for describing them. For example, suppose we wanted to consider given by

having to write this table (i.e. write out in essence ) is a pain. The standard convention is to write

Thus, in general for we may represent it as

The other common notation is to, once acquainted, omit the actual composition symbol when composing permutations, giving a more group theoretic look. In other words means the same thing, in this context, as . Thus, combining this with the above discussion we may write as

Lastly, for we define , , and . From this it’s not hard to see that

and

*Orbits*

In this spirit of this post we can recall that if then

eventually must start to repeat, in the sense that for some . But, this clearly implies by injectivity that . Intuitively this is the orbit of under , namely

It turns out then that, in a sense we shall technically define in a second, these orbits partition into disjoint classes.

So now that we have an idea of what an orbit is, we can attempt to define it rigorously. We begin by, for a fixed , defining a relation on by

**Theorem: ***The relation is an equivalence relation.*

**Proof: **Clearly is reflexive since . To see that is symmetric we note that if then for some and so and thus . Lastly, we note that if and that and for some and thus

and thus .

Now, it’s clear that the equivalence class of some under are the same as the orbit of under . Thus, we now *define *the *orbit *of under as

The set of all orbits under is denoted . Let’s, for the sake of clarity, give an example. Namely, let’s take as listed above and write out the cycles. To do this we fix and consider until we start repeating and then this set of non-repeats will form the orbit of under . And, since these orbits partition we’ll know we’re done once we’ve “hit” all the elements. More precisely, any collection of orbits whose union is all of constitutes all the distinct orbits of . Moreover, if we find we need not check since, as a result that the orbits partition , that . So, we first compute

and thus we may conclude that

Thus, we notice that we need not check the orbits of we next check the orbit of .

so that

Next, we check the orbit of to get

so that once again

Lastly, we check the orbit of to arrive at

so that

Thus, induced the partition of up into the orbits .

We end this post by making one last observation that the orbit of under , , is really the minimal set such that is a bijection.

**References**

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

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

[…] 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, […]

Pingback by Permutations (Pt. III Orbits and Cycles cont.) « Abstract Nonsense | November 7, 2010 |