## Group Theory: Symmetric, Alternating, and Quaternion groups

Let’s talk about “symmetric groups” and, at the very end of the post, “alternating groups” and the “quaternion group”.

First, let’s get the abstract algebra package running… and tell it that we’re doing groups. (The alternative is “rings”, which have two operations instead of one.) You can find this free package here.

Let’s see what happens if I ask for the symmetric group “3” (and I’ve asked for its set of elements and called it p):

The help system tells me that the elements of this group are all of the permutations of 3 objects, with composition as the group product.

Let’s back up. Given a set X – any set X, possibly infinite – we consider the set $S_X\$ of all bijections from X to X – that is, all one-to-one onto functions from X to X. Each such function is called a permutation. Function composition $\circ\$ is associative, so it is a plausible group operation. We also have closure: the composition of two bijections (permutations) is a bijection (permutation). We also have an identity, the permutation which maps every element to itself. Finally, we can exhibit an inverse permutation.

The group $(S_X, \circ)\$ is called the symmetric group on the set X. If X = {1, 2, …, n}, we write $S_n\$ and call it the symmetric group of degree n.

We can show that the order of the group is n! (n factorial, n bang, or n shriek).

Returning to the group in our hands, it would appear that I asked for the symmetric group of degree 3, and it is of order 6, i.e. 3!.

It is important to realize what is meant by the notation, for example, {1,3,2}. The command I need is:

That says that this function maps 1 to 1, 2 to 3, and 3 to 2.

Another?

It maps 1 to 3, 2 to 2, and 3 to 1.

All of them?

Anyway, since the top line is always (1,2,3) we may omit it… and that’s why the elements were written as 6 lists – the 6 bottom lines – each of length 3.

