## 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 ?

**b) **How many distinct -cycles are there in ?

**Proof:**

**a) **This was covered in this post. Less rigorously, let . Then, there are precisely choices for , and thus after that has been designated there are precisely choices for , etc. Thus, there are precisely choices for .

**b) **This is a little less obvious. Clearly if the only -cell is , so assume that . So, let us fix and try to figure out how many distinct -cycles there are of the form with .

Let us define an equivalence relation on by

To see that this is an equivalence relation, we note that it’s a) reflexive since , b) symmetric since if then and c) transitive since and implies that .

So, what is the cardinality of ? Well, it contains precisely so that for any we have that . Thus, since these equivalence classes partition into blocks of cardinality , it follows that there must be blocks. So, let the set of all -cycles consisting of and the partition of into the equivalence classes induced by .

Define by where . Evidently this is a surjection, and so it remains to show that this is an injection. So, suppose that Then, we know that the induced given by the two tuples are equivalent. Thus, . But, by definition this means that

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

and thus injectivity of follows. Therefore, is a bijection and so . Therefore, considering there are ways of selecting from we may conclude that the number of cycles in is

2.

**Problem: **If and are permutations in , then .

**Proof: ** We know that is a group and so it suffices, by the uniqueness of inverses, to show that . But this is trivial since

and

3.

**Problem:**

**a) **If then there exists a unique permutation such that .

**b) **If and are permutations such that then .

**Proof:**

**a) **Uniqueness is clear since were such that then by **b) **. Thus, noticing that it follows that .

**b) **Notice that

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

4.

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

**Proof: **Consider . Suppose that where for . Then,

which is clearly a contradiction.

5.

**Problem: **Prove that every permutation in is the product of a transpositions of the form where . Is this factorization unique?

**Proof: ** Let . We claim that

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

So, every transposition may be written as the product of transpositions of the form 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 . And no, the representation is not unique since .

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 is non-trivial with non-trivial orbit then we know that for that so that . So, in particular we know that in particular for we have that . To finish off the problem we know note that if where

so that

from where it follows that and thus if is a cycle so is . Moreover, the above shows that

.

*Remark: *Note that the above shows something fairly interesting. Note that the above says that and if then so that if and only if . 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

No comments yet.

## Leave a Reply