Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Proving That a Symmetric Group on a Finite Set Is Not Cyclic If the Set Has More Than Two Elements

Date: 01/11/2010 at 17:35:20
From: Tom
Subject: Abstract Algebra (college math)

A group is cyclic if an element, g, of the group generates the entire 
group in the sense that if h is any other element of the group, then, 
for some k,

   h = g^k = g * g * g * ... * g

Show that the symmetric group on a finite set, S, is not cyclic if 
the set has more than 2 elements.

Would this be correct?

For 2 elements, h and b, of a cyclic group, let h = g^x and b = g^y.

Then h*b = (g^x)*(g^y) = g^(x + y) = g^(y + x) = b*h.

So the cyclic group is Abelian.

Let a symmetric set S = {1, 2, 3, 4, 5, ....., n}.

Let A = {2, 1, 3, 4, 5, ....., n}.

Let B = {1, 3, 2, 4, 5, ....., n}.

Then A*B is not equal to B*A.  Therefore, the set is not commutative, 
and consequently it is not cyclic.  Right?

I've no idea if I answered the question.  I'm also not sure if I used 
the proper terms (I'm new to abstract algebra).  Were enough steps 
and information shown to answer the question?



Date: 01/12/2010 at 14:56:57
From: Doctor Carter
Subject: Re: Abstract Algebra (college math)

Hi Tom -

What you've written is very good -- excellent, in fact, for a person 
new to algebra.

Let me quickly summarize your main ideas:

(A)  All cyclic groups are abelian
(B)  The symmetric group on n letters is not abelian if n > 2

Both these statements are true, and this is a very nice proof.  But 
there's a detail in your work which is incorrect.  Let me give some 
comments on your proof of (B):

1)  When you refer to S, call it "the symmetric group on the set {1, 
2, ..., n}" rather than "the symmetric set...."  The set {1, 2, ..., 
n} has n elements.  S has n! (n factorial) elements and S is a group, 
not just a set.  These are not the main problem, just nits.  But I 
mention them.

2)  When you say "let A = {2, 1, 3, 4, 5, ....., n}" I'm assuming you 
want A to be a certain n-cycle.  Use parentheses rather than set 
braces in your notation for cycles.  Reserve set braces for sets.  
Again, this is just a nit.

3)  Your idea, if I understand correctly, is to show that the n-
cycles (2, 1, 3, 4, ..., n) and (1, 3, 2, 4, ..., n) do not commute.  
Finding a pair of elements in S which do not commute is exactly what 
you want to do, but these two don't quite do it for you, and this is 
the real mistake in your work.  Notice that when n = 3, your two 
cycles are (2, 1, 3) and (1, 3, 2).  These notations actually 
represent exactly the same cycle; it's the function f:{1, 2, 3}-->{1, 
2, 3} given by f(1) = 3, f(2) = 1, and f(3) = 2.  Since the element f 
of S commutes with itself (or any power of itself), the elements you 
give *do* commute when n = 3.

So there's an important detail which you need to fix.  Can you show 
instead that the 2-cycles (1, 2) and (1, 3) fail to commute?

Cheers and best wishes,

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



Date: 01/12/2010 at 16:06:18
From: Tom
Subject: Abstract Algebra (college math)

Hi Doctor Carter,

In the second part, I'm not sure what you mean by "n-cycles"; there's 
so many definitions out there, it is sometimes confusing to know 
which one to use.  I see the problem you pointed out in my set; would 
it make more sense if I said

   Sn = group of permutations of (1, 2, 3, 4, 5, ..., n)

and then let

   A = (1, 2, 3, 4, 5, ..., n) 

and 

   B = (1, 3, 2, 4, 5, ..., n) ?

I'm trying to show that A*B is not the same as B*A by using what I 
showed earlier in the first part in a general way (I don't want them 
to commute).  Does this show that the finite set, S, is not cyclic?

Thanks for replying :)

Tom



Date: 01/12/2010 at 20:10:03
From: Doctor Carter
Subject: Re: Abstract Algebra (college math)

Hi Tom -

1)  It's fine to call Sn the "group of permutations of the set {1, 
2, ...,n }.  Use curly brackets here, because you're talking about a 
SET of elements, and we use curly brackets to denote sets in 
mathematics.

2)  When you define A, I assume you mean it to be the function in Sn 
which sends 1 to 2, 2 to 3, 3 to 4, ..., (n - 1) to n, and n back to 
1.  This function A permutes the n elements of the set {1, 2, ..., n} 
cyclically and is an example of what's called an n-cycle.  If n 
happens to be 3, A will be the 3-cycle (1, 2, 3) which sends 1 to 2, 
2 to 3, and 3 to 1.  So far, so good.

