In which we start to explore permutations.
- Definition of a subgroup of a group.
- Definition of the order of an element of a group, and of what it means for an element of a group to have infinite order.
- Definition of an isomorphism between two groups, and of what it means for two groups to be isomorphic.
- Definition of a permutation, and of the set for a set . We noted that in this course we shall write permutations on the right.
- Theorem 7: Let be a set.
- is a group under composition, called the symmetry group of .
- If , then is non-Abelian.
- We have .
The first part was a standard check. We showed that the group is non-Abelian by explicitly exhibiting two permutations in that do not commute. To count permutations, we considered the number of possibilities for where each of , , …, is sent.
- Definitions of a cycle and a -cycle and the length of a cycle and a transposition.
- Definition of what it means for two cycles to be disjoint.
- Proposition 8: Let and be disjoint cycles. Then and commute. We checked this by working out where each number is sent to by and .
- 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. (We’ll prove the uniqueness part in the next lecture.)
Understanding today’s lecture
I suggest that you pick an explicit example of a permutation, and use the (existence part of the) proof of Theorem 9 to write your chosen permutation as a product of disjoint cycles. This is an excellent way to develop your understanding of the proof (and you need to be able to decompose permutations in this way anyway). Can you prove the uniqueness part for yourself (before we do it in the lecture on Friday)?
There are lots of interesting points in this blog post by Tim Gowers — but do be careful, he writes permutations on the left, whereas we write permutations on the right.
Preparation for Lecture 4
If I give you a permutation written as a product of disjoint cycles, how can you work out its order? What information do you need?
We’ll use the first part of Sheet 2 Q3 to help us prove a result, so you might find it helpful to have looked at that particular question before the lecture.
We’ll think a bit about permutation matrices, which you touched on briefly in the Linear Algebra II course (when you thought about determinants) — it would be worth reviewing that part of the Linear Algebra course before the lecture.
Pick any cycle (of any length). Can you write it as a product of transpositions?