Observations about the symmetric groups

Recall that the nth symmetric group consists of all permutations of the set {1,…,n}.

An easier way to multiply elements. Let’s use (1 2)(2 3) again and see, working left to right, where each number is sent. Although it is arbitrary we’ll start with {1}.

So first we have that (1 2) sends 1 to the second position. As (2 3) sends the second position to the third position, we have that (1 2)(2 3) sends 1 to the third position i.e.

(1 3 …

and so we will now look where (1 2)(2 3) sends {3} (the number which starts in the third position). The first cycle, (1 2), does nothing to {3}. But the second cycle, (2 3), sends 3 to the second position i.e. we have

(1 3 2…

which means we want to see where (1 2)(2 3) sends {2}. Here we have that (1 2) sends it to the first position and then (2 3) leaves the first position alone. Hence {2} is sent to the first position. That completes our cycle! This shows us that (1 2)(2 3) = (1 3 2).

Before continuing: try the above but start with a different number, e.g. {2}. What do you think (1 2)(2 5) would be? How about (1 4)(4 3)? Check if your intuition is correct.

Hopefully this way of seeing the permutations gives you a quicker way of putting elements together. It also means we may just write the group elements of Sn rather than keep track of the set [1,…,n] on the left. If we want to make it clear that we are considering a right action, or to read from left to right, we could use X to represent this set. If you’re confused when looking at permutations or want some more practice before adopting this convention, using my [1,…, n] notation shouldn’t cause too much confusion (though you may need to define this notation as it is somewhat non standard). You may also like the following summary and alternative notation.

Writing an element in disjoint cycle notation. Any cycle in Sn represents a bijection on {1,…,n}. We know that composition of such bijections will produce another bijection on {1,…,n}. So all we need to do is to show that any such bijection can be written in disjoint cycle notation.

We did the example (1 2)(2 3) above. We’ll now generalise this. Let’s think about about permutation on {1,…,n} as a bijection, and call it g. We want to conclude that g can be written using our disjoint cycle notation. Let’s just follow the steps from above:

  • first work out {1}g. If 1 is fixed by g then we can just write down (1), otherwise
  • work out {{1}g}g, which is either 1 -we write down (1 {1}g)- or
  • work out {{{1}g}g}g, which is either {{1}g}g -we write down (1 {1}g {{1}g}g)- or…

and so on. This process will end after at most n steps. We then run the same process but start with the smallest number not yet accounted for i.e. the smallest element in

{1,…,n} \ {{1}gk | k a whole number}

until we have described where every element from {1,…,n} has been sent. From now on we may always assume that elements are in disjoint cycle notation.

Conditions for elements to commute. We’re going to investigate when elements commute in the symmetric group. Imagine we had two permutations g and h in Sn. First, picture the case where each permutation consists of a single cycle. If these were the same cycle, then they’d commute. Similarly for a general g and h, if g=h then they will commute: we’d be applying the permutation of g twice whether we write gh or hg. Is that it?

No! What about cycles whose support is disjoint (i.e. no number 1,…,n appears in a cycle of g and of h)? Before continuing: decide what will happen and try to justify your intuition.

Note that if z is not in supp(f) for a permutation f, then {z}f={z} i.e. it is fixed by f. Now, if supp(g) and supp(h) have no points in common, then x is in supp(g) implies that {x}gh={x}g. Similarly for any y in supp(h), we have {y}hg={y}h. Putting these facts together we have that

  • {x}hg={{x}h}g={x}g={x}gh for all x in supp(g)
  • {y}gh={{y}g}h={y}h={y}hg for all y in supp(h)
  • {z}gh={z}={z}hg for all z not in supp(g) or supp(h)

and so if g and h have disjoint supports (when written in disjoint cycle notation) then they commute. This means that when g is written in disjoint cycle notation we are free to move the cycles of g past each other: this distinct part commute within g. This means that if g and h contain a cycle a (or any powers of this cycle) then we may write g=g’a=ag’ and h=h’a=ah’ for some g’ and h’. If g’ and h’ commute then gh=ag’h’a=ah’g’a=hg. Similarly if g and h share any number of cycles then we may ‘factor these out’. Is that it?

No! Let’s consider g = (1 2)(3 4). By direct computation, this commutes with (1 3)(2 4) and also with (1 4)(2 3). In order to see why, note that gh=hg is the same as h-1gh=g.

Definition. Let G be a group and g be in G. Then f and g are conjugate in G if there is a h in G such that f=h-1gh. Also {h-1gh | h in G} are the conjugates of g in G.

An aside: conjugacy. The cycle notation we have produced plays very nicely with conjugacy. Have a go yourself at showing the following identity, which we’ll be using next.

Lemma. Let g = (i1 i2…ik) and h be an element of Sn. Then

h-1(i1 i… ik)h = ({i1}h  {i2}h  … {ik}h)

i.e. ((1 3)(2 4))-1(1 2 3 4)((1 3)(2 4)) = (3 4 1 2).

We may now use one of the great mathematical tricks: multiplication by 1 or, in the group theory sense, multiply by the identity element. We will do this to apply our lemma to g = (i11 i12…i1k)(i21 i22…i2k’)…(ir1 ir2…irk”’). First of all,

h-1(i11 i12…i1k)(i21 i22…i2k’)…(ir1 ir2…irk”’)h

and

h-1(i11 i12…i1k)hh-1(i21 i22…i2k’)hh-1…hh-1(ir1 ir2…irk”’)h

are equal, and so we can apply our lemma to each of the cycles in g.

Looking back at our example from before, the element (1 3)(2 4) sends g = (1 2)(3 4) to (3 4)(1 2) which is again equal to g. Thus any element which ‘permutes’ the cycles of g will commute with g. Other examples would be with, say g=(1 2 3)(4 5 6)(7 8 9) and then

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

all commute with g. Note that any h which does not permute the cycles of g (in any of the 3 ways discussed above) cannot satisfy h-1gh=g because of our lemma.

Definition. Let G be a group and g be an element of G. Then the centraliser of g in G, denoted CG(g), consists of all elements which commute with g. Specifically

CG(g):={h in G | hg = gh}.

Before continuing: for a given r-cycle, what is the inverse? Use this to work out an inverse to a general element in disjoint cycle notation.

Answer: given a permutation in disjoint cycle notation, we note that (1)(2)…(n) is the identity element and the inverse of (i1 i2…ik) is (ik ik-1…i1). Using the fact that disjoint cycles commute we may write an inverse of an element as the inverse of each of its cycles when it is written in disjoint cycle notation.

Last little exercise. Recall that a subgroup of a group G is a subset of the elements of the group which also form a group using the binary operation from G. A useful exercise is to think about how the previous groups that we have seen (i.e. Cn and Dn) are captured as subgroups of a symmetric group. Before continuing: write, in cycle notation, the permutations seen in C4 and D4. It may help to visualise them as permutations on our square (below). But is it true that D4 (and so C4) are subgroups of S5? Subgroups of Sn (where n ≥ 4)?

rotations1

Thanks again for reading.

Advertisements
Observations about the symmetric groups

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