Group actions

In a previous post I discussed how the elements of a group could be seen as “acting” on other elements directly as if they were functions. There's a more direct way of getting at this, but it is so simple, it might be a bit of a disappointment. But we'll take things a bit further.

First, let's consider the group with the element 0, 1, and 2 where the binary operation is addition modulo 3. It is closed, associative, 0 is the identity element, and 1 and 2 are inverses of each other. It is a group.

;; save the real multiply
> (define real-multiply *)
real-multiply

> (define (* a b) (modulo (+ a b) 3))
*

> (* 0 1)
1

> (* 1 1)
2

> (* 2 2)
1

But the elements of the group aren't functions, they are integers. They cannot directly act on other elements:

> (1 2)
Error -- application of non-procedure object 1

There's a simple trick to get directly at the “action” of an element on another element. Just “curry” the * operator:

> (define (get-action operator element)
    (define (action other-element) (operator element other-element))
    action)
get-action

> (define action-of-1 (get-action * 1))
action-of-1

> (action-of-1 2)
0

> (action-of-1 1)
2

See, that's almost disappointingly simple. Of course the other elements in the group will have their own actions obtained in the same way:

>(define action-of-0 (get-action * 0))
action-of-0

>(action-of-0 1)
1

No surprise that the action of the identity element leaves things unchanged.

Let's consider a different group. This group also has 3 element, '(a b c), '(b c a), and '(c a b). The operator is a funny sort of list rotation: if the first argument is '(a b c), it doesn't rotate the second argument at all. If the first argument is '(b c a), it rotates the second argument left by one position. If the first argument is '(c a b) it rotates the second argument by two positions:

> (define (funny-rotate first second)
     (cond ((equal? first '(a b c)) second)
           ((equal? first '(b c a)) (rotate-left second))
           ((equal? first '(c a b)) (rotate-left (rotate-left second)))))
funny-rotate

> (funny-rotate '(a b c) '(b c a))
(b c a)

> (funny-rotate '(b c a) '(c a b))
(a b c)

You've probably noticed by now that this second group is a disguised version of the first group with

0 <=> (a b c)
1 <=> (b c a)
2 <=> (c a b)
(modulo (+ a b) 3) <=> (funny-rotate first second)

This is an example of an isomorphism between two groups.

Suppose, for the sake of argument, that this second group is just like it currently is, but it had a few more elements that funny-rotate knew how to handle. But otherwise everything else is the same. Then there would be elements that didn't have a one-to-one mapping. This wouldn't be an isomorphism but a monomorphism. These are both kinds of homomorphisms between groups. (The wall of terminology appears.)

Let's back away from the wall of terminology for a moment and go back to the action of an element. Notice that the action of an element is a function. It maps elements to elements. The action is actually a bit more abstract than that. We can swap out the elements with the elements of an isomporphic group. So the action-of-1 which carries 0->1,1->2, and 2->0 can be considered the same action that carries '(a b c)->'(b c a), '(b c a)->'(c a b), and '(c a b)->'(a b c). Even though 1 doesn't even belong to the same group as '(a b c), we can consider action-of-1 and action-of-bca to be the same thing.

The action is even a bit more abstract. We can swap out the operator of the action, too. Here we have to be careful to make sure we don't ruin the group structure when we do that. To give an example, consider the conjugate of some action on some argument: (conjugate (f g)) = (h f) where we've found the h that makes (h f) equal to (f g). Recall that h is equivalent to fgf-1. We can, without ruining the group structure, give each element in the group the action of conjugating it's argument. (Just to throw out a little more terminology, when a group element acts on other elements in the same group, it's called an automorphism.)

We can, if we are careful not to ruin the group structure, swap out both the operator and the elements of the action of an element. But let's not do that. Let's return to simply getting the elements of the group to act on each other by currying the operator. This is a nice, easy to understand automorphism. In our examples, our groups have three elements. You can imagine them as sitting on the corners of a triangle. One element is the identity element, it leaves everything alone. One element bring 0->1, 1->2, and 2->0 or the equivalent, and the final element undoes it, bringing 0->2, 1->0, and 2->1. If they were sitting on the corners of a triangle, one element rotates clockwise, one elements rotates counterclockwise, one element does nothing. These automorphisms simply permute the elements of the group. And it has to be so. Because each element has an inverse, we have to be able to determine what the “input” element was associated with the “output” element, so each unique input must lead to a unique output, which makes it a permutation.

Ok, one more thing. Permutations are associative. If you have a set of permutations that are closed, includes the identity and all the inverses, then you have a group of permutations (called the symmetric group, even though there are many because it depends on how many items you are permuting. Better to parameterize by the number of items and call it symmetric_n.) Cayley's theorem says that every group is a subgroup of the symmetric_n group acting on the elements. That is, every group has some symmetries associated with it. The symmetries can help you gain insight into the group. This is pretty remarkable: we started with foldable sequences with identity elements and inverse elements, and we ended up with deep connection to symmetries.

I just wanted to get to as far as Cayley's theorem, so I'll end this now. I hope there wasn't too much terminology, but I'm afraid there was enough abstraction to make me dizzy.