# Abstract Nonsense

## Halmos Section 26 and 27: Permutations and Cycles cont.

Point of post: This is a continuation of this post.

7.

Problem: Prove that the representation of a permutation $\pi$ as the product of disjoint cycles is unique up to reordering.

Proof: Notice that if

$\sigma_1\cdots\sigma_m=\pi=\sigma'_1\cdots\sigma'_k$

Then, if $\mathcal{O}_j$ is the non-trivial orbit of $\sigma_j$ and $\mathcal{O}'_{j}$ is the non-trivial orbit of $\sigma'_j$ then the above implies that $\left\{\mathcal{O}_1,\cdots,\mathcal{O}_m\right\}=\text{Orb}\left(\pi\right)=\left\{\mathcal{O}'_1,\cdots,\mathcal{O}_k'\right\}$ from where the conclusion follows.

This might have been a little bit too much abstract nonsense. So, let’s think of it this way. Suppose that

$(a_{1,1},\cdots,a_{1,m_1})\cdots(a_{r,1},\cdots,a_{r,m_r})=\pi=(b_{1,1},\cdots,b_{1,k_1})\cdots(b_{s,1},\cdots,b_{s,k_s}),\text{ }(1)$

with $r\leqslant s$. Now clearly we must have that $\displaystyle \bigcup_{j=1}^{r}\{a_{j,1},\cdots,a_{j,r_j}\}=\bigcup_{j=1}^{s}\{b_{j,1},\cdots,b_{j,k_j}\}$. So, for notice that $a_{1,1}\in\{b_{j_1,1},\cdots,b_{j_1,r_{j_1}}\}$ for some $j\in[s]$. It follows then that $\{a_{1,1},\cdots,a_{1,m_1}\}\cap\{b_{j_1,1},\cdots,b_{j_1,k_{j_1}}\}\ne\varnothing$ but since these are both orbits for $\pi$ it follows (since the orbits are equivalence classes) that $\{a_{1,1},\cdots,a_{1,m_1}\}=\{b_{j_1,1},\cdots,b_{j_1,k_{j_1}}\}$. So, it is then evident that $(a_{1,1},\cdots,a_{1,m_1})=(b_{j_1,1},\cdots,b_{j_1,k_{j_1}})$. Repeating this process for $a_{2,1},\cdots,a_{s,1}$ we  find $(b_{j_\ell,1},\cdots,b_{j_\ell,k_{j_{\ell}}}),\text{ }\ell=1,\cdots,r$ such that $(a_{\ell,1},\cdots,a_{\ell,m_\ell})=(b_{j_\ell,1},\cdots,b_{j_\ell,k_{j_{\ell}}})$. So, recalling that the cycles in both representations are disjoint we may arbitrarily rearrange and using 3. b) cancel them. Now, if $s>r$ so that there would still be a cycle  left we’d have that the identity permutation is represented as the product of disjoint cycles which, using the same methodology as 4., is impossible. Thus, the set of cycles represented on the left hand side of $(1)$ equals the set of cycles represented on the right hand side. But, this is precisely what we were to show.

8.

Problem: The order of a permutation $\pi$ is the least integer $p>0$ such that $\pi^p=\text{id}{[n]}$.

a) Every permutation has an order.

b) What is the order of a $p$-cycle?

c) IF $\sigma$ is a $p$-cycle, $\tau$ is a $q$-cycle, and $\sigma$ and $\tau$ are disjoint, what is the order of $\sigma\tau$?

Proof:

a) Consider $E\overset{\text{def.}}{=}\{\pi,\pi^2,\cdots,\pi^{n!},\pi^{n!+1}\}\subseteq S_n$. Then by the Pigeonhole Principle at least two elements of  $E$ must be equal. Thus, $\pi^r=\pi^s$ for some $1\leqslant r. It follows though by the cancellation property then that $\pi^{s-r}=\text{id}_{[n]}$. Thus, $K=\left\{n\in\mathbb{N}:\pi^n=\text{id}_{[n]}\right\}$ is non-empty, and by the well-ordering principle $K$ must have a least element, and this is the order of $\pi$.

b) The order of a $p-cycle$ is it’s length. To see this suppose that $\sigma\in S_n$ was a $p$-cycle $(x_1,\cdots,x_p)$. Recall that by definiton

$\displaystyle \sigma(x)=\begin{cases}x_{k+1\text{ mod }p} & \mbox{if}\quad x=x_k,\text{ }k=1,\cdots,p\\ x & \text{otherwise}\end{cases}$

Note then that

$\sigma^p(x)=\begin{cases}x_{k+p\text{ mod }p} & \mbox{if}\quad x=x_k\text{ }k=1,\cdots,p\\ x & \text{otherwise}\end{cases}$

from where it follows that $\sigma^p=\text{id}_{[n]}$. Now, if $1\leqslant q we note that

$\sigma^q(x_1)=x_{p+q+1\text{ mod }p}=x_{q+1}\ne x_1$

and thus $q$ is not the order of $\sigma$. It follows that $\text{ord}(\sigma)=p$ as desired.

e) So, by the division algorithm we have that $q=pn+r$ for some $0\leqslant r. But, then

$\text{id}_{[n]}=\pi^q=\pi^(pn+r)=\pi^{pn}\pi^r=\pi^r$

But, if $r>0$ then $p$ is not the least positive number for which $\pi^k=\text{id}_{[n]}$, but this contradicts the definition of $p$. Thus, $r=0$ and the conclusion follows.

c) We claim that $\text{ord}(\sigma,\tau)=\text{l.c.m}\left(\text{ord}(\sigma),\text{ord}(\tau)\right)$. To see this denote $\text{ord}(\sigma)$, $\text{ord}(\tau)$, $\text{ord}(\sigma\tau)$, and $\text{l.c.m}\left(\text{ord}(\sigma),\text{ord}(\tau)\right)$ by $a,b,c$, and $d$ respectively. Note first that indeed

$(\sigma\tau)^d=\sigma^d\tau^d=\text{id}_{[n]}\text{id}_{[n]}=\text{id}_{[n]}$

so that we see it’s true that $c\mid d$. Note though that

$\text{id}_{[n]}=(\sigma\tau)^c=\sigma^c\tau^c$

but this implies that

$\tau^c=\sigma^{-c}$

but by the disjointness of $\tau$ and $\sigma$ this will happen if and only if $\tau^c=\sigma^{-c}=\text{id}_{[n]}$. Thus, $c\mid a$ and $c\mid b$ and so by definition $c\mid d$. Thus, it follows that $c=d$.

c) This follows by taking a transposition $\tau$ and noticing that $\text{ord}(\tau)=2$ but $\text{ord}(\tau^2)=\text{ord}(\text{id}_{[n]})=1$

Remark: It can be shown in general using a similar methodology to that used in part e) that if $\pi$ is the product of transpositions that $\pi$‘s order is the $\text{l.c.m.}$ of the cylcles’ orders.

9.

Problem: Every permutation in $S_n$ can be written as a product , each factor of  which is one of the transpositions $(1,2),\cdots,(1,n)$

Proof: We proceed by induction. This is trivially true for $n=2$. Suppose then that it’s true for $n=m$. Note then that if $\pi\in S_{m+1}$ and $\pi(m+1)=k$ that $\pi(1,m)(1,n)$ fixes $n$ and so by the induction hypothesis may be written as the product of the desired transpositions. But, if $\pi(1,m)(1,n)$ can be written as the product of the desired transpositions then so can $\pi$. The conclusion follows.

References:

1. Halmos, Paul R. “Bilinear Forms.” Finite-dimensional Vector Spaces,. New York: Springer-Verlag, 1974. Print