Gracious Living


Subgroups and Symmetric Groups
November 13, 2010, 14:57
Filed under: Algebra, Math | Tags: , , , ,

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!2. 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!



1
“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.

 

2The 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.

Advertisements

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

[…] 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

[…] 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




Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s



%d bloggers like this: