wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Generators of the Alternating Group
        
(Message started by: william wu on Feb 2nd, 2004, 9:35pm)
Title: Generators of the Alternating Group
Post by william wu on Feb 2nd, 2004, 9:35pm
Show that when n is odd, the permutations (123) and (12...n) together generate An. Similarly, show that if n is even, (12) and (23....n) together generate An.

Hint:[hide] For n>=3, the 3-cycles generate An.[/hide]


Background Information:

An is called the alternating group of degree n. It is the subgroup formed by the even permutations of Sn. A permutation is "even" if it can be written as the product of an even number of transpositions. Transpositions are permutations of length 2 (e.g. (12) is a transposition).


Source: Groups and Symmetry by M.A. Armstrong, p. 31
Title: Re: Generators of the Alternating Group
Post by Barukh on Feb 5th, 2004, 8:28am

on 02/02/04 at 21:35:13, william wu wrote:
Show that when n is odd, the permutations (123) and (12...n) together generate An.

As both given permutations are even, they may potentially generate An…
[smiley=blacksquare.gif]
[hide]As William pointed out, An is generated by the 3-cycles of Sn.1 So, it is to show that the 2 given permutations generate every 3-cycle.

First, note that (12…n)(123)(12…n)n-1 = (12…n)(123)(12…n)-1 = (234), similarly, (12…n)(234)(12…n)-1 = (345) etc. 2

Next, assume we’ve got all 3-cycles from the set {1,2,…,k} together with the 3-cycle L=(k-1 k k+1). Then, for every i,
(i k k+1) = L (i k-1 k) L-1,

(i k-1 k+1) = L-1 (i k k-1) L,

(i j k+1) = L (i j k) L-1,    j < k-1.

This – together with the inverses – gives all 3-cycles from the set {1, 2, …, k+1}. Because we’ve got originally (123), we may gradually build all 3-cycles.[/hide]
[smiley=blacksquare.gif]


Quote:
Smilarly, show that if n is even, (12) and (23....n) together generate An.

Since (12) is an odd permutation, these two generate something different… Did you mean (123) instead?

1 To prove this, observe that there are just two distinct pairs of transpositions – (ij)(jk) and (ij)(kl). The first one is a single 3-cycle (ijk), and the second is a composition (ijk)(ilk).

2 Given two elements g, x of a group, the third element gxg-1 is called a conjugate of x w.r.t. g. Here’s an easy way to obtain conjugates in Sn: if x = (i1i2… im), then gxg-1 = (g(i1) g(i2)… g(im)).


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board