Subgroups and Symmetric Groups

November 13, 2010, 14:57
Filed under: Algebra, Math | Tags: algebra, combinatorics, group theory, MaBloWriMo, Math

Like yesterday, today is pretty much just going to be me talking about groups until I feel like stopping. I’m hoping to osmose to you some of the ways in which groups “work” and that you can deal with them. Pretty soon, we should have the background ready for one of the neatest paradoxes/counterexamples in math — the Banach-Tarski Paradox!

Last time, we talked about homomorphisms (functions between groups that preserve the group operation), isomorphisms (bijections that are homomorphisms both ways), generators (elements which give you the whole group through inversion and multiplication), and cyclic groups (groups generated by a single element, which all work like modular arithmetic). Let me start with two factoids I should have mentioned last time. We can get a cyclic group generated by an element $a$ , but without any requirement that $a^n=e$ . So the elements of the group are $\dotsc a^{-2},a^{-1},e=a^0,a^1,a^2,\dotsc$ , and they’re all distinct. This group is isomorphic to $\mathbb{Z}$ , the integers under addition! In this sense, we call $\mathbb{Z}$ the infinite cyclic group. As expected, there aren’t “any other” infinite cyclic groups: for example, no rational generates every other rational through repeated addition, nor does any real generate every other real.

The second fact is something useful to remember: note that $(h^{-1}g^{-1})(gh)=h^{-1}h=e$ and likewise $(gh)(h^{-1}g^{-1})=e$ . As we showed, inverses are unique, so this proves that $h^{-1}g^{-1}=(gh)^{-1}$ . Inversion reverses the order of composition.

Okay, so today I want to talk about subgroups. A subgroup is a subset of a group that is still a group with the same operation. What does this mean? Well, associativity is a given. It has to contain the identity of the big group, as well. The other things to check are what we call closure properties — a set is closed under an operation when performing that operation on elements of the set gives you back an element of the set. (So the integers aren’t closed under division since the quotient of two integers isn’t necessarily an integer). In this case, we need to check that the subgroup is closed under multiplication and inversion ( $g\mapsto g^{-1}$ ).

Going back to our favorite example of $D_8$ , let’s look at the subset $\{e,r,r^2,r^3\}$ . It should be clear that this contains the identity and is closed under multiplication and inversion (the product of two rotations is a rotation, the inverse of a rotation is a rotation). So this is a subgroup of $D_8$ . Similarly, the subset $\{e,f\}$ is a subgroup. Trivially, we have $\{e\}$ and $D_8$ itself. There are two others, one of order 2, and one of order 4. Can you find them?

There’s a shorter way to describe our subgroups. Once we know that a subgroup contains $r$ , we also know it contains $r^2$ and $r^3$ . The first subgroup, above, is thus the smallest subgroup containing $r$ — we could have just said “the subgroup generated by $r$ .” Since we already know how the group operation works, a subgroup is completely described by just saying its generators!

There’s a place I think I’m supposed to go from here, but I’d rather show you something cool first. Perhaps the founding example of a group was the group of permutations of a set of things. Nowadays, we call this the symmetric group on $n$ symbols, or $S_n$ for short. Let’s look at $S_3$ . We start with the string 123, and then every element of $S_3$ is a possible rearrangement of those three numbers. In $S_3$ , these are [123], [132], [213], [231], [312], and [321], for a total of six elements, and in general, $|S_n|=n!$ ². We shouldn’t think of the group elements as arrangements, but as ways to move around a string of three symbols, so I’ll put brackets around the group elements and nothing around the symbols they transform.

Here’s how $S_3$ works: You start with 123 and you apply the group element [321] to it. This gives you the string 321. If you then apply [213], this switches the first two symbols, giving 231. Thus, $[213]\circ [321]=[231]$ , where the order corresponds to the composition of functions. Meanwhile, $[321]\circ [213]=[312]$ . Symmetric groups are, in general, very non-commutative. There’s actually a lot to be said about their structure and use, but I’d rather leave that for its own post. For now, all you need is the bare essentials.

The symmetric group on a set $A$ , $S_A$ is the set of “permutations” of $A$ , i. e. bijections $A\rightarrow A$ . We don’t talk about these groups as much. But observe, for example, that if $A$ is finite with cardinality $n$ , then the symmetric group on $A$ is isomorphic to $S_n$ , and a canonical isomorphism exists for each bijection $b:n\rightarrow A$ : namely, send a bijection $f:A\rightarrow A$ to the permutation of $n$ , viewed as a set of $n$ symbols, given by $b^{-1}\circ f\circ b$ .

Theorem (Cayley). Every group is isomorphic to a subgroup of a symmetric group — in fact, $G$ is isomorphic to a subgroup of $S_G$ for all groups $G$ .

Proof. For every $g\in G$ , define $p_g$ to be the map $G\rightarrow G$ given by $p_g(h)=gh$ . This is just left multiplication by $g$ . Each such map is a bijection: it is one-to-one because if $gh=gj$ , then $g^{-1}gh=g^{-1}gj$ , so $h=j$ ; and it is onto because for every element $h$ , we have $p_g(g^{-1}h)=h$ . We give the set of maps $p_g$ a group structure by composition of maps. I claim that $p_g\circ p_h=p_{gh}$ : just observe $p_g(p_h(j))=p_g(hj)=g(hj)=(gh)j=p_{gh}(j)$ . Composition of maps is always associative, the identity is $p_e$ , and the inverse of $p_g$ is $p_{g^{-1}}$ . But then $g\mapsto p_g$ is an isomorphism from $G$ to the set of maps $p_g$ ! Moreover, since the set of maps $p_g$ define a group, they are a subgroup of the set of all bijections on the set $G$ , which is just $S_G$ . $\square$

In particular, if $G$ is a finite group of order $n$ , then $G$ is isomorphic to a subgroup of $S_n$ . We say that $G$ can be embedded into $S_n$ . It should be pretty clear that you can get an isomorphism just by drawing a multiplication table for $G$ , labelling its elements 1 through $n$ , and sending every element of $G$ to the permutation given by the corresponding row of the multiplication table.

Of course, such an embedding isn’t necessarily the best way of doing things: for example, Cayley’s Theorem give us an embedding of $S_3$ into $S_6$ , since it has six elements, but there’s a trivial embedding of $S_3$ into itself! So the symmetric group given by Cayley’s Theorem could possibly be made smaller, in some circumstances.

Next time — quotient groups!

¹“Check for associativity” is always left as an exercise, just because it’s the most utterly tedious thing you can imagine. Worse yet, it gets more tedious when it’s non-obvious and actually needs to be checked, as in matrix multiplication. Like everything in math, though, if you do it once, you won’t have to do it again.

²The notation $n!$ is “ $n$ factorial,” defined as $n!=n(n-1)(n-2)\dotsm 2\cdot 1$ . This is the number of permutations of $n$ things. Among other things, it’s huge for large numbers. For more information, see here.

3 Comments

3 Comments so far
Leave a comment

[…] 16 11 2010 Today we’re going to take the abstract group machinery we’ve been building up, and unleash it on some sets. When mathematicians say that […]

Pingback by Group Actions « Gracious Living November 16, 2010 @ 15:01

[…] mention a couple more ways of “building” groups. We’ve already seen how to find subgroups, and how to take the quotient by a normal subgroup, and how to find the direct product of a family […]

Pingback by More Products of Groups « Gracious Living November 27, 2010 @ 22:40

[…] seen symmetric groups before. The symmetric group on an arbitrary set, or , is the group of bijections from the set to […]

Pingback by Symmetric Groups « Gracious Living December 18, 2010 @ 11:36

RSS feed for comments on this post. TrackBack URI

Gracious Living

Categories

Archives

Links

Gracious Living

Categories

Archives

Links

Share this:

Related

Leave a comment Cancel reply