Proof about symmetric groups and generators

1. Aug 8, 2016

SuperSusanoo

1. The problem statement, all variables and given/known data
Let n>=2 n is natural and set x=(1,2,3,...,n) and y=(1,2). Show that Sym(n)=<x,y>

2. Relevant equations

3. The attempt at a solution
Approach: Induction

Proof:

Base case n=2

x=(1,2)
y=(1,2)

Sym(2)={Id,(1,2)}
(1,2)=x and Id=xy

so base case holds

Inductive step assume Sym(k)=<x,y> where x=(1,2,3,4,...,k) and y=(1,2)

Show Sym(k+1)=<t,y> where t={1,2,...,k+1} and y=<1,2>

To prove the inductive step, I was thinking we have to use the fact that every b in Sym(k+1) can be represented as the product of pairwise disjoint cycles. I think that we can express $\lambda$ in terms of x

2. Aug 8, 2016

Staff: Mentor

Hint: $(1\;2\; \dots \; k\; (k+1)) =(1\;2\; \dots \; k)\circ (k \; (k+1))$ - from right to left. So $(k \; (k+1)) = (1\;2\; \dots \; k)^{-1} \circ (1\;2\; \dots \; k\; (k+1)) \in \mathcal{Sym}(k+1)$ by induction and the fact that all permutations that doesn't involve $k+1$ are in
If you can show, that all other transpositions $(i \; (k+1))$ are in it, too, you're done. This is because you then can place $k+1$ in every position with an arbitrary fixed order of the other elements.
Remember that all transpositions $(i \; j)$ with $i\, , \, j \, \leq \, k$ are already in the group.

Edit: Plus the fact that $\{ \pi \in \mathcal{Sym}(k+1) \; | \; \pi(k+1) = k+1 \} \cong \mathcal{Sym}(k) \subset \mathcal{Sym}(k+1)$

Last edited: Aug 8, 2016
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted