## 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 as the product of disjoint cycles is unique up to reordering.

**Proof: **Notice that if

Then, if is the non-trivial orbit of and is the non-trivial orbit of then the above implies that 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

with . Now clearly we must have that . So, for notice that for some . It follows then that but since these are both orbits for it follows (since the orbits are equivalence classes) that . So, it is then evident that . Repeating this process for we find such that . So, recalling that the cycles in both representations are disjoint we may arbitrarily rearrange and using **3. b) **cancel them. Now, if 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 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 is the least integer such that .

**a) **Every permutation has an order.

**b) **What is the order of a -cycle?

**c) **IF is a -cycle, is a -cycle, and and are disjoint, what is the order of ?

**Proof:**

**a) **Consider . Then by the Pigeonhole Principle at least two elements of must be equal. Thus, for some . It follows though by the cancellation property then that . Thus, is non-empty, and by the well-ordering principle must have a least element, and this is the order of .

**b) **The order of a is it’s length. To see this suppose that was a -cycle . Recall that by definiton

Note then that

from where it follows that . Now, if we note that

and thus is not the order of . It follows that as desired.

**e) **So, by the division algorithm we have that for some . But, then

But, if then is not the least positive number for which , but this contradicts the definition of . Thus, and the conclusion follows.

**c) **We claim that . To see this denote , , , and by , and respectively. Note first that indeed

so that we see it’s true that . Note though that

but this implies that

but by the disjointness of and this will happen if and only if . Thus, and and so by definition . Thus, it follows that .

**c) **This follows by taking a transposition and noticing that but

*Remark: *It can be shown in general using a similar methodology to that used in part **e) **that if is the product of transpositions that ‘s order is the of the cylcles’ orders.

9.

**Problem: **Every permutation in can be written as a product , each factor of which is one of the transpositions

**Proof: **We proceed by induction. This is trivially true for . Suppose then that it’s true for . Note then that if and that fixes and so by the induction hypothesis may be written as the product of the desired transpositions. But, if can be written as the product of the desired transpositions then so can . The conclusion follows.

**References:**

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

No comments yet.

## Leave a Reply