Gracious Living

Symmetric Groups
December 18, 2010, 11:36
Filed under: Algebra, Math, Uncategorized | Tags: , , , ,

We’ve seen symmetric groups before.  The symmetric group on an arbitrary set, S_X or {\rm Sym}(X), is the group of bijections from the set to itself.  As usual, we’re only interested in the finite case S_n, which we call the symmetric group on n 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 S_4, for example, [2314] 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: x_1 to x_2, x_2 to x_3, …, x_k to x_1, with no other symbols affected.  We’ll write cycles with parentheses: the above would be (x_1x_2\dotsm x_k), (12) is the generator of S_2, and so on.  We can multiply cycles just as we do permutations: (123)(45) is an element of S_5 (or of any S_n with n\ge 5, it isn’t entirely clear) which rotates the first three symbols and flips the fourth and fifth.  Its order is 6, 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: (123)(45)=(45)(123).  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: (123)=(231)=(312).  But, on the other hand, (132)=(213)=(321)=(123)^{-1}.  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 p be our permutation, and let P\subset S_n be the cyclic group generated by it.  Then P also acts on the set of symbols \{1,\dotsc,n\}.  For each 1\le k\le n, find the image of k under successive applications of p, and write them out in order: clearly, this is one cycle (it’s of finite length because P is finite).  But also, this is some ordering of the orbit of k under P.  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 p 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. \square

Now let’s talk about transpositions.  A transposition is a cycle of length 2.  Clearly, we can write permutations as products of transpositions: (123)=[231]=(12)(13), 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 — (13)=(23)(12)(23).  It follows that the n-1 transpositions (12),(23),\dotsc,((n-1)(n)) are generators for the group.  What are the relations?  Letting \tau_i=((i)(i+1)), it’s clear that disjoint \tau_i commute, that each \tau_i is order 2, and that conjugating \tau_i by \tau_{i+1} is the same as conjugating \tau_{i+1} by \tau_i: both give you ((i)(i+2)).  So we have at least the three relations:

  • \tau_i^2=e
  • \tau_i\tau_j=\tau_j\tau_i for |i-j|>1
  • \tau_{i+1}\tau_i\tau_{i+1}=\tau_i\tau_{i+1}\tau_i for |i-j|=1

Clearly S_n satisfies these relations.  But does the above presentation generate S_n?  In fact, they do.  Here’s a somewhat lengthy proof.  Let T_n, say, be the group generated by this presentation, that is, the group \langle t_1,\dotsc,t_{n-1}|t_i^2,t_it_jt_i^{-1}t_j^{-1},t_{i+1}t_it_{i+1}t_i^{-1}t_{i+1}^{-1}t_i^{-1}\rangle where |i-j| is always at least 2.  Since S_n satisfies the same relations as T_n, there’s a surjective homomorphism T_n\rightarrow S_n with t_i\mapsto \tau_i for each i.  To prove it’s an isomorphism, it remains to be shown that it’s injective, or equivalently, that |T_n|=|S_n|=n!.  (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 T_n can be written as a word in t_1,\dotsc,t_{n-1} without using their inverses.  By induction, let’s prove that t_{n-1} only has to occur once in this word.  Clearly this holds for S_1=\{e\},S_2=\{e,t_1\}.  Assume it holds for T_{n-1}, and let w be a word in T_n with two occurrences of t_{n-1}.  Look at the word between them.  If it doesn’t contain t_{n-2}, 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 t_{n-1} to either side of it, and change the resulting t_{n-1}t_{n-2}t_{n-1} to t_{n-2}t_{n-1}t_{n-2}.  Clearly, we can repeat these operations until we only have one t_{n-1}.

The final step is to look at the following sets:

\displaystyle U_1 = \{e,t_1\}

\displaystyle U_2 = \{e,t_2,t_2t_1\}

\displaystyle \dotsc

\displaystyle U_{n-1}=\{e,t_{n-1},t_{n-1}t_{n-2}, t_{n-1}t_{n-2}\dotsm t_1\}

By induction, we’re going to prove that T_n\subset U_1U_2\dotsm U_{n-1} (any element of T_n can be written as a product of one element from each set, in that order).  Again, this is true for T_1,T_2.  Suppose it holds for T_{n-1}.  Given g\in T_n, we can use the above to write it with a single t_{n-1}, g=w_1t_{n-1}w_2, where w_1,w_2 are words not containing t_{n-1}.  By the induction hypothesis, we can write w_2 as a product u_1u_2\dotsm u_{n-2},u_i\in U_i for all i.  Obviously t_{n-1} commutes with all u_i but the last, so we can write g=w_1u_1u_2\dotsm t_{n-1}u_{n-2}.  But t_{n-1}u_{n-2}\in U_{n-1}.  Meanwhile, w_1u_1\dotsm u_{n-3} is in T_{n-1}, so by the induction hypothesis, we can write it as a product v_1\dotsm v_{n-2},v_i\in U_i.  Multiplying the two halves together again, we get what we asked for.

Why were we doing this?  Because |U_i|=i+1, and the above gives a surjective function (not a homomorphism, the U_i aren’t groups) from U_1\times\dotsb\times U_{n-1} to T_n.  Since the cardinality of the first set is n!, |T_n|\le n!.  But we also have a surjective homomorphism T_n\rightarrow S_n, so |T_n|\ge n!.  Taken together, these facts give |T_n|=n!,T_n=S_n.  \square

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 \tau_i 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, {\rm sgn}(p).  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 \rm sgn is a group homomorphism to \mathbb{Z}/2, where 0 is “even” and 1 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 A_n.  These guys show up all the time — A_4 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 A_5 as the orientation-preserving symmetry group of a dodecahedron or icosahedron.

A final word about conjugacy.  Given a cycle q=(a_1a_2\dotsm a_k), the result of conjugating by a permutation p is pqp^{-1}=(p(a_1)p(a_2)\dotsm p(a_k)), as you should check.  Conversely, any two cycles of the same length are conjugate: if they are (a_1a_2\dotsm a_k), (b_1b_2\dotsm b_k), then we just need a permutation that sends a_i to b_i for each i, 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 S_n 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 e=(1)(2)\dotsm (n)), then the number of conjugacy classes of S_n is equal to the number of partitions of n: for example, for 4, we have 1+1+1+1 (the identity), 1+1+2,2+2,1+3,4.  We can use the binomial theorem to compute the class equation; for S_4:

\displaystyle 4!=24=1+6+3+8+6

Hope you enjoyed!

Leave a Comment so far
Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: