Abstract Nonsense

Crushing one theorem at a time

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.

\text{ }

Motivation

Recall from the last post that for any \pi\in S_n we have that [n] can be partitioned into orbits \left\{\mathcal{O}_1,\cdots,\mathcal{O}_m\right\}. Notice though that each of these orbits induces an element of S_n namely each \mathcal{O}_k induces \pi_k\in S_n given by

\text{ }

\pi_k(x)=\begin{cases}\pi(x) & \mbox{if}\quad x\in\mathcal{O}_k\\ x & \mbox{if}\quad x\notin\mathcal{O}_k\end{cases}

\text{ }

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 \sigma\in S_n a cycle if at most of the orbits induced by \sigma has cardinality greater than one. For example \sigma\in S_7 given by

\text{ }

\sigma=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7\\2 & 3 & 5 & 4 & 1 & 6 & 7\end{pmatrix}\quad(1)

\text{ }

is a cycle since \text{Orb}(\pi)=\left\{\{1,2,3,5\},\{4\},\{6\},\{7\}\right\} and only one of these has cardinality greater than one. Evidently cycles, in general, take a relatively simple form.

\text{ }

For a cycle writing the entire representation, as in (1), is superfluous. Instead we may write a cycle \sigma\in S_n as

\text{ }

\sigma=(a_1,a_2\cdots,a_m)

\text{ }

which is to be understood as meaning

\text{ }

a_1\overset{\sigma}{\longmapsto}a_2\overset{\sigma}{\longmapsto}\cdots\overset{\sigma}{\longmapsto} a_m\overset{\sigma}{\longmapsto}a_1

\text{ }

and \sigma(x)=x,\text{ }x\ne a_1,\cdots,a_m. Or, said differently

\text{ }

\sigma(x)=\begin{cases}a_{k+1\text{ mod }m} & \mbox{if} \quad x=a_k\text{ }k\in\{1,\cdots,m\}\\ x & \text{otherwise}\end{cases}

\text{ }

It’s obvious from this definition that

\text{ }

(a_1,a_2,a_3,\cdots,a_m)=(a_2,\cdots,a_m,a_1)=(a_3,\cdots,a_m,a_1,a_2)=\cdots

\text{ }

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

\text{ }

\sigma=(1,2,3,5)=(2,3,5,1)=(3,5,1,2)=(5,1,2,3)

 \text{ }

Remark: Note that it is impossible to tell given (a_1,\cdots,a_m) for which S_n we intend to view as (a_1,\cdots,a_m) as being a cycle in.

We say that a cycle (a_1,\cdots,a_m)\in S_n has length m. And we say that two cycles (a_1,\cdots,a_m),(b_1,\cdots,b_k)\in S_n are disjoint if \{a_1,\cdots,a_m\}\cap\{b_1,\cdots,b_k\}=\varnothing. With these definitions we are able to state and prove our first theorem

Theorem: Let \sigma_1,\sigma_2,\cdots,\sigma_k\in S_n,\text{ }k\geqslant 2 be disjoint cycles. Then,

\text{ }

\sigma_1\sigma_2\cdots\sigma_k=\sigma_2\cdots\sigma_k\sigma_1

\text{ }

Proof: To prove the case when k=2 it suffices to show that \sigma_1(\sigma_2(x))=\sigma_2(\sigma_1(x)) for all x\in[n]. So, by assumption we have that \sigma_1=(a_1,\cdots,a_{m_1}) and \sigma_2=(b_1,\cdots,b_{m_2}) where \{a_1,\cdots,a_{m_1}\}\cap\{b_1,\cdots,b_{m_2}\}=\varnothing. So, if x=a_k for some k we see that

\text{ }

\sigma_1(\sigma_2(a_k))=\sigma_1(a_k)=\sigma_2(\sigma_1(a_k))

\text{ }

if x=b_k for some k then

\text{ }

\sigma_1(\sigma_2(b_k))=\sigma_2(b_k)=\sigma_2(\sigma_1(b_k))

\text{ }

If x\notin\{a_1,\cdots,a_{m_1}\}\cup\{b_1,\cdots,b_{m_2}\} then

\text{ }

\sigma_1(\sigma_2(x))=\sigma_1(x)=x=\sigma_2(x)=\sigma_2(\sigma_1(x))

\text{ }

and since all x\in[n] are of one of these three forms, it follows that \sigma_1(\sigma_2(x))=\sigma_2(\sigma_1(x)) for all x, and thus \sigma_1\sigma_2=\sigma_2\sigma_1.

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

\text{ }

\sigma_1\sigma_2\cdots\sigma_{k+1}=\sigma_2\sigma_1\cdots\sigma_{k+1}=\sigma_2\cdots\sigma_{k+1}\sigma_1

\text{ }

where the last step is via the induction hypothesis since \text{card }\left(\{1,\cdots,k+1\}-\{2\}\right)=k. The conclusion follows. \blacksquare

Corollary: Using this and some real mathematical elbow grease one can show that if \sigma_1,\cdots,\sigma_k\in S_n are disjoint cycles and \pi\in S_k then

\text{ }

\sigma_1\cdots\sigma_k=\sigma_{\pi(1)}\cdots\sigma_{\pi(k)}

\text{ }

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

Theorem: Let \pi\in S_n, then \pi may be written as the disjoint product of cycles.

Proof: Let \text{Orb}(\pi)=\left\{\mathcal{O}_1,\cdots,\mathcal{O}_k\right\}. Let\pi_k is given by

\text{ }

\displaystyle \pi_k(x)=\begin{cases}\pi(x) & \mbox{if}\quad x\in\mathcal{O}_k\\ x & \mbox{if}\quad x\notin\mathcal{O}_k\end{cases}

\text{ }

we claim that \pi=\pi_1\cdots\pi_k. To see this x\in[n] be arbitrary. Then, x\in\mathcal{O}_m for some m\in\{1,\cdots,k\}. Then, recalling that by definition \pi_\ell(x)=x for all \ell\ne m, \pi_m(x)=\pi(x), and \pi(x)\in\mathcal{O}_m we see that

\text{ }

\pi_1(\cdots(\pi_k(x))\cdots)=\pi_1(\cdots(\pi_m(x))\cdots)=\pi_1(\cdots(\pi(x))\cdots)=\pi(x)

\text{ }

and since x\in[n] was arbitrary it follows that \pi=\pi_1\cdots\pi_k. Thus, noting that each \pi_m is a cycle, since \text{Orb}(\pi_m)=\left\{\mathcal{O}_m\right\}\cup\left\{\{x\}:x\notin\mathcal{O}_m\right\} and that they are disjoint since \mathcal{O}_p\cap\mathcal{O}_q=\varnothing\text{ }p\ne q. The conclusion follows. \blacksquare

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

\text{ }

\text{ }

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.

Advertisements

November 7, 2010 - Posted by | Algebra, Group Theory | , , ,

3 Comments »

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

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

  3. […] 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 | 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: