Generators and Defining Relations on the Symmetric Group of degree n

[wnorman27]

Homework Statement

I am working through MacLane/Birkhoff's Algebra, and in the section on Symmetric and Alternating groups, the last few exercises deal with generators and Defining relations for Sn (the symmetric group of degree n). These read:

11. Prove that Sn is generated by the cycles (1 2 ... n-1) and (n-1 n).
12. In Exercise 11 determine defining relations on these two generators.
13. Prove that Sn is generated by the transpositions (1 2), (2 3), ..., (n-1 n).
14. In Exercise 13 show that the generators t$_{i}$ = (i i+1), i =1,...,n-1 satisfy the defining relations

(t$_{i}$)$^{2}$ = 1
t$_{i}$t$_{j}$ = t$_{j}$t$_{i}$ if i-j≠±1
and
(t$_{i}$t$_{i+1}$)$^{3}$ = 1
and that this is a complete list of relations.

Homework Equations

Thm: Any permutation on n is a composite of transpositions.

The Attempt at a Solution

I believe I understand why/how the given generators do generate Sn in problem 11:
any transposition of elements (j k) can be constructed using the cycles x = (1 2 ... n-1) and y = (n-1 n) as (x$^{-j}$°y°x$^{j}$)°(x$^{-k}$°y°x$^{k}$)°(x$^{-j}$°y°x$^{j}$)

And by the theorem, we can represent any permutation (any element of Sn) as a composition of these transpositions.

and in problem 12:
the transposition (1 2 ... n-1) can be written as (n-1 n-2)...(4 3)°(3 2)°(2 1) and (n-1 n) is already of the given form, so the given transpositions can be combined to form the permutations of 11 which in turn generate Sn. What I am having difficulty with is what the process is for determining defining relations and then showing that they form a complete list of relations. Perhaps showing the order of each of the generators (x$^{n-1}$=1 and y$^{2}$=1) and how the generators "commute" with one another is standard? If so how in the world do you figure out what these additional relations are?

Thank you all, this is my first post, so feedback on the amount/quality of information given is welcome and appreciated.

 

[micromass]

Let us first show that the set of relations in (14) is complete.

What it means is that if $t_1,...,t_n$ are in a group G, if $t_i\neq t_j$ and if they satisfy the relations, then $G=S_n$. Can you agree with that or did you have a different definition of complete??

What I would do is apply Cayley's theorem to obtain that G is a subgroup of a certain symmetric group Sym(X) (note that X is possibly infinite).
So we can write $t_1,...,t_n$ as permutations. Now use the relations to see which permutations they are.

For example, from $t_1^2=1$, I can see that $t_1$ must be a disjoint product of transpositions. Use the other relations to obtain some useful results.

 

[wnorman27]

micromass,

I can agree with your definition of complete, though I'm still lost as to how one would show that our group G = Sn from the given information.

Also, t$_{i}$ are given explicitly as t$_{i}$ = (i i+1), so the fact that they are transpositions is clear.

I see how Cayley's theorem allows us to show that G is a subgroup of some Sym(x), but I don't understand how to restrict this x so that x = n. Maybe I'll try to show that G is a subgroup of Sym(n) and then that Sym(n) is a subgroup of G? Any suggestions? Thanks!

 

[micromass]

OK, let's try something different as my method seems to get complicated.

I think the easiest way to show this is by some sort of induction argument.

So let $G_n$ be the group generated by the elements $t_1,...,t_n$. We wish to show that $G_n$ is isomorphic to $S_{n+1}$.

First, find a surjective group homomorphism $\varphi:G_n\rightarrow S_{n+1}$.

It remains to show that $|G_n|\leq (n+1)!$. This can be done by induction.

Assume that $|G_{n-1}|\leq n!$. Write for convenience $G_{n-1}$ generated by $t_1,...,t_{n-1}$ and write $G_n$ generated by $s_1,...,s_n$.

Define $\psi:G_{n-1}\rightarrow G_n$ by $\psi(t_i)=s_{i+1}$. Is this well-defined?
Let H be the image of $\psi$, then $|H|\leq (n-1)!$. It remains to be shown that $|G_n/H|\leq n+1$.

Define $H_0=H,~H_1=s_1H,...,H_n=s_ns_{n-1}...s_1H$. Show that $\{H_0,...,H_n\}$ are exactly the cosets of $G_n$.
That is, if $x\in G_n$, then $xH_i$ is a certain $H_j$.

 

[wnorman27]

So I'm trying to wrap my head around how I would find the surjective group homomorphism φ:Gn→Sn+1. Also I believe that statements about |Gn/H| must be using some results about the orders of groups that I haven't yet come across - I'll look into that.

The bigger question I have though is how in general we go about determining generators and defining relations for any given group. For example, how did MacLane/Birkhoff find the generators (1 2 ... n-1) and (n-1 1) for Sn in the first place? For groups of low order, I can see how staring at the multiplication table can be helpful, but then how in general do we determine the number of distinct elements in a group in the absence of defining relations?

Perhaps I just need some direction toward a topic this book hasn't gone through yet?