Intro to Symmetric Groups

In this post I will introduce symmetric groups. Imagine you have four identical pennies and you arrange them into a row, and then you number the pennies as 1, 2, 3, and 4.

penny (1)

This collection of pennies is the “object” we will examine the symmetries of. Remember: symmetries are transformations you can apply to something, where the object is indistinguishable before and after the transformation. If something has rotational symmetry, you can rotate it and it looks the same. If something has mirror symmetry, you can reflect it and it looks the same.

These pennies, although they are circular, all have pretty complex patterns on them. They have no rotational symmetries, and no mirror symmetries. However, there is still something we can do: if we swap the positions of the pennies, the system will look the same as it does now! For example, if we swap 1 and 2:

pennyflip.png

Our object looks the same! The symmetries of this object are generated by shuffling these pennies around in various ways.

Let’s introduce some compact notation so I don’t have to keep putting up pictures of pennies. I will label each arrangement by just listing the order of the pennies!

  • The original arrangement at the top, I will call [1 2 3 4].
  • The second arrangement shown above will be [2 1 3 4].

With this notation, we can pretty easily list all of the possible arrangements:

 [1 2 3 4]  [2 1 3 4]  [3 1 2 4]  [4 1 2 3]
 [1 2 4 3]  [2 1 4 3]  [3 1 4 2]  [4 1 3 2]
 [1 3 2 4]  [2 3 1 4]  [3 2 1 4]  [4 2 1 3]
 [1 3 4 2]  [2 3 4 1]  [3 2 4 1]  [4 2 3 1]
 [1 4 2 3]  [2 4 1 3]  [3 4 1 2]  [4 3 1 2]
 [1 4 3 2]  [2 4 3 1]  [3 4 2 1]  [4 3 2 1]

This is just a list of every possible permutation of the set {1,2,3,4}. In general, for n objects, the number of permutations will be equal to n! (n factorial). In this case we have four elements, and 4! = 24, matching the number of elements listed above.


Permutations as Transformations

We can think about each of these permutations as a transformation  acting on our four pennies. For example, [2 1 3 4] is the transformation which swaps the first two pennies:

pennnny

It is an action you perform on your pennies. What [2 1 3 4] means is: swap the two pennies in positions #1 and #2.

Another example? [1 4 2 3] is the transformation which swaps the pennies around like this:

pennnn.png

What [1 4 2 3] means is: move the penny in position #2 to position #3, move the penny in position #3 to position #4, and move the penny in position #4 back to position #2.

Sometimes to make the things a bit clearer conceptually, these permutations will be written in a slightly different way. For example, [2 1 3 4] can be written as

[ 2 \ 1 \ 3 \ 4] = \left( \begin{matrix}1 & 2 & 3 & 4 \\ 2 & 1 & 3 & 4\end{matrix} \right)

The top row is where the pennies start, and the bottom row is where the pennies are moving to. You can see that penny #1 is moving to position #2, and penny #2 is moving to position #1. The other two pennies stay where they are.

Similarly, you can write [1 4 3 2] as:

[1 \ 4 \ 3 \ 2 ] = \left( \begin{matrix}1 & 2 & 3 & 4 \\ 1 & 4 & 2 & 3 \end{matrix} \right)

From this, it’s easy to see that the penny in position #1 stays where it is, and the other three pennies get shuffled around.

Meanwhile, the permutation [1 2 3 4] does absolutely nothing:

[1 \ 2 \ 3 \ 4 ] = \left( \begin{matrix}1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 \end{matrix} \right)

All four pennies stay where they are, and nothing happens.

Although this notation doesn’t add any more information, it makes the transformations a little more transparent and easier to grasp.


Combining Permutations

To form a group from our table of permutations, we need a rule for how to multiply them together.  We will accomplish this by performing these permutations one after the other.

Let’s say we have two permutations, a and b. The definition of multiplication is as follows:

a \cdot b = transform by b, then transform by a

As a concrete example, below is shown the product of [1 4 2 3] and [2 1 3 4]:

pennyny

We first applied the permutation [2 1 3 4], followed by the permutation [1 4 2 3], and we ended up with a new permutation [2 4 1 3]. What we have shown above is the fact that

[1 \ 4 \ 2 \ 3] \cdot [2 \ 1 \ 3 \ 4] = [2 \ 4 \ 1 \ 3]

Combining two permutations together gives you another permutation! That’s exactly what we want. For another example, let’s try this product again, but in reverse order:

pennyrev.png

What we have shown above is the fact that

[2 \ 1 \ 3 \ 4] \cdot [1 \ 4 \ 2 \ 3] = [4 \ 1 \ 2 \ 3]

Notice that [2 \ 1 \ 3 \ 4] \cdot [1 \ 4 \ 2 \ 3] \ne [1 \ 4 \ 2 \ 3] \cdot [2 \ 1 \ 3 \ 4] ! That is, the order of multiplication matters!  This means you have to be careful when you are multiplying permutations together.


Cycle Notation

There is another notation that is often used to characterize these kind of permutations. Let’s take another look at the element

[1,4,2,3] = \left( \begin{matrix}1 & 2 & 3 & 4 \\ 1 & 4 & 2 & 3\end{matrix} \right)

What this permutation does is:

  • The penny in position #2 moves to position #4 (2 \rightarrow 4)
  • The penny in position #3 moves to position #2 (3 \rightarrow 2)
  • The penny in position #4 moves to position #3 (4 \rightarrow 3)

So, combining all of the information above, we could think of this permutation as the following mapping:

2 \rightarrow 4 \rightarrow 3 \rightarrow 2

This is the essence of cycle notation, to simply list where each position is mapped to. Because position #1 just stays where it is, we don’t bother to include it. In cycle notation, this permutation would be labeled:

[1 \ 4 \ 2 \ 3] =  (2 \ 4  \ 3) = (3 \ 2 \ 4 ) = (4 \ 3 \ 2 )

Each position is moved to the new position to its right, and the rightmost position “wraps around” and is mapped to the first number.  Because of this “wrap around” convention, there are typically several ways to write a certain permutation (as shown above). Essentially, only the order matters , from left to right.

Let’s try applying this notation to our other example, [2 1 3 4]:

[2 \ 1 \  3 \  4] = (1 \ 2) = (2 \ 1)

Position #1 is mapped to position #2, and position #2 is mapped to position #1.

There are other situations where you need more than once cycle to build a permutation. For example, let’s look at [2 1 4 3]. This permutation swaps positions #1 and #2, but it also swaps positions #3 and #4. We could write this as follows:

[2 \ 1 \ 4 \ 3 ] = ( 2 \ 1 ) (4  \ 3)

This permutation is a product of two swaps. One can show generally that every permutation can be written as a product of disjoint cycles like this.


General Symmetric Groups

What we have discussed so far is the symmetric group of four objects, or S_4, but all the notation and logic I have listed applies to larger symmetric groups as well. For example, if we had five pennies instead of four, our group would be S_5 and we would have 5! = 120 elements. An example of one of the elements:

[1 \ 3 \ 2 \ 5 \ 4] = \left( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 1 & 3 & 2 & 5 & 4 \end{matrix} \right) = (3 \ 2 ) ( 5 \ 4)

Shown represented with the different notations I’ve mentioned.

In general, the symmetric group of n objects S_n will have n! elements, since there are n! different ways to arrange the objects.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s