In which we explore permutations in more detail.
- Theorem 9: Every permutation can be written as a product of disjoint cycles. Moreover, this is unique up to cycling elements within cycles and permuting the order of the cycles. To check existence (of decomposition as a product of disjoint cycles), we considered the orbit of some , which is permuted via a cycle, and then considered orbits of new elements until there were none left. Note that the process is guaranteed to terminate because we have only finitely many elements to consider so at some point the disjoint cycles will use them all up. To check uniqueness, we took two equal products of disjoint cycles and showed that in fact they are the same (up to shuffling cycles and cycling cycles), by considering what they to do and then to other elements.
- Definition of the cycle type of a permutation.
- Proposition 10: Let be written as as a product of disjoint cycles. For , let have length . Then the order of is . The proof is a good exercise.
- Definition of what it means for two permutations to be conjugate.
- Lemma 11: Let be a cycle, and take . Then . This is an exercise on Sheet 2.
- Theorem 12: Let , be permutations in . They are conjugate if and only if they have the same cycle type. To show that if they’re conjugate then they have the same cycle type, we wrote as a product of disjoint cycles, then noted that conjugating each of them yields a cycle of the same length (by Lemma 11), so must have the same cycle type as . For the other direction, we wrote and as products of disjoint cycles with the same cycle type, and then we were able to use Lemma 11 to write down an explicit permutation so that conjugating by it gives .
- Definition of a permutation matrix (a square matrix in which each row and each column contains exactly one entry that is 1, with all other entries 0), and of the permutation matrix corresponding to a permutation .
- Lemma 13: If , , then . We proved this by using our previous observation that for a permutation , we have .
- Lemma 14: If is a transposition, then . If , then is the identity matrix with two rows swapped, so is times the determinant of the identity matrix, so is .
- Theorem 15: (i) Any permutation can be written as a product of transpositions. (ii) A permutation cannot be both even and odd. We’ll prove this next time.
Understanding today’s lecture
Practise writing permutations as products of disjoint cycles, this is a really important thing to be able to do! Can you then find the inverses of those permutations?
Can you prove Proposition 10? (Remember that you can leave a comment below if you have any queries.)
It would definitely be worth thinking about the link between our work here on permutation matrices and your previous work on determinants — this will act as good revision of part of the Linear Algebra II course, as well as helping you to understand the new material in this course. We used determinants of permutation matrices to prove Lemma 14, and we’ll use them for Theorem 15(ii). In the Linear Algebra II course you used transpositions to think about determinants, so do we have a circular argument? Happily no: we didn’t use determinants to prove Theorem 15 (i), so we know that any permutation can be written as a product of transpositions, and that was the property you used to study determinants in the Linear Algebra course. Along the way, you noted something equivalent to Theorem 15 (ii), when you discussed the sign of a permutation. Phew.
Don’t forget that Richard Earl’s online notes have lots of worked examples and other little comments that are well worth looking at. One good approach would be to try to do the worked examples for yourself, and then check your answers with his.
Some of you might be interested in the book Visual Group Theory, by Nathan Carter, which covers (at least most if not all of) the content of this course, from a rather different perspective — experience suggests that some students find his approach very helpful.
There’s a Wikipedia page that discusses ideas relating to Theorem 15. Of course, there are lots of group theory books out there that go into this too.
How much do you know about the group theorist Hanna Neumann?
Preparation for Lecture 5
Can you prove Theorem 15?
What can you say about the cycle type of an even permutation?
In Linear Algebra I, you had the ‘subspace test’, which streamlined the process of checking whether a subset of a vector space is a subspace. What might a ‘subgroup test’ look like?
If I give you a group and an element , is there a subgroup that contains ?
Is a subgroup of a cyclic group also itself a cyclic group?