(Let explain that rather cryptic Mathematica® command. The [#]& is a placeholder for one argument… and the /@p says use each of the elements of p one at a time. The problem is that the function PermutationMatrix can only take one argument at a time, but I want to feed it a list of 6. That’s how I do it.)

Next, if our group operation is the composition of functions, let’s look at composition – which I’ll think of, and refer to, as multiplication. How about p1 times p2? Well, p1 is the identity, so I hope we get p2 for the product.

Good. And I could comfortably use the shorthand notation because the answer is p2.

Now how about p2 times p3? We need to think about it. If I write p2 p3, I want to be using the usual elementary notation for composition: the juxtaposition p2 p3 is to mean the function p3 followed by the function p2 – just as f(g(x)) means the function g followed by the function f.

(I could change that; it’s an option. We could set it so that p2 p3 means apply p2 first, and then p3. I strongly prefer the usual elementary notation – but every author gets to choose his own preference, so you have to see what convention is in use in whatever you’re reading.)

Here’s the product – but I’m writing all three permutations out the long way. Note that the third line – not printed! – computed the product, while the fourth line displayed it. Since I will apply p3 first, I write it first. The three lines, then are p3, p2, and the product p2 p3 (i.e. p3 followed by p2):

Can we follow that? p3 maps 1 to 2, and p2 maps 2 to 3, so the composition should map 1 to 3. Good.

p3 maps 2 to 1, and then p2 maps 1 to 1, so the composition should map 2 to 1. Good.

p3 maps 3 to 3, and then p2 maps 3 to 2, so the composition should map 3 to 2. Good.

Now that we know how to multiply permutations… what’s the inverse of p2? Write out p2…

Hmm. That’s p2 again. Is it really its own inverse? Yes:

That’s the identity permutation, mapping x to x, for x = 1,2,3.

Well, let’s ask for the orders of all the elements:

Three elements of order 2, two of order 3, and one (the identity, of course) of order 1.

Let’s ask for the multiplication table:

Now, let’s look at the multiplication table for D3, the dihedral group of order 6, i.e. all the symmetries of an equilateral triangle:

They’re the same. (The same colors have been assigned to the same elements, and the layout of colors is the same. I didn’t compare permutations; I compared colors.)

This paragraph and the next one belong between the two pictures – but I need these pictures to be right close to each other. You might have remembered that when I first looked at the dihedral group of order 6, i.e. D3, I asked for it as a set of permutations – so that I could show how the vertex numbers changed on an equilateral triangle.

In that form, D3 consisted of 6 permutations on 3 symbols. But that’s all of the permutations on 3 symbols. Do you find it plausible that it’s the very same group as S3?

We could look at S4… but it’s got 4! = 24 elements, so it’s getting kind of big for looking at.

But there’s something else we need to look at. They’re called cycles. They are permutations, but special ones.

Let me start by showing you some.

That is, the permutation {1, 3, 2} cycles 2 -> 3 -> 2; 1 isn’t shown because it’s fixed. If you’re new to cycles and permutations, go ahead and include the 1-cycle (1) along with the 2-cycle (2,3):

(1) (2,3)

O…K… This time 1 and 2 cycle, and 3 is fixed. He showed the “3”, to tell us what the largest number is in the given permutation.

Let’s look at the identity:

He printed nothing for “1” or “2” – they’re fixed; but he printed Cycle[3] to show that “3” is the largest number in the permutation. That is, instead of printing

(1) (2) (3)

he printed only (3).

Another one?

So this cycle is 1 –> 2 –> 3 –> 1 etc.

Right?

Right. That’s exactly what the permutation p4 does.

Perhaps you begin to suspect there might be a great opportunity here – to completely screw up.

If we are looking at (1,2,3) we damned well better know whether that’s a permutation or a cycle. As a permutation, it’s shorthand for the identity:

… which is not the identity.

So: the notational distinction between permutations and cycles is crucial. (You may never have a problem. I envy you. I learned to be careful by messing it up.)

There’s something else you might have noticed: our cycles ere disjoint. The relevant and key theorem is that

any permutation may be written (essentially) uniquely as a product of disjoint cycles.

Essentially? It doesn’t really matter whether we write, for example, (1,2,3) or (2,3,1) or (3,1,2). It doesn’t really matter if we write, for example, any one of

(1) (2,3)
(2,3) (1)
(2,3)
(3,2)
(3,2)(1)
(1) (3,2).

One last thing before we’re done with permutations in general. There is another possible decomposition: into 2-cycles, also called transpositions. This is not generally unique….

Let’s see one.

What does that mean?

I have to say that disjoint cycles made perfect sense to me right off the bat… but what does it mean when they’re not disjoint?

Just treat (1 3) (1 2) as a product. Remember that my convention is to apply them from right to left.

1 -> 2 -> 2
2 -> 1 -> 3
3 -> 3 -> 1

Then just read the RHS: the permutation is {2,3,1}.

Right? Right, the permutation {2, 3, 1} is what we started with.

Just for the fun of it, let’s reverse the 2-cycles: we take (1 2) (1 3):

1 -> 3 -> 3
2 -> 2 -> 1
3 -> 1 -> 2

so the permutation is {3,1,2}.

We can check that… I define the list… ask for the 2-line display to make sure the package did what I wanted… and then ask for

Now that we know about transpositions, I need to hit you with another theorem which I’m not going to prove. Although the decomposition of a permutation into transpositions is not unique,

the number of transpositions is always the same.

That, in turn, means that every permutation is either the product of an even number of transpositions or an odd number of transpositions, and we may classify any permutation as even or odd. Since the identity is the product of zero transpositions, and zero is an even number… we have to wonder if the subset of even transpositions in Sn is a group in its own right. (The subset of odd permutations cannot be a group because it doesn’t have an identity.)

It is. It’s called the alternating group, and written An. It turns out that half the permutations in Sn are even, and half are odd, so An has half the order of Sn, namely n!/2.

Here’s A3…

Interesting. He wrote the identity as (1 3) (3 1). Hmm. (1 2) (2 1) would have worked too… but his way shows the highest number in the permutations. OK. The point is that we have an even number of transpositions in every case.

While we’re here, what are the disjoint cycle decompositions?

Here’s A4…

And possible transposition decompositions?

Two elements are the product of four 2-cycles; the other 10 are each the product of two 2-cycles.

And while we’re here, what are the disjoint cycle decompositions of A4?

Moving right along….

The quaternion group has 8 elements. ±1, ±i, ±j, ±k, where i, j, k are the quaternion units: i^2 = j^2 = k^2 = -1, and ij = k. I think that’s enough to work them all out… but if necessary, we could use the right hand rule to get jk, and ik and kj, etc.

(Instead of having two square roots of -1, namely ±i, we have 6. And the mixed products such as jk could be computed as though it was the cross product of the unit j and k vectors. I should give you a link to my introduction to quaternions.)

The package uses JJ and KK for J and K, and it explains why. Its “I” is Mathematica’s usual imaginary unit.

Here’s its multiplication table. (This wouldn’t be too bad to fill in by hand. S3 would have been annoying, and A4 would have been painful to do by hand. I’m so grateful for my computer and software.)

Like S3 (and D3, and Sn and Dn for n >= 3), the quaternion group is not abelian (i.e. commutative). We know that as soon as we know that ij = -ji = k. But we see it in the table because it’s not symmetric about the main diagonal.

Let me close by pointing out that S3 (equivalently, D3) is the smallest nonabelian group. It’s a good place to start when you’re wondering about nonabelian groups.

By the same token, the quaternion group is an interesting counterexample. I haven’t explained the terminology “normal subgroup”, and won’t for a while, but….

If a group is abelian, then every subgroup is normal.

The converse (If every subgroup is normal, then the group is abelian) is false, and the quaternion group is a counterexample: every subgroup of the quaternion group is normal, but the group is not abelian.

Oh, let me close with another counterexample: the group A4, which is of order 12, does not have a subgroup of order 6. It is a major theorem (Lagrange’s) that

the order of a subgroup divides the order of the group;

but there need not be a subgroup corresponding to every divisor. I’ll get to this.

But let me be clear: Lagrange’s theorem says that any subgroup of A4 must have order 1, 2, 3, 4, 6, or 12. (Order 1 is the identity alone; order 12 is all of A4: these are improper subgroups.) The fact is that A4 has subgroups of all those orders except 6.

I think the next group theory topic will have to be homomorphisms and isomorphisms.