## Monday, April 24, 2006

### Permutations and Symmetry Groups

One group that's particularly interesting to CS guys like me is called the symmetric group. The symmetric group is, in one view, the first step towards something called Category Theory, which has become very trendy in theoretical CS circles lately.

There isn't one symmetric group; the symmetric groups are finite groups, and for any given size N, there is a symmetric group of that size, called the symmetric group of degree N.

Symmetric groups are the "master" groups of something called permutation groups. Permutation groups are groups whose members are mappings between elements of sets of size N.

Just as a reminder: permutations are rearrangements of a set. The permutations of a set S are every ordering of all of the members of S. The number of permutations of a set of size S is S! (the factorial of S).

There are two ways of looking at a permutation group. One is sort of what you might expect from the name: for a permutation group over the set of numbers from 1 to N, the possible members are all of the ways you can re-order the numbers. For example, if you've got the set of integers from 1 to 3, the possible members of the permutation groups are:

{ (1->1, 2->2, 3->3), (1->1, 2->3, 3->2), (1->2, 2->1, 3->3), (1->2, 2->3, 3->1), (1->3, 2->1, 3->2), and (1->3, 2->2, 3->1) }

The other way of looking at the possible values in a permutation group over 1 to N is as the set of all total, one-to-one functions from (1..N) to (1..N). If you look at that list up above, it does include every possible total one-to-one function from {1, 2, 3} to {1, 2, 3}.

The set of pemutation values become a group when we assign the group operation, and show that it has identity elements and inverses.

The group operation is straightforward: composition of the permutations. I think it's easiest to understand that if you think of the group members as functions; then the operator is just function composition: given two members f(x) and g(x), then f*g = f(g(x)).

So, for example, let's look at two members, F=(1->2,2->3,3->1) and G=(1->1,2->3,3->2).
• G(1)=1; F(1)=2, so F*G(1)=2.
• G(2)=3; F(3)=1, so F*G(2)=1.
• G(3)=2; F(2)=3, so F*G(3)=3.
So the composition F*G=(1->2,2->1,3->3).

The identity value should be pretty obvious - it's the identity function, which for all i maps i -> i. So for a the permutation group of order 3, the identity value is {(1->1),(2->2),(3->3)}.
And finally, inverses: just reverse the direction of the arrows in the mappings: for example, the inverse of (1->3,2->1,3->2) is (3->1,1->2,2->3), which can also be written (1->2,2->3,3->1) - and which is one of the members of the group.

The symmetric group of degree N is the permutation group containing all of the possible permutations over 1..N.

The symmetric group has a lot of really interesting properties. This is getting long, so for today, I'll just mention one really amazing one: every finite group is isomorphic to a subgroup of a symmetric group. (To remind you: a subgroup of a group G is a group whose members are a subset of the members of G.) The symmetric groups are a supergroup of every finite group!

That's exactly why they're so important: every possible symmetry property of a finite group is embedded in the structure of the symmetric group!

(Note: this post was corrected to remove a terminology error pointed out by poster Ivan M. I originally erroneously used the term "symmetry group" for "symmetric group". The error was a mistake dating all the way back to my group theory notebook from school! Thanks, Ivan, for catching it and being persistent about correcting me.)

• Not sure if you're aware of Mark-Jason Dominus' blog, but he occasionally forays into math and is currently looking a symmetry and permutation as well, though from a different angle. He's more of a giften amateur enthusiast than professional math geek, but he also has a remarkable talent for explanation.

By  BMurray, at 10:16 PM

• To my knowledge, "the symmetric group [of degree n]" is the correct phrase [for the group of order n! consisting of all permutations of degree n], rather than "symmetry group". To me, the phrase "symmetry group" just means, well, the group of symmetries (automorphisms) of some mathematical object, and I think this is pretty standard among working mathematicians.

By  ivan m., at 12:24 AM

• Oh, and one request re. one of your earlier posts-- would you mind inserting the word "normal" into the definition of simple group? (A simple group is one that has no nontrivial *normal* subgroups.) Nonabelian simple groups always have nontrivial subgroups, but they are not normal. I know you were only mentioning simple groups in passing, but I guess I'm obsessive about these things.

By  ivan m., at 12:35 AM

• Gah! I just can't get away from category theory, can I?

By  Blake Stacey, at 4:50 AM

• Ivan:

My old school notes have "symmetry group"; so does Wolfram Mathworld. Wikipedia uses symmetric group the way you do, and "symmetry group" for a geometric group closed under composition. So I think it's a tossup :-)

Given that both seem acceptable, I'm going to stick with the one that I'm used to; if I try to change, I'll likely mess up and end up using both, which will be even more confusing.

By  MarkCC, at 8:27 AM

• blake:

I know exactly what you mean. I first got exposed to category theory back in grad school; and since then, it seems like no matter where I turn, there it is, staring me in the face again.

By  MarkCC, at 8:29 AM

• ivan:

I understand obsessiveness all too well :-) The earlier post now has the correction.

