Wednesday, January 02, 2008

Abstract algebra

In our last post, our intrepidly heroic mathematicians were hunting around for a new tool with which to attack some classic conundrums of geometry. The tool they eventually settled on is known as abstract algebra. This post will attempt to summarise it very briefly.

Compared to the 100 pages of lecture notes I'm working from, anyway.

Abstract algebra

The purpose of abstract algebra is to study and categorise various kinds of mathematical structure that crop up with depressing regularity. What do I mean by "structure"? Well, let's take a look at a really simple example: a group.

A group is formed of two components. Firstly, you have a big bag of thingies. Any thingies, it really doesn't matter that much. We'll refer to the bag as X, just to save my having to use the word "thingy" too much.

Secondly, you have a rule that combines two thingies to give a third. We'll refer to the bag as #. The rule must have certain "nice" properties:

1) Closure - the product of two thingies is a thingy. Formally, if x and y are in X then so is x#y.
2) Associativity - if you apply the rule twice to merge three thingies into one, it mustn't matter which two order you do the merging in. Formally, (x#y)#z = x#(y#z).
3) Identity - there is a thingy that can be ignored when applying the rule. Formally, there exists a single element e of X (the identity element) such that x#e = e#x = x for all x in X.
4) Inverse - for any thingy, there must be another thingy such that, when they're merged, you get the identity element. Formally, for any x in X, there exists an element y such that x#y = e.

Got that? No? Well that's not a problem, because I'm going to give you a concrete example.

The set will be as follows: {..., -3, -2, -1, 0, 1, 2, 3, ...}
The rule will be as follows: +

So 1+1=2, 2+6=8, etc. Looking familiar now?

The group that we've just described is the set of integers (whole numbers) under addition. It obeys all the four rules:

1) Add two integers and you get a third integer
2) (a+b)+c = a+(b+c)
3) a+0 = 0+a = a
4) If x is an integer then -x is also an integer

There are lots and lots of other examples:

A) The set of integers under multiplication
B) The set of reflections and rotations of a shape under composition (aka the dihedral group)
C) The set of hours on a 12-hour clock under addition (aka the cyclic group of order 12)

Example A is pretty straightforward - proof that it's a group is left to the interested reader.

Example B is more interesting. Consider, for example, the dihedral group of a triangle. Imagine the triangle is a piece cut out of a sheet of paper - you can flip it over or rotate it around in any way, as long as it still fits in the hole. Why not get yourself a real sheet of paper and try it?

Start off with one point of the triangle sticking directly upwards. You'll quickly find that the valid operations are as follows:

a) Keep it as it was
b) Rotate it 120° left
c) Rotate it 120° right
d) Flip it in the top/bottom line of symmetry
e) Flip it in the top-left/bottom-right line of symmetry
f) Flip it in the top-right/bottom-left line of symmetry

So our set is {a,b,c,d,e,f}. Our group rule is composition, which means doing two of these operations one after another. So for example, b#c = a, and d#e = b. Try it!

Is this a group? It quite clearly has closure, identity and inverses. It turns out to also have associativity, although this is less obvious.

One interesting point to notice is that the operations {a,b,c} form a group in their own right, even without including d, e and f. This subgroup consists of all the ways that a triangle can be rotated. It is called the cyclic group of order 3.

Example C, the clock, is fairly basic - most of the time it behaves just like the integers under addition. Just remember that 4 hours past 10:00 is actually 2:00, and you'll have understood most of what's going on here.

This group also has subgroups. For example, consider what happens if you're only allowed to move the clock on in four-hour intervals. The times you can reach are 0:00, 4:00 and 8:00 (I'm writing 12:00 as 0:00 here - either way, it's the identity element).

This subgroup is in fact the cyclic group of order 3 - so the dihedral group of order 3 and the cyclic group of order 12 both share it as a subgroup, despite having very different origins and properties.


There's one last group that I'm going to describe, because it will be particularly relevant later on. That is the "permutation group".

A permutation is just a rearrangement or shuffle. For example, we could reorder the list "1 2 3 4 5" to "2 5 3 4 1". Call this permutation p.

How does p behave? Well it replaces each 1 with a 2, each 2 with a 5, each 3 with a 3, each 4 with a 4, and each 5 with a 1. Mathematicians have a very concise way of describing this, called cycle notation. A cycle is just a list of elements [a,b,c,...,z], so that the permutation takes a to b, b to c, c to d, z to a, and so on.

In our example permutation p, there are two very obvious cycles. p takes 3 to 3, so [3] is a cycle of p. Similarly, [4] is a cycle of p. p also takes 1 to 2, 2 to 5 and 5 to 1, so [125] is the final cycle. All our knowledge about p can be conveyed by writing it as [125][3][4].

It's easy to note that these permutations form a group - if you do one permutation followed by another, the result is a third permutation. All permutations can be undone, and there is an identity permutation [1][2][3][4][5]. Associativity is slightly less easy, but not hard, to show.

Permutation groups are a particularly important example of finite groups - groups with only a finite number of members. For example, cyclic groups and dihedral groups are finite, but the integers are not finite. The group of all permutations of n objects is called the symmetric group of order n, written as Sn. For example, the group of all possible shuffles of a set of cards is S52.

These symmetric groups are important because it can be proven that any finite group is a subgroup of some symmetric group. This will become relevant later.

This series of posts has gotten far longer than I intended. I'll take a short break before the next post.

No comments: