Filed under: Algebra, Math, Uncategorized | Tags: algebra, combinatorial, group theory, Math, symmetry
We’ve seen symmetric groups before. The symmetric group on an arbitrary set, or , is the group of bijections from the set to itself. As usual, we’re only interested in the finite case , which we call the symmetric group on symbols. These are pretty important finite groups, and so I hope you’ll accept my apology for writing a post just about their internal structure. The language we use to talk about symmetric groups ends up popping up all the time.
The notation we used to describe symmetric groups when I first introduced them was as follows: in , for example, meant to send 1 to 2, 2 to 3, 3 to 1, and 4 to 4. But there are at least two better ways of describing them. First is cycle notation. A cycle is a permutation sending symbols in a circle: to , to , …, to , with no other symbols affected. We’ll write cycles with parentheses: the above would be , is the generator of , and so on. We can multiply cycles just as we do permutations: is an element of (or of any with , it isn’t entirely clear) which rotates the first three symbols and flips the fourth and fifth. Its order is , which is the lowest common multiple (lcm) of the lengths of the cycles forming it. (Prove this.)
Clearly, disjoint cycles, those that don’t share any symbols, commute: . Also, though it’s customary to write a cycle beginning with the first symbol possible, the symbols in a cycle can be rotated without changing its meaning: . But, on the other hand, . So all we can do is re-cycle an individual cycle, not permute it without rhyme or reason.
- Theorem. Every permutation can be written as a product of disjoint cycles, and this is unique up to ordering of the cycles and re-cycling of each individual one. (The identity is the product of zero cycles.)
Proof. Let be our permutation, and let be the cyclic group generated by it. Then also acts on the set of symbols . For each , find the image of under successive applications of , and write them out in order: clearly, this is one cycle (it’s of finite length because is finite). But also, this is some ordering of the orbit of under . Since distinct orbits are disjoint, we can choose the cycle corresponding to one element of each orbit, multiply them together, and we’ll have an expression for as a product of disjoint cycles. If we choose a different element from an orbit, this necessarily corresponds to a re-cycling of the corresponding cycle.
Now let’s talk about transpositions. A transposition is a cycle of length . Clearly, we can write permutations as products of transpositions: , where, as usual, a product of cycles is applied right to left, like a composition of functions. In fact, we can even use transpositions of adjacent symbols — . It follows that the transpositions are generators for the group. What are the relations? Letting , it’s clear that disjoint commute, that each is order , and that conjugating by is the same as conjugating by : both give you . So we have at least the three relations:
Clearly satisfies these relations. But does the above presentation generate ? In fact, they do. Here’s a somewhat lengthy proof. Let , say, be the group generated by this presentation, that is, the group where is always at least . Since satisfies the same relations as , there’s a surjective homomorphism with for each . To prove it’s an isomorphism, it remains to be shown that it’s injective, or equivalently, that . (Of course, as we discussed, it isn’t even clear from an arbitrary generators-and-relations presentation if the given group is finite.)
Since all the generators are order 2, we don’t need the inverse symbols at all: an arbitrary element of can be written as a word in without using their inverses. By induction, let’s prove that only has to occur once in this word. Clearly this holds for . Assume it holds for , and let be a word in with two occurrences of . Look at the word between them. If it doesn’t contain , then they commute with it, so we can scoot one of them through to the other side and cancel it out. If it does, then by the induction hypothesis, it only occurs once, so we can scoot both copies of to either side of it, and change the resulting to . Clearly, we can repeat these operations until we only have one .
The final step is to look at the following sets:
By induction, we’re going to prove that (any element of can be written as a product of one element from each set, in that order). Again, this is true for . Suppose it holds for . Given , we can use the above to write it with a single , , where are words not containing . By the induction hypothesis, we can write as a product for all . Obviously commutes with all but the last, so we can write . But . Meanwhile, is in , so by the induction hypothesis, we can write it as a product . Multiplying the two halves together again, we get what we asked for.
Why were we doing this? Because , and the above gives a surjective function (not a homomorphism, the aren’t groups) from to . Since the cardinality of the first set is , . But we also have a surjective homomorphism , so . Taken together, these facts give .
Unfortunately, there’s no unique or standard way to write a permutation as a product of adjacent transpositions. But the generators-and-relations presentation suggests something. See, applying the first relation to a word changes its number of by two, and applying either of the other relations keeps the number the same. So if two words represent the same group element, they must differ by an even number of generators! Thus, whether a permutation takes an even or odd number of generators is invariant of how we write that permutation — we call this the sign of the permutation, . Note that all transpositions are odd (prove this yourself), so we can find the sign by writing a permutation in terms of arbitrary transpositions rather than adjacent ones.
Oh, and it should also be pretty easy to see that is a group homomorphism to , where is “even” and is “odd.” Its kernel is therefore a normal subgroup (actually, any subgroup of index 2 is normal — see why?). We call this the alternating group . These guys show up all the time — is the orientation-preserving symmetry group of a tetrahedron, since you can rotate three vertices and leave one fixed, or flip two pairs of two vertices, but you can’t flip just two vertices without employing a reflection. We also talked about as the orientation-preserving symmetry group of a dodecahedron or icosahedron.
A final word about conjugacy. Given a cycle , the result of conjugating by a permutation is , as you should check. Conversely, any two cycles of the same length are conjugate: if they are , then we just need a permutation that sends to for each , which is easy enough. This reinforces the heuristic that conjugacy is just sort of “change of basis”. But now look: by induction, any two permutations are conjugate in iff when written in disjoint cycle form, they have cycles of the same length. If we write out permutations with “1-cycles” of the letters they don’t fix (so ), then the number of conjugacy classes of is equal to the number of partitions of : for example, for , we have (the identity), . We can use the binomial theorem to compute the class equation; for :
Hope you enjoyed!
Leave a Comment so far
Leave a comment