# Abstract Nonsense

## 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.

November 7, 2010 -