By  MarkCC, at 8:33 AM

• bmurray says:

"[Another blogger is] more of a gifte[d] amateur enthusiast than professional math geek"

Is the Good Math blogger a professional math geek? I thought he was a computer scientist. Professional math geeks tend to have papers indexed on MathSciNet; Mark Chu-Carroll does not.

markcc writes:

"My old school notes have 'symmetry group'; so does Wolfram Mathworld."

I believe that you're mistaken and that Mathworld calls the symmetric group the symmetric group and calls symmetry groups symmetry groups. See, e.g., this.

By  nat whilk, at 9:39 AM

• Mark:

re. "symmetry group": I don't think it's a tossup; I think you erroneously conflated two different terms in your notes. Wikipedia and Mathworld have the correct usages.

re. the definition of simple group: Your correction still has errors-- (1) commenter ray was the first to point out the original error, not me; (2) simple groups may have *simple* subgroups, but not *normal* ones; (3) the phrase "the normal ones need to be trivial" is bound to confuse those who don't yet know what "trivial" means (equal to the whole group or to the subgroup consisting of the identity alone).

By  ivan m., at 1:14 PM

• nat:

I am a computer scientist. I also believe that I am a professional math geek. I work for an industrial research lab - which means that I don't get to publish everything I do; and when I do publish, it's on the applications of math than on the pure math itself. I don't claim to be a research mathematician; I'm a computer scientist who works with and on applied mathematics.

For example, I've done rather a lot of work on applications of graph theory: static program analysis; graph-based representations of control flows and dependencies; isomorphic graph transformations; and fast ways of identifying maximal isomorphic subgraphs between graph pairs.

I've also done some work on program composition, which reduces to a kind of graph merge that needs to preserve a particular set of isomorphisms while not worrying about others.

I've done a lot of work involving the applications of various logics and calculi as models for programs; temporal logic, linear logic, lambda calculus, pi calculus, and CCS.

And finally, because of the programming-language focus of my work, I get hit with a whole lot of category theory and domain theory. I don't do any work with cat theory myself, but it's become so prevalent that you can't keep up on the lit without knowing at least a bit of it.

So do I qualify as a professional math geek? :-)

By  MarkCC, at 1:15 PM

• No one who thinks all groups are abelian qualifies as a professional math geek. Okay, so that's a harsh judgement, but harsh judgements are what this website is all about, isn't it?

By  nat whilk, at 2:05 PM

• ivan:

I know when I'm beaten :-) I don't know why I thought mathworld was using the terminology my way - probably just the old "you read what you expect to see, not what you actually see" problem that always screws up proofreading... I will correct it in the post, and try to remember to use the correct term.

WRT the correction on the post with the link to the great math song; it's a goofy post whose purpose is to link to a hysterically funny song performed by a bunch of math geeks. I understand obsessiveness, but I've also got limited time; I'm not going to go back and fix it *again*.

If it were a serious post which was intended to really teach people anything, I would have been much more careful writing it, and I would go back and correct it as many times as it took.

By  MarkCC, at 3:15 PM

• Mark:

Fair enough about not fixing the definition of simple group again, but the concept is elementary (simple? :) enough that it deserves to be understood properly (see the definition of normal subgroup).

Another matter of terminology (but more minor) is that the phrase "symmetric group" does not always refer to a finite group. The symmetric group on the set X is finite if and only if X is finite.

By  ivan m., at 4:21 PM

• The fact that every group embeds in a symmetric group is not really so amazing; what is more interesting is the question: what are the degrees of the interesting (the technical word is primitive) permutation representations? These correspond to the maximal subgroups of the given group.

What I find really amazing is the existence of the highly transitive Mathieu groups. These are sporadic simple groups which are naturally written as permutation groups of small degree, which means they are easy to play with!

By  ivan m., at 4:42 PM

• ivan:

Be patient! I'm trying to take things one step at time, building up intuition at each step.

I promise that I *will* eventually talk about subgroups, abelian groups, normal subgroups, trivial groups, maximal groups, symmetric groups over infinite sets, &c. I just want to get there in a way that keeps it fun, interesting, and understandable to folks who are interested in math, but who don't necessarily have the background/patience to handle the rapid-fire density of the common math-course presentation.

Finally - as I said, there are a lot of amazing and fascinating properties of the symmetry groups. I wanted to start off with one that has some depth to it, but which is easy to understand without needing to throw in even more definitions; in technical writing, my style is pretty definition-heavy; I'm fighting that in my writing here. And I was absolutely knocked off my feet when I first learned that all of the possible symmetries are embedded in something as simple as the symmetric group.

By  MarkCC, at 4:52 PM

• nat:

You're welcome to your opinion :-) But I still consider myself a professional math geek.

Group theory is fascinating to me, but it's not what I do every day. Even if it *were* my specialty, I don't think that it's a big deal to make a mistake while trying to explain a complicated abstract field of math to laymen - especially since I do my best to own up to my mistakes and correct them.

By  MarkCC, at 7:54 PM