Halmos Section 26 and 27: Permutations and Cycles cont.
Point of post: This is a continuation of this post.
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.
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 ?
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.
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.
1. Halmos, Paul R. “Bilinear Forms.” Finite-dimensional Vector Spaces,. New York: Springer-Verlag, 1974. Print
No comments yet.