Identity Element

Date: 02/09/2002 at 15:22:28
From: bill Flynn
Subject: modern algebra

Let f be an element of S_n.  Show that there exists a positive integer 
k such that f^k = i, the identity function.  

Thank you very much, 

Bill

Date: 02/09/2002 at 15:42:32
From: Doctor Paul
Subject: Re: Modern algebra

Hi Bill, 

As a consequence of Lagrange's Theorem, a random element of *any* 
group (not just S_n) raised to the order of the group is the identity 
element. So choose k = |S_n| = n! and you're done. 

See if you can prove that if a is a random element of a group G, then 
a^|G| = i. (Use Lagrange's theorem.)  If you need help, try searching 
our archives; write back if you can't find it.

I hope this helps.  Please write back if you'd like to talk about this 
more.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/   

Date: 02/11/2002 at 16:08:55
From: Bill Flynn
Subject: Modern algebra

Dr. Paul, thank you for your help. But we have not covered groups yet.  
We are still in the first chapter of our textbook, dealing with 
functions, sets, and mappings. Is there a simpler explanation for this 
problem?

Date: 02/11/2002 at 17:28:50
From: Doctor Paul
Subject: Re: Modern algebra

Hi Bill, 

I'm not sure what notation you use to represent elements of S_n.
An element of S_n will be a permutation of the set 

  {1, 2, 3, ..., n}.

So one way to write this is in matrix form:

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

This says that the permutation takes 1 to 3, fixes 2, takes 3 to 4, 
and takes 4 to 1.

An alternate notation is to write: 

  (1 3 4)

This is read as 

  1 goes to 3, 3 goes to 4, 4 goes to 1

and sometimes written as 

  1 -> 3, 3 -> 4, 4 -> 1.  

Since 2 is missing, we know that this permutation fixes 2.  We can 
also write:

  (1 3 4)(2)

How would you compose two permuations?

Suppose you had 

  (1 4 3)(3 2 1 4)

Start with the permutation on the right, and consider the first 
element: 1 goes to 4. But then move to the permutation on the left and 
see what happens to 4: it goes back to 3. So the end result is that 1 
gets moved to 3. 

Now look at 3. 3 goes to 2, which gets fixed in the left permutation, 
so in the end 3 goes to 2.

Now look at 2. 2 goes to 1, but 1 goes to 4, so in the end, 2 goes to 
4. 

Now look at 4. 4 goes to 3, which goes to 1, so 4 goes to 1. 

Thus 

   (1 4 3)(3 2 1 4) = (1 3 2 4)

The length of a cycle is the number of digits it contains. So 

  (1 4 3) 

is a three cycle, 

  (2) 

is a one cycle, and 

  (3 2 1 4) 

is a four cycle.

Consider the element 

  s = (1 5 4 2) 

in S_6.  See if you can convince yourself that s^4 = i, that is, 

  (1 5 4 2)(1 5 4 2)(1 5 4 2)(1 5 4 2) = (1)(2)(3)(4)(5)(6)

It might help you to write 

  (1 5 4 2) 

as 

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

and then verify that

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

is the identity element in S_6 (i.e., the permutation that fixes all 
elements of S_6).

Why did raising this to the 4th power work? Because the cycle length 
is four.

An n-cycle composed with itself n times will always give the identity 
permutation. This is nice, but it's not going to completely solve the 
problem. Why not? Because some elements can't be written as n-cycles.

Consider the following element of S_5:

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

In shorter notation, this permuation is:

 s = (1 3)(2 4 5)

Here we have a perfectly legitimate element of S_5 written as a 
product of a two cycle and a three cycle. Let's consider powers of 
this element to see when we get the identity. We can start with s^2:

  s^2 = (1 3)(2 4 5)(1 3)(2 4 5) 

If we find that s^2 takes some number k to a number that isn't k, then 
we know that s^2 isn't the identity permutation and we'll stop short 
of computing all of s^2 and move on to s^3.

Let's see:

  1 -> 3 -> 1 (we're okay so far)
  2 -> 4 -> 5

So s^2 takes 2 -> 5, which means that s^2 isn't the identity.  What 
about s^3?

  s^3 = (1 3)(2 4 5)(1 3)(2 4 5)(13)(2 4 5)

Let's see: 

  1 -> 3 -> 1 -> 3

Already we see that s^3 takes 1 -> 3 and hence can't be the identity.  
Do you see that s^k will never be the identity if k is odd?  

This is because s^k will always send 1 -> 3 if k is odd. Thus the only 
powers of k that we have to consider from here on out are even powers 
of k. What about s^4?

  s^4 = (1 3)(2 4 5)
         (1 3)(2 4 5)
          (1 3)(2 4 5)
           (1 3)(2 4 5)

Let's see: 

  1 -> 3 -> 1 -> 3 -> 1
  2 -> 4 -> 5 -> 2 -> 4

No good.  So s^4 doesn't work either.

Let's consider s^6:

  s^6 = (1 3)(2 4 5)
         (1 3)(2 4 5)
          (1 3)(2 4 5)
           (1 3)(2 4 5)
            (1 3)(2 4 5)
             (1 3)(2 4 5)

Check it yourself and see that s^6 is the identity. So why does s^6 
work?

Notice that 

  (1 3)^2 = identity

and that 

  (2 4 5)^3 = identity

So in order to make both of these the identity, we need to make sure 
that we are simultaneously squaring and cubing. This requires taking 
the sixth power.

In other words, we choose 6 because 6 is the product of the cycle 
lengths.

But what if we had 

  (1 3)(2 6 4 5) 

as an element of S_6?  Do we need to raise this to the 2*4 = 8th power 
to get the identity? It turns out that we don't. The 8th power will 
work, but is a bit of an overkill because the 4th power is enough.  

Notice that raising to the 4th power fixes each of the elements of (2 
6 4 5) since it is a 4-cycle and raising to the 4th power fixes all of 
the elements of (1 3) since its elements will be fixed by any even 
power. (Verify this with an example if it's not clear why this is the 
case.)

So why did we need 2*3 in the first example, while 2*4 was too big in 
the 2nd example? It turns out that the LCM of the cycle lengths will 
be the smallest power that will give the identity.

Recall that 

  LCM(a,b,c) = LCM(LCM(a,b),c) 

and you can apply this formula inductively if you need to compute the 
LCM of 4 or more numbers.

So if you have

  s = (1 4 5)(6 2 8 7)(9 3 10 11 12) 

which is an element of S_12, the smallest power that will produce the 
identity is 

  LCM(3,4,5) = 3*4*5 = 60

In this case, since the numbers are all relatively prime, the LCM is 
just the product. But if 

  s = (1 4 5)(6 2 8 7)(9 3 10 11)

then the smallest power that will produce the identity is

  LCM(3,4,4) = LCM(3,4) = 12.

Does this explain what's going on?  I hope so.  

Please write back if you'd like to talk about this some more.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/