Symmetric Groups


Symmetric Groups
----------------

S₄ = permutations of {1,2,3,4}

|S_n| = n!

∴ |S₄| = 24 elements.

These are 1234, 1342, 4321 etc. etc.

Permutations can be regarded as the map,

f: {1,2,3,4} -> {1,2,3,4} 

Where f is a function.

Treating the permutations as functions allows us 
to define multiplicatio. 

Consider f: 1234 -> 1342 and g: 1234 -> 4321

The corresponding functions are:

f(1) = 1, f(2) = 3, f(3) = 4, f(4) = 2

g(1) = 4, g(2) = 3, g(3) = 2, g(4) = 1

The compositions are:

f o g(1) = 2, 

f o g(2) = 4 

f o g(3) = 3 

f o g(4) = 1

This is sometimes written in shorthand as:

 -       -     -       -     -       -
| 1 2 3 4 | . | 1 2 3 4 | = | 1 2 3 4 |
| 1 3 4 2 |   | 4 3 2 1 |   | 2 4 3 1 |
 -       -     -       -     -       -

The identity permutation is:

 -       -
| 1 2 3 4 |
| 1 2 3 4 |
 -       -

The inverses can be obtained by interchanging 
the 2 rows (and sorting the order). For example,

 -       -       -       -     -       -
| 1 2 3 4 |^-1 = | 1 3 4 2 | = | 1 2 3 4 |
| 1 3 4 2 |    | 1 2 3 4 |   | 1 4 2 3 |
 -       -       -       -     -       -

Therefore,

 -       -     -       -     -       -
| 1 2 3 4 | . | 1 2 3 4 | = | 1 2 3 4 |
| 1 3 4 2 |   | 1 4 2 3 |   | 1 2 3 4 |
 -       -     -       -     -       -

Multiplication enables us to construct a Cayley 
table as follows:
     
  x  | 1234 | 4321 | ....
-----+------+------+------
1234 | 1234 | 4321 | ....
-----+------+------+------
1342 | 1342 | 2431 | ....
-----+------+------+------
.... | .... | .... | ....

Completing the entire table shows that the closure
property is satisfied.

Cycle Notation
--------------

Another notation used is cycle notation.  
Consider:

 -               -
| 1 2 3 4 5 6 7 8 |
| 5 4 7 6 2 8 3 1 |
 -               -

(1 -> 5 -> 2 -> 4 -> 6 -> 8 -> 1 and 3-> 7

(1 5 2 4 6 8)(3 7)

Cayley's Theorem
----------------

Every finite group is isomorphic to a subgroup 
of the symmetric group.   



Cayley's theorem can be understood as a group 
action on itself whereby multiplying an element 
on the left by another element produces another
element.  We can think of the ith row of the 
Cayley table as defining a function, f_i which 
takes j to i.j.  This function can be seen as 
a permutation of the elements of the group 
and as a element of the symmetric group.

Example:

Consider the symmetry group of the square, D₄:

D₄ = {R₀,R₉₀,R₁₈₀,R₂₇₀,m₁,m₂,δ₁,δ₂}

R₀ = 1234

R₉₀ = 2341

R₁₈₀ = 3412

R₂₇₀ = 4123

m₁ = 2143

m₂ = 4321    

δ₁ = 3214

δ₂ = 1432

The corresponding Cayley table (partial) is:

  x  | 1234 | 2341 | 2143  ... 
-----+------+------+------
1234 | 1234 | 2341 | 2143  ...
-----+------+------+------
2341 | 2341 | 3412 | 3214  ...
-----+------+------+------
2143 | 2143 | 1432 | 1234  ...
  .      .      .      .
  .      .      .      .
  .      .      .      .

If the entire table is completed it is easy to
see that each row is a realization of D₄ as a 
subgroup of S₄.

Redshift Academy