Abstract Nonsense

Crushing one theorem at a time

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<s\leqslant n!+1. 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<p 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<p. 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

Advertisements

November 10, 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: