Group Actions

November 16, 2010, 15:00
Filed under: Algebra, Math | Tags: algebra, graph theory, group theory, MaBloWriMo, Math, pretty pictures

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 “groups describe symmetry,” this is exactly what they’re talking about. Say we have a set, and some “symmetries” of that set. Pretty much any definition of “symmetry” will take it to be a bijection on the set, and we moreover expect to be able to undo symmetries, to compose them (associatively), and to use the identity map as a symmetry. These heuristics are just informal versions of the group axioms! The element we’ve been leaving out so far, though, is the set itself on which the symmetries are founded. We say that this symmetry group acts on this set. Below, let’s make this formal.

Given a group $G$ and a set $S$ , an action of $G$ on $S$ is a map $G\times S\rightarrow S$ , written $g\cdot s$ or just $gs$ , such that:

$e\cdot s=s$ for all $s\in S$ , where $e$ is the identity of $G$
$g\cdot (h\cdot s)=(gh)\cdot s$

That’s it. The identity acts as the identity map, and acting by two elements in a row is the same as acting by their product.

Technically, this is a left action because we’re acting on the left, and $S$ is called a left $G$ -set. A right action has the same identity property, but has instead $g\cdot (h\cdot s)=(hg)\cdot s$ . This looks weird, but it straightens out if you write the group elements to the right of the set elements: $(s\cdot h)\cdot g=s\cdot (hg)$ . These are not the same. One good way of thinking about the difference is that in a left action, we can treat the group elements like bijections on $S$ with composition as the group operation. On the other hand, we can go from a left action to a right action, and vice versa: simply define $s\cdot g=g^{-1}\cdot s$ . Because of this, I’m only going to be talking about left actions, but there are times when it’s just more convenient to write an action as right.

Examples. Actions are all about the examples. We can have any group act on any set by having all group elements act as the identity, but that’s pretty boring. we’ve seen some examples of group actions built into the definitions of certain groups: for example, the dihedral group $D_{2n}$ acts on a regular polygon with $n$ sides by rotation and reflection, which in fact give you all of its symmetries. (Prove this? What’s the order of $D_{2n}$ , and can we count the symmetries of a polygon by looking at its vertices?) The cyclic group $\mathbb{Z}_n$ acts on that same polygon just by rotation, and so you could say that it’s the group of orientation-preserving symmetries of that polygon. The symmetric group is, in a sense, the group of symmetries of the set $\{1,\dotsc,n\}$ .

But we don’t even need to think about geometry or combinatorics to get cool examples. A group’s a set, right? We have a pretty obvious action of $G$ on $G$ by left-multiplication: $g\cdot h=gh$ . We also have an action of $G$ on itself, or indeed any normal subgroup, by conjugation: $g\cdot h=ghg^{-1}$ . Or we could look at the left cosets of a subgroup $H$ , and act on them by left multiplication: $g\cdot aH=gaH$ . Or we could act on the subsets of cardinality $n$ by left multiplication. And so on. All of these are examples of a group’s internal symmetry.

And it doesn’t stop there: we can combine the geometrical and group-theoretical viewpoints, into something called the Cayley graph of $G$ . A bit of background: besides the graph of a function, the word “graph” has a second meaning in math. A directed graph or digraph is a pair of sets $(V,E)$ , where $V$ , called the vertices, is just a set, and $E$ , the edges, is a set of ordered pairs of elements of $V$ . Obviously, you’re just supposed to think of the vertices as points, and the edges as curves going from their first vertex to their second. The Cayley graph of a group $G$ is the graph that has a vertex for every element of $G$ , and, for every generator $a$ and group element $g$ , an edge from $g$ to $ag$ . An example for — what else? — $D_8$ is shown at left. The red arrows are left-multiplication by $r$ , and the blue arrows by $f$ . From this, we can just read off things like subgroups and cosets, and the way $r$ works backwards on “flipped” transformations.

But wait, this isn’t unique! It relied on our choosing a generating set for $G$ ! How do we tell what digraphs are Cayley graphs for $G$ — or, indeed, Cayley graphs at all? The answer is quite simple: just as as $G$ acts on itself by left multiplication, it has to act on its graph by left-multiplication as well. Moreover, the action of each group element has to be a symmetry of the graph — that is, it has to biject on vertices and edges, and the image of each edge $(v_0,v_1)$ must be the edge $(gv_0,gv_1)$ . But certain symmetries can’t happen: for instance, no symmetry besides the identity can send any vertex of the graph to itself (the action is free). Other symmetries have to happen: for any two vertices, there has to be a symmetry sending the first to the second (the action is transitive).

Theorem (Sabidussi¹). A digraph is a Cayley graph for $G$ iff $G$ has a free transitive action on it by symmetries.

Proof. One direction is easy: it’s obvious that any Cayley graph of $G$ has all the necessary properties. Now suppose that we have a graph with the necessary properties. Pick one vertex and label it $v_e$ . By transitivity, for any other vertex $v$ , there’s an element of $G$ whose action sends the $v_e$ to $v$ ; if there are two such elements $g,h$ , then $gh^{-1}$ fixes $v_e$ , so it must be the identity. So there’s a unique element of $G$ sending $v_e$ to each other vertex. Just label the vertex equal to $g\cdot v_e$ by $v_g$ , and label the edge between $v_g$ and $v_h$ by $hg^{-1}$ . $\square$

In particular, if two groups act freely on a graph by symmetries, we can perform the above labelling process for both of them at the same time. This gives a bijection between their elements, and a bijection between the generating sets defining the edge-labels. It should be clear that these bijections together define an isomorphism of the groups. So a Cayley graph uniquely determines a group, though not every graph is a Cayley graph, and a group itself can have several Cayley graphs.

I wanted to prove that subgroups of free groups were free using Cayley graphs, but I’d been thinking of a proof that used more topology than we know. There’s another proof, from J. P. Serre, that only uses graph theory, but it’s somewhat involved and I don’t want to make this post too long. So you guys can see this math at work, I think I’ll put it in its own post, either today or sometime soon.

¹Sabidussi, Gert. “On a Class of Fixed-Point-Free Graphs.” Proceedings of the American Mathematical Society, Vol. 9, No. 5, Oct. 1958. pp. 800-804.

About these ads

1 Comment

1 Comment so far
Leave a comment

[...] of Free Groups are Free 28 12 2010 Okay, first post for a while. As I promised quite a while back, let’s prove together that subgroups of free groups are free. It’s [...]

Pingback by Subgroups of Free Groups are Free « Gracious Living December 28, 2010 @ 07:33

RSS feed for comments on this post. TrackBack URI

Gracious Living

Categories

Archives

Links

Follow “Gracious Living”

Gracious Living

Categories

Archives

Links

Share this:

Like this:

Leave a Reply Cancel reply

Follow “Gracious Living”