3)  The function B you define next appears to be different from A, so 
that's an improvement over your original choices.  I understand what 
B is when n is at least 4, but what value does B have if n = 3?  The 
notation doesn't make it clear. Perhaps in the case n = 3, you want B 
to be (1, 3, 2)?  This would be logical, but something unfortunate 
happens: If A = (1, 2, 3) and B = (1, 3, 2), then A and B commute!  
In fact, in this case, B = A^2.  You should try to show this; it will 
help you understand more about how permutations work.

So you've still got some trouble.  You'd like to find functions A and 
B in Sn which don't commute, and you'd like to do this whenever n is 
at least 3.  If you succeed, you will have shown that Sn is not an 
abelian group, so not cyclic.

But the candidates you have given so far for A and B do not do the 
job.  You need new candidates, and I suggested possible candidates in 
my first response.  When I suggest that you let A = (1, 2), the 
function in Sn that I'm talking about is the function A for which
A(1) = 2, A(2) = 1, and A(k) = k for all k between 3 and n.  The 
function B = (1, 3) takes these values: B(1) = 3, B(2) = 2, B(3) = 1, 
and B(k) = k for k between 4 and n.

It is possible (by computing tables of values) to show that functions 
A and B do not commute.  Try hard to show this.  I'll give you a 
hint:  AB = (1, 3, 2).  Can you compute BA?

Keep at it; you'll definitely get it.  Write back if you still need 
help.

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



Date: 01/12/2010 at 20:59:17
From: Tom
Subject: Abstract Algebra (college math)

Hello again, Doctor Carter,

Earlier you said:

If A = (1, 2, 3) and B = (1, 3, 2), then A and B commute!  In fact, 
in this case, B = A^2.

I don't see how you arrived at B = A^2 in that case.

Also, when I'm trying to find finite sets, aren't those A and B, 
which you keep calling as "functions"? 

Is it enough to show when n = 2 (2-cycle), A = {1, 2} and B = {1, 3}, 
where A*B is not B*A? Isn't that still solving for only 2 elements in 
the symmetric group on the finite set S?

Actually, this brings me back to the same problem above: how can I 
actually multiply sets like this and still get a product?

Hopefully I'm not losing sight of solving the original problem. And 
thanks again for taking the time to help me,

- Tom




Date: 01/12/2010 at 23:19:35
From: Tom
Subject: Abstract Algebra (college math)

Hi, Doctor Carter.

I'm not sure if giving values like that would solve the original 
problem.  It looks confusing, and the notation is completely new to 
me (they haven't been covered yet in my class).  Would it be enough 
to solve the problem if I said this?

Sn = set of permutation of {1, 2, 3, ... , n} and A is the 
permutation that swaps 1 and 2.

Let B be the permutation that swaps 2 and 3.

Then A*B is not equal to B*A.  Symmetric groups are not commutative, 
thus not cyclic.

Would I really need to explicitly use that example you suggested?

A = (1, 2)  and B = (1, 2, 3)
A*B = (1, 3, 2)
B*A =
(1, 2, 1, 2, 3)
(2, 5, 2, 1, 1)

- Tom



Date: 01/13/2010 at 01:26:25
From: Tom
Subject: Abstract Algebra (college math)

Doctor Carter --

This is my third spontaneous follow-up without reply.  Sorry; I got 
excited!

I couldn't solve the A and B defined in your second reply; it was too 
hard for me to do with 3 numbers, so I used an easier example:

For the symmetric group Sn, let n = 3, A = (1, 2) and B = (2, 3).

Then AB = (3, 2, 1) and BA = (1, 2, 3).

Thus AB and BA are not commutative!

Is this correct for the second part of the solution?  Is the 
symmetric group on the finite set S now shown to be not cyclic if 
there's more than 2 elements?  I have a good feeling about this one!

Sorry for the excessive replies.

Tom



Date: 01/13/2010 at 09:03:01
From: Doctor Carter
Subject: Re: Abstract Algebra (college math)

Hi Tom -

It looks like you've been making good progress while I've been 
sleeping!

You're right to feel good about things now.  Many mathematicians, and 
your teacher may be one of them, will agree exactly with everything 
you've said just now.  In fact, I agree with it too, but I need to 
point out that you are getting different answers for AB and BA than I 
would.  The reason for this, though you may not realize it, has to do 
with how we represent functions.

If A and B are functions from the set {1, 2, 3} to itself, I write 
the value of A on the element x as A(x).  And when I talk about AB, I 
mean the function whose values are computed using function 
composition in this way:

   (AB)(x) = A(B(x))

For me, the function on the right acts first.

But this is only a convention, and there have been famous 
mathematicians (among them, Samuel Eilenberg, an influential 20th 
century algebraic topologist) who advocate letting functions operate 
from the right.  Using this convention, the value of a function A on 
the element x is written (x)A and function composition now happens in 
the opposite order:

   (x)(AB) = ((x)A)B

The function A, which is on the left, acts first.

You are using this convention in the argument you give.  It's 
completely valid, so what you've written is CORRECT!  But I want you 
to be aware of the convention you're using, since the majority of 
mathematicians use the other convention, where functions are written 
to the left of their argument and where the rightmost of two 
functions being composed is the once which acts first.

Let me try to consolidate things now, using the more common 
convention.

1)  The group Sn consists of all the bijective functions from the set 
{1, 2, ..., n} to itself.  The group operation in Sn is composition 
of functions.  "Bijective" means one-to-one and onto.  In particular, 
if F is an element of Sn and x and y are different elements of
{1, 2, ..., n}, then F(x) and F(y) are not equal.

