in which we prove that disjoint cycle notation works and get a first glimpse of the sign of a permutation.
We started the lecture by proving that disjoint cycle notation works: every permutation can be written (essentially uniquely) as a product of disjoint cycles. Here are the main ideas of the proof: we want to establish the cycle which starts with and use the fact that the permutation is a bijection to show that we indeed get a finite cycle. Then we similarly establish the next cycle and so on. These cycles are disjoint, again because is a bijection. Essential uniqueness comes from being a function, which implies that the first number in each cycle completely determines the whole cycle. This result gives us the cycle type of a permutation, a very useful bit of information, as we started to see in “order by cycle type”: the order of a permutation is the least common multiple of the cycle lengths in disjoint cycle notation.
To learn a lot more about the symmetric group, we then wanted to introduce the sign of a permutation. For this we first need to know that is generated by transpositions (that is, -cycles). But to make any use of such products (this facorisation is almost not unique at all, to quote my own lecturer), we then had to prove that no matter how we write a permutation as a product of transpositions, we get, for a specific permutation, either always an even number or an odd number of transpositions. (So that is the only degree to which it is unique 🙂 .) The main idea of this proof is to start with something which is completely determined by a permutation, namely the number of disjoint cycles. Then we show that the parity of this number changes when the permutation is multiplied by a transposition. This means that when we make a given permutation out of a product of transpositions, the parity of this number of disjoint cycles changes each time we add a new transposition. But the end result is fixed, so we conclude that the parity of transpositions needed is also fixed. We used this result to define the sign of a permutation: , where is the number of transpositions we need to get . The previous result ensures that sign is well-defined.
Understanding today’s lecture
To get used to the “almost not unique at all” part of products of transpositions, take some permutation, perhaps a cycle or so, and see how many ways you can find to write it as a product of transpositions.
To get some intuition for the “almost not unique at all” vs “parity is fixed”, I’ve tried to come up with some sort of analogy. It’s not the best of analogies, but let’s try it anyway. Take integers, which we know we can factor into prime factors. But if we say we want to factor into positive or negative prime factors, then the “distribution of the minus signs” is “almost not unique at all”. The only thing that has to be fixed is that if you are factoring a positive integer, overall you have an even number of minus signs, and if you’re factoring a negative integer, overall you have an odd number of minus signs.
Preparing for Lecture 8
Next time we are going to prove that this sign is a homomorphism. Can you think of any nice properties it will have? You could compare it with the “positive and negative” property of (real) numbers to get some ideas. You can also think about whether you can find a nice “rule” of determining whether a given permutation is even or odd.
Going a little deeper
Can you think of any other situations where we have a choice of writing something, but there is some invariant of the choice? Invariant means something that is the same for each choice you make. Some easy examples to start you thinking: If I have a chessboard, I can cover it with domino tiles (which are of a size that exactly covers two chess squares). Now, if I take out one of the corners, then I clearly can’t completely cover it with domino tiles any more, because we’ve now got an odd number of chess squares. The invariant here would be: chessboards which can be covered have an even number of squares. However, perhaps you can find an even nicer invariant: What if we delete two opposite corners? Can it be covered now? It has an even number of squares, but is that enough? I’ll let you think about that on. (I suppose it is really more “Numbers and Sets”y than “Groups”y.)
Or maybe you can come up with a better analogy than my “minus signs in prime factorisation”? I would be interested to hear.