I can't think of a witty title for permutations
part 3 of abstract algebra (toc)
As abstract algebra whizzes by, I feel like I'm learning a whole bunch of stuff. So much stuff I don't even know where to begin with resuming posts on the topic. The last time I wrote something, I finished off subgroups and groups. Where do we go now?
Let's mix it up. (harharhar.)
Well, we looked at some groups so far. Specifically, we've seen the reals under addition, integers under addition, integers under modular arithmetic... it's all abelian! Here, we dive into the first big/important nonabelian group: the group of permutations on n letters. Not too sure why it's on letters...what's wrong with balls or stars or hats? Well, a rose by any other name...so let's get to it.
A permutation on n letters is just a rearrangment of n items. Semantically, it's a bijection of a set back onto itself. Since it doesn't really matter what the n items are, specifically, (since the overall structure of the permutation will be the same) we can just think about permutations on the integers 1, 2, 3, ... , n. The collection of all permutations on a set of size n is a group under permutation composition. We call this group the symmetric group on n letters, Sn. (Verifying that it is indeed a nonabelian group isn't too bad, especially when we recall that function composition is associative.)
That's all fun and well and good, but how do we compactly represent a permutation?
Well...we can think about where the permutation sends each number, and we could list the permutation one by one. For example, a permutation on 1 to 3 could send 1 to 2, 2 to 3, and 3 to 1. So we could list: 1 → 2; 2 → 3; 3 → 1. A different way to write the same permutation is in what's called disjoint cycle notation, so the permutation is represented as (1, 2, 3). We just read this left to right similarly: 1 goes to 2, 2 goes to 3, 3 goes to 1. A permutation that looks like (2, 4, 6)(3, 5) sends 2 to 4, 4 to 6, and 6 to 2; as well as 3 to 5 and 5 to 3. The advantage of this notation is that it's much faster to write permutations on large sets than to spell out the bijection one by one. It's also quite useful to visualise exactly how the permutation moves around the set: here, we see that it does two separate processes: one on 2, 4, 6 and one on 3, 5. These are called the disjoint cycles of the permutation. Cool (and useful) theorem: all permutations can be written as the product (composition) of disjoint cycles. Disjoint cycles are nice because, while permutation composition isn't generally commutative, it is on disjoint cycles.
It's also nice because we can tell right away how many times we need to do the permutation before we back the original sequence. The cycles are disjoint so they aren't interfering with each other. Let's consider (2, 4, 6)(3, 5). We see that if we did (2, 4, 6) three times, we would get the original sequence back: we just rotate the three elements, in this case 2, 4, and 6, around three times and they return to their original spot. Similarly for (3, 5), we see that it only takes two times for this cycle to be undone. Generally, a cycle of k length will take k iterations before we get back to the original sequence we started with. So if we have a product of disjoint cycles, the least common multiple of their lengths is the number of times we'd need to do the product before it undid itself.
Another way to write permutations is by representing it as the product of a bunch of transpositions. A transposition is just a permutation that swaps two elements and leaves all the other ones intact. It should be pretty visually/intuitively understandable that we can represent a reordering of n elements to just a series of two-element swaps. However, we can see that this representation isn't unique: we can find more than one way to compose swaps to result in the same permutation. Thankfully, there is a property that we can pull out of this transposition representation: if a permutation can be represented as the succession of an even number of transpositions, then it certainly cannot be represented as a succession of an odd number of transpositions. The same is true for the reverse. Thus, we can categorise a permutation as either even or odd, based on whether it can be written as the composition of an even or odd number of transpositions. We notice that the subset of all even permutations in Sn is a subgroup of Sn. For some reason, that subgroup is called the alternating group on n letters, An. (The collection of odd permutations isn't a group because it isn't closed: the composition of two odd permutations is even.)
Great. So what's the point of permutations? Well...they're kind of cool! And they give us a whole selection of groups that are nonabelian, to which we may compare other nonabelian groups. It's probably useful to notice that the order of Sn is n factorial (n!).
The last cool thing: Cayley's theorem. Every single group (ALL the groups!) is isomorphic to a subgroup of permutations. While this result is a little trippy and hard to think about, just visualise a group table, say Z3:
+ 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1
See, for example, that the element 1 permutes 012 to 120 and the element 2 permutes 012 to 201 (of course, the identity element performs the identity permutation). Then, we can form a bijection between each element in the group to the permutation it performs.
Woah. Take a while, let it sink in. Until next time.
(While it's pretty cool that we can find an isomorphism between any group to a subgroup of permutations, unfortunately Cayley's theorem isn't used too much in practice because we can't really say much more about the subgroup of permutations than we typically can just derive from the group itself.)