2)  If n is at least 3, then Sn contains the following two functions 
(and more):  

The function A whose values are given by A(1) = 2, A(2) = 1, and
A(x) = x when x is not 1 or 2.

The function B whose values are given by B(1) = 1, B(2) = 3, 
B(3) = 2, and B(x) = x for x not equal to 2 or 3.

3)  We can compose these functions.

AB is the function whose values are given as follows:
   (AB)(1) = A(B(1)) = A(1) = 2
   (AB)(2) = A(B(2)) = A(3) = 3
   (AB)(3) = A(B(3)) = A(2) = 1
   (AB)(x) = A(B(x)) = A(x) = x  if x is not 1, 2, or 3

BA is the function whose values are given as
   (BA)(1) = B(A(1)) = B(2) = 3
   (BA)(2) = B(A(2)) = B(1) = 1
   (BA)(3) = B(A(3)) = B(3) = 2
   (BA)(x) = B(A(x)) = B(x) = x  if x is not 1, 2, or 3

4)  The functions AB and BA are not equal!  So the group Sn is not 
abelian when n is 3 or greater.  And if it's not abelian, it cannot 
be cyclic.

5)  [CONVENTION]  I and many others use the cycle notation (1, 2, 3) 
to represent the function (AB) given above, which sends 1 to 2, 2 to 
3, and 3 to 1. Likewise, I use (1, 3, 2) to represent the function 
(BA) which, sends 1 to 3, 3 to 2, and 2 to 1.

This has been a very long reply.  Let me finish with just one more 
calculation, relating to a question in one of your earlier replies:  
the meaning of (1, 2, 3)^2.

6)  Let C be the function from {1, 2, 3, ..., n} to {1, 2, 3, .., n} 
whose values are given by C(1) = 2, C(2) = 3, C(3) = 1, and C(x) = x 
when x is not 1, 2, or 3.  Then C^2 has the following values:

   (C^2)(1) = C(C(1)) = C(2) = 3
   (C^2)(2) = C(C(2)) = C(3) = 1
   (C^2)(3) = C(C(3)) = C(1) = 2
   (C^2)(x) = C(C(x)) = C(x) = x  when x is not 1, 2, or 3

C^2 sends 1 to 3, 3 to 2, and 2 to 1.  I and many others use the 
cycle notation (1, 2, 3) to represent C and (1, 3, 2) to represent 
C^2.

I hope this has been helpful!  Congratulations if you're still 
reading!  And let me say again that you are right to feel good about 
this problem -- the last things you had to say were exactly right; 
they just assumed a different notational convention.

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



Date: 01/13/2010 at 15:43:04
From: Tom
Subject: Abstract Algebra (college math)

Hello again Doctor Carter,

Thanks for letting me know about that convention, that should clear 
up future confusion.

Thank you again for all your help!!!

Cheers,

Tom



Date: 01/13/2010 at 15:47:51
From: Tom
Subject: Thank you (Abstract Algebra (college math))

My thanks goes to Doctor Carter who spent lots of time to give very 
thorough explanations on the thought process, notations and 
conventions used for abstract algebra, which is an intensely hard 
subject of math! Thanks so much!
Associated Topics:
College Modern Algebra

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/