Abstract Nonsense

Crushing one theorem at a time

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

which is clearly a contradiction.

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<n. Is this factorization unique?

Proof: Let a_1<a_2\in[n]. 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<k<a_2-a_1+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

Advertisements

November 8, 2010 - Posted by | Fun Problems, Halmos, Linear Algebra, Uncategorized | , , , , ,

No comments yet.

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: