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. We proved the ‘existence’ part of this last time. 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, 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 proved (i) by noting that since any permutation can be written as a product of disjoint cycles, it suffices to show that any cycle can be written as a product of transpositions. And we have . For (ii), we showed that if can be written as a product of transpositions, then .
- Definition of the alternating group .
Some comments following questions you asked me after the lecture.
- Theorem 15 doesn’t claim that the number of transpositions is well defined, just the parity of the number of transpositions. If I can write a permutation as a product of 6 transpositions, then I may well be able to write it as a product of 8 transpositions (in fact, I can: write it as those six transpositions followed by ). But I’ll never be able to write it as a product of 7 transpositions, or 101.
- We used determinants of permutation matrices to prove Theorem 15(ii), and 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.
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.
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.
Preparation for Lecture 5
Can you show that the alternating group really is a group?
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?