# Abstract Nonsense

## Halmos Section 26 and 27: Permutations and Cycles

Point of post: In this post we’ll complete the problems in chapters 26 and 27 of Halmos’s book.

1.

Problem:

a) How many permutations are there in $S_n$?

b) How many distinct $p$-cycles are there in $S_n$?

Proof:

a) This was covered in this post. Less rigorously, let $\pi\in S_n$. Then, there are precisely $n$ choices for $\pi(1)$, and thus after that has been designated there are precisely $n-1$ choices for $\pi(2)$, etc. Thus, there are precisely $n(n-1)\cdots1=n!$ choices for $\pi$.

b) This is a little less obvious. Clearly if $p=1$ the only $p$-cell is $\text{id}_{[n]}$, so assume that $p>1$. So, let us fix $\{x_1,\cdots,x_p\}\subseteq [n]$ and try to figure out how many distinct $p$-cycles there are of the form $(a_1,\cdots,a_p)$ with $\{a_1,\cdots,a_p\}=\{x_1,\cdots,x_p\}$.

Let us define an equivalence relation on $S_p$ by

$\pi(x)\sim \pi'(x)\Leftrightarrow \exists k\in\{0,\cdots,n-1\}\text{ such that }\pi(x)=\pi'(x+k\text{ mod }p)$

To see that this is an equivalence relation, we note that it’s a) reflexive since $\pi(x)=\pi(x+0\text{ mod }p)$, b) symmetric since if $\pi(x)=\pi'(x+k\text{ mod }p)$ then $\pi'(x)=\pi(x+(p-k)\text{ mod }p)$ and c) transitive since $\pi_1(x)=\pi_2(x+k_1\text{ mod }p)$ and $\pi_2(x)=\pi_3(x+k_2\text{ mod }p)$ implies that $\pi_1(x)=\pi_3(x+\left((k_1+k_2)\text{ mod } p\right)\text{ mod }p)$.

So, what is the cardinality of $[\pi]$? Well, it contains precisely $\pi(x),\pi(x+1\text{ mod }p),\cdots,\pi(x+p-1\text{ mod }p)$ so that for any $\pi\in S_p$ we have that $\text{card }[\pi]=p$. Thus, since these equivalence classes partition $S_p$ into blocks of cardinality $p$, it follows that there must be $(p-1)!$ blocks. So, let $C$ the set of all $p$-cycles consisting of $\{x_1,\cdots,x_p\}$ and $P$ the partition of $S_p$ into the equivalence classes induced by $\sim$.

Define $f:C\to D$ by $f:(x_{k_1},\cdots,x_{k_p})\mapsto[\pi]$ where $\pi(j)=k_j$. Evidently this is a surjection, and so it remains to show that this is an injection. So, suppose that $f\left((x_{k_1},\cdots,x_{k_p})\right)=f\left((x_{k'_1},\cdots,x_{k'_p})\right)$ Then, we know that the induced $\pi,\pi'$ given by the two tuples are equivalent. Thus, $\pi(x)=\pi(x+m\text{ mod }p)$. But, by definition this means that

$(x_{k'_1},\cdots,x_{k'_p})=(x_{k_m},\cdots,x_{k_p},x_{k_1},\cdots,x_{k_{m-1}})$

but by the definition of cycles we may “shift” the tuples $m$ positions to the right without changing the identity of the tuple, thus

$(x_{k'_1},\cdots,x_{k'_p})=(x_{k_m},\cdots,x_{k_p},x_{k_1},\cdots,x_{k_{m-1}})=(x_{k_1},\cdots,x_{k_p})$

and thus injectivity of $f$ follows. Therefore, $f$ is a bijection and so $\text{card }C=(p-1)!$. Therefore, considering there are $\displaystyle n\choose p$ ways of selecting $x_1,\cdots,x_p$ from $[n]$ we may conclude that the number of $p$ cycles in $S_n$ is

$\displaystyle {n\choose p}(p-1)!=\frac{n!}{(n-p)!p}$

2.

Problem: If $\sigma$ and $\tau$ are permutations in $S_n$, then $(\sigma\tau)^{-1}=\tau^{-1}\sigma^{-1}$.

Proof: We know that $S_n$ is a group and so it suffices, by the uniqueness of inverses, to show that $(\sigma\tau)(\tau^{-1}\sigma^{-1})=(\tau^{-1}\sigma^{-1})(\sigma\tau)=\text{id}_{[n]}$. But this is trivial since

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

and

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

3.

Problem:

a) If $\sigma,\tau\in S_n$ then there exists a unique permutation $\pi$ such that $\sigma\pi=\tau$.

b) If $\pi,\sigma$ and $\tau$ are permutations such that $\pi\sigma=\pi\tau$ then $\sigma=\tau$.

Proof:

a) Uniqueness is clear since $\pi,\pi'$ were such that $\sigma\pi=\tau=\sigma\pi'$ then by b) $\pi=\pi'$. Thus, noticing that $\sigma(\sigma^{-1}\tau)=\tau$ it follows that $\pi=\sigma^{-1}\tau$.

b) Notice that

$\pi\sigma=\pi\tau\implies \pi^{-1}(\pi\sigma)=\pi^{-1}(\pi\tau)\implies\text{id}_{[n]}\sigma=\sigma=\tau=\text{id}_{[n]}\tau$

Remark: These are just virtues of the fact that $S_n$ is a group.

4.

Problem: Give an example of a permutation that is not the product of disjoint transpositions.

Proof: Consider $\text{id}_{[n]}$. Suppose that $\text{id}_{[n]}=(a_1,a_2)\cdots(a_{m-1},a_{m})$ where $\{a_{k},a_{k+1}\}\cap \{a_{\ell},a_{\ell+1}\}=\varnothing$ for $\ell\ne k$. Then,

$\text{id}_{[n]}(a_1)=\left((a_1,a_2)\cdots(a_{m-1},a_m)\right)(a_1)=((a_1,a_2))(a_1)=a_2\ne a_1$

5.

Problem: Prove that every permutation in $S_n$ is the product of a transpositions of the form $(j,j+1)$ where $1\leqslant j. Is this factorization unique?

Proof: Let $a_1. We claim that

$(a_2,a_2-1)\cdots(a_1+2,a_1+1)(a_1,a_1+1)(a_1+1,a_1+2)\cdots(a_2-1,a_2)=(a_1,a_2)\quad\quad\quad(1)$

Indeed if $x\ne a_1,a_1+1,\cdots,a_2-1,a+2$ they are clearly equal. So, note that if one plugs in $a_1$ it will be “ignored” until it gets to $(a_1,a_1+1)$ in which case it will be mapped to $a_1+1$. From there each of the transpositions will increase it by one until finally we get to $(a_2,a_2-1)$ which then map it to $a_2$ as required. Similarly we see that if one plugs in $a_2$ the first $a_2-a-1-1$ transpositions will decrease $a_2$ by one until it gets to $(a_1,a_1+1)$ at which point it will be $a_2-(a_2-a_1-1)=a_1+1$ and so this transposition will change it to $a_1$ and from there on out it will be “ignored” and thus $a_2$ is mapped to $a_1$. Now suppose we plugged in $a_1+k$ for some $1 we see that it will left fixed by all the cycles until $(a_k,a_k+1)$ at which point it will be changed to $a_k+1$ from where it will be left fixed all the way until it reaches $(a_k+1,a_k)$ where it will be mapped to $a_k$ and after that point it will be left fixed again and thus it will, in total, be mapped to $a_k$. From where equation $(1)$ follows.

So, every transposition may be written as the product of transpositions of the form $(j,j+1)$ and since every permutation may be written as the product of transpositions it follows that every permutation may be written as the product of transpositions of the form $(j,j+1)$.  And no, the representation is not unique since $\text{id}_{[n]}=(1,2)(1,2)$.

6.

Problem: Is the inverse of a cycle a cycle?

Proof: Yes. To prove this let’s just think back to the definition of a cycle. If $\sigma\in S_n$ is non-trivial with non-trivial orbit $\mathcal{O}$ then we know that for $x\notin\mathcal{O}$ that $\sigma(x)=x$ so that $\sigma^{-1}(x)=x$.  So, in particular we know that in particular for $x\notin\mathcal{O}$ we have that $\mathcal{O}_{\pi^{-1}}(x)=\mathcal{O}_{\pi}(x)=\{x\}$. To finish off the problem we know note that if $\mathcal{O}=\{a_1,\cdots,a_m\}$ where

$a_1\overset{\pi}{\longmapsto}a_2\overset{\pi}{\longmapsto}\cdots\overset{\pi}{\longmapsto}a_n\overset{\pi}{\longmapsto}a_1$

so that

$a_n\overset{\pi^{-1}}{\longmapsto}\cdots\overset{\pi^{-1}}{\longmapsto}a_2\overset{\pi^{-1}}{\longmapsto}a_1\overset{\pi^{-1}}{\longmapsto}a_n$

from where it follows that $\text{Orb}(\pi)=\text{Orb}\left(\pi^{-1}\right)$ and thus if $\pi$ is a cycle so is $\pi^{-1}$. Moreover, the above shows that

$\pi=(a_1,\cdots,a_n)\implies \pi^{-1}=(a_n,\cdots,a_1)$.

Remark: Note that the above shows something fairly interesting. Note that the above says that $(a_1,\cdots,a_n)^{-1}=(a_n,\cdots,a_1)=(a_1,a_n,\cdots,a_2)$ and if $n>2$ then $(a_1,a_n,\cdots,a_2)\ne(a_1,a_2,\cdot,a_n)$ so that $(a_1,\cdots,a_n)^{-1}=(a_1,\cdots,a_n)$ if and only if $n=2$. In other words, a cycle is it’s own inverse if and only if it’s a transposition.

References:

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