Symmetric Groups

December 18, 2010, 11:36
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, $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$ :