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.)