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 , but *without any requirement* that . So the elements of the group are , and they’re all distinct. This group is isomorphic to , the integers under addition! In this sense, we call 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 and likewise . As we showed, inverses are unique, so this proves that . 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 ().

Going back to our favorite example of , let’s look at the subset . 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 . Similarly, the subset is a subgroup. Trivially, we have and 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 , we also know it contains and . The first subgroup, above, is thus the *smallest* subgroup containing — we could have just said “the subgroup **generated** by .” 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 symbols**, or for short. Let’s look at . We start with the string 123, and then every element of is a possible rearrangement of those three numbers. In , these are [123], [132], [213], [231], [312], and [321], for a total of six elements, and in general, ^{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 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, , where the order corresponds to the composition of functions. Meanwhile, . 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** , is the set of “permutations” of , i. e. bijections . We don’t talk about these groups as much. But observe, for example, that if is finite with cardinality , then the symmetric group on is isomorphic to , and a *canonical* isomorphism exists for each bijection : namely, send a bijection to the permutation of , viewed as a set of symbols, given by .

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

**Proof**. For every , define to be the map given by . This is just left multiplication by . Each such map is a bijection: it is one-to-one because if , then , so ; and it is onto because for every element , we have . We give the set of maps a group structure by composition of maps. I claim that : just observe . Composition of maps is always associative, the identity is , and the inverse of is . But then is an isomorphism from $G$ to the set of maps ! Moreover, since the set of maps define a group, they are a subgroup of the set of all bijections on the set , which is just .

In particular, if is a *finite* group of order , then is isomorphic to a subgroup of . We say that can be **embedded** into . It should be pretty clear that you can get an isomorphism just by drawing a multiplication table for , labelling its elements 1 through , and sending every element of 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 into , since it has six elements, but there’s a trivial embedding of 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.

^{2}The notation is “ **factorial**,” defined as . This is the number of permutations of things. Among other things, it’s huge for large numbers. For more information, see here.

**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 LivingNovember 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 LivingNovember 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 LivingDecember 18, 2010 @ 11:36