Abstract Nonsense

Crushing one theorem at a time

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 [n] induced by a permutation \pi. 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 \pi\in S_{8} given by

\begin{array}{c|c} x & \pi(x)\\ \hline 1 & 2\\ 2 & 3\\ 3 & 5\\ 4 & 4\\ 5 & 1\\ 6 & 6\\ 7 & 8\\ 8 &7\end{array}

having to write this table (i.e. write out in essence \pi(1)=?,\cdots,\pi(8)=?) is a pain. The standard convention is to write

\pi=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 2 & 3 & 5 & 4 & 1 & 6 & 7 & 8\end{pmatrix}

Thus, in general for \pi \in S_n we may represent it as

\pi=\begin{pmatrix} 1 &\cdots &n\\ \pi(1) & \cdots & \pi(n)\end{pmatrix}

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

\pi\pi'=\begin{pmatrix} 1 & \cdots &n\\ \pi(1) & \cdots & \pi(n)\end{pmatrix}\begin{pmatrix}1 & \cdots & n\\ \pi'(1) & \cdots & \pi'(n)\end{pmatrix}=\begin{pmatrix} 1 & \cdots &n\\ \pi(\pi'(1)) & \cdots & \pi(\pi'(n))\end{pmatrix}

Lastly, for \pi\in S_n we define \pi^n=\underbrace{\pi\circ\cdots\circ\pi}_{n\text{ times}}, \pi^0=\text{id}_{[n]}, and \pi^{-n}=\left(\pi^n\right)^{-1}. From this it’s not hard to see that

\pi^m\circ\pi^n=\pi^{m+n}

and

\left(\pi^m\right)^n=\pi^{mn}

 

Orbits

In this spirit of this post we can recall that if \pi\in S_n then

x\overset{\pi}{\longmapsto}\pi(x)\overset{\pi}{\longmapsto}\pi^2(x)\overset{\pi}{\longmapsto}\pi^3(x)\cdots

eventually must start to repeat, in the sense that \pi^{m}(x)=\pi^{n}(x) for some m\leqslant n. But, this clearly implies by injectivity that \pi^{n-m}(x)=x. Intuitively this is the orbit of x under \pi, namely

\mathcal{O}_\pi(x)=\left\{\pi^n(x):n\in\mathbb{Z}\right\}

It turns out then that, in a sense we shall technically define in a second, these orbits partition [n] 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 \pi\in S_n, defining  a relation R on [n] by

x\overset{\pi}{\sim} y\Leftrightarrow x=\pi^n(y)\text{ for some }n\in\mathbb{Z}

Theorem: The relation \overset{\pi}{\sim} is an equivalence relation.

Proof: Clearly \overset{\pi}{\sim} is reflexive since x=\pi^0(x). To see that \overset{\pi}{\sim} is symmetric we note that if x\overset{\pi}{\sim} y then x=\pi^n(y) for some n\in\mathbb{Z} and so \pi^{-n}(x)=y and thus y\overset{\pi}{\sim} x. Lastly, we note that if x\overset{\pi}{\sim} y and y\overset{\pi}{\sim} z that x=\pi^n(y) and y=\pi^m(z) for some n,m\in\mathbb{Z} and thus

x=\pi^n(y)=\pi^n\left(\pi^m\left(z\right)\right)=\pi^{n+m}(z)

and thus x\overset{\pi}{\sim} y. \blacksquare

Now, it’s clear that the equivalence class of some x  under \overset{\pi}{\sim} are the same as the orbit of x under \pi. Thus, we now define the orbit of x under \pi\in S_n as

\mathcal{O}_\pi(x)=\left\{y\in[n]:x\overset{\pi}{\sim}y\right\}

The set of all orbits under \pi is denoted \text{Orb }(\pi). Let’s, for the sake of clarity, give an example. Namely, let’s take \pi\in S_8 as listed above and write out the cycles. To do this we fix x_0\in [8] and consider 8,\pi(8),\pi^2(8),\cdots until we start repeating and then this set of non-repeats will form the orbit of 8 under \pi. And, since these orbits partition [8] we’ll know we’re done once we’ve “hit” all the elements. More precisely, any collection of orbits whose union is all of [8] constitutes all the distinct orbits of \pi. Moreover, if we find y\in\mathcal{O}_\pi(x) we need not check \mathcal{O}_\pi(y) since, as a result that the orbits partition [8], that \mathcal{O}_\pi(x)=\mathcal{O}_\pi(y). So, we first compute \mathcal{O}_\pi(1)

1\overset{\pi}{\longmapsto}2\overset{\pi}{\longmapsto}3\overset{\pi}{\longmapsto}5\overset{\pi}{\longmapsto}1

and thus we may conclude that

\mathcal{O}_{\pi}(1)=\left\{1,2,3,5\right\}

Thus, we notice that we need not check the orbits of 2,3,5 we next check the orbit of 4.

4\overset{\pi}{\longmapsto}4

so that

\mathcal{O}_{\pi}\left(4\right)=\{4\}

Next, we check the orbit of 6 to get

6\overset{\pi}{\longmapsto}6

so that once again

\mathcal{O}_{\pi}(6)=\{6\}

Lastly, we check the orbit of 7 to arrive at

7\overset{\pi}{\longmapsto}8\overset{\pi}{\longmapsto}7

so that

\mathcal{O}_{\pi}(7)=\{7,8\}

Thus, \pi induced the partition of [8] up into the orbits \left\{\{1,2,3,5\},\{4\},\{6\},\{7,8\}\right\}.

We end this post by making one last observation that the orbit of x under \pi, \mathcal{O}_{\pi}(x), is really the minimal set \{x\}\subseteq E\subseteq[n] such that \pi\mid_E:E\to\pi\left(E\right) 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.

Advertisements

November 6, 2010 - Posted by | Algebra, Halmos, Linear Algebra, Uncategorized | , , , ,

1 Comment »

  1. […] 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 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: