How to find generators of symmetric groups

[jackmell]

Hi,

I was wondering how to find a minimal set of generators for the symmetric groups. Would it be difficult to fill-in the following table?
$\begin{array}{cl} S_3&=\big<(1\;2),(2\;3)\big> \\ S_4&=\big<(1\;2\;3\;4),(1\;2\;4\;3)\big>\\ \vdots\\ S_{500} \end{array}$
Is there a procedure to find them other than by trial an error? How about just $S_{10}$ for that matter?

I know how to find generator orders for the integer mod groups simply by finding their isomorphic additive groups. Can I do something similar to find for examples the orders of the generators needed to generate the symmetric groups?

Thanks,
Jack

 

[Citan Uzuki]

For every n, we have: $$S_n = \langle (1\ 2),\ (1\ 2\ \ldots\ n)\rangle$$

 

[jackmell]

For every n, we have: $$S_n = \langle (1\ 2),\ (1\ 2\ \ldots\ n)\rangle$$

Ok thanks. I suppose I should try and prove that now. I'll make a conjecture: It's because:

$S_n\overset{?}{=}\{(1\;2)^k(1\;2\;3\;\cdots\;n)^j: k=\pm 1, j=1,2,\cdots,n\}\bigcup\{\epsilon\}$

Not sure that's correct though at this point.

Edit:

That's not right since it's not $n!$. I'll work on it.

And I'm just now realizing the generation of a non-abelian group from a set of generators must include non-commutative cases. For example, in the set above, I would also have to include the case of factors of the form $(1\;2\;3\;4)^k (1\;2)^j$ as well as combinations of different permutations of those factors but as far as the expression Citan gave above, why that works eludes me at the moment.

 

[Citan Uzuki]

Remember that the symmetric group is generated by the set of all transpositions, so it suffices to show that all transpositions can be generated by these two elements. Hint: first try to show that those two elements generate the set {(12), (23), (34), ..., (n-1 n)}. Then show that all transpositions can be generated from the transpositions in that set.

If you get absolutely stuck, you can find the proof here

 

[jackmell]

Ok thanks for that Citan. Working on it.

I do know how to factor any permutation into a set of adjacent transpositions so that if I can show that generator generates the set of adjacent transpositions, then I assume I can show it generates all permutations.

I'm just not use to dealing with generators of non-abelian groups. I assume in such a case, we consider all finite products:

$G=\big<a,b\big>=\{a,b,ab,ba,aab,bba,aba,bab,bbaa,abab,\cdots\}$

 

[Citan Uzuki]

I'm just not use to dealing with generators of non-abelian groups. I assume in such a case, we consider all finite products:

$G=\big<a,b\big>=\{a,b,ab,ba,aab,bba,aba,bab,bbaa,abab,\cdots\}$

Yes, but not just those. We also have products involving $a^{-1}$ and $b^{-1}$. So a list of all elements generated by $a$ and $b$ would include:
$$1,\ a,\ b,\ a^{-1},\ b^{-1},\ a^2,\ ab,\ ab^{-1},\ ba,\ b^2,\ ba^{-1},\ a^{-1}b,\ a^{-2},\ a^{-1}b^{-1},\ b^{-1}a,\ b^{-1}a^{-1},\ b^{-2},\ \ldots$$

But this is the wrong approach in this case. Rather than trying to write out all products of the elements and their inverses and show that it contains the adjacent transpositions, it is better to take each adjacent transposition and try to find some specific product of the generators and their inverses which gives that transposition. E.g. if $a = (1\ 2)$ and $b=(1\ 2\ \ldots n)$, we can get $bab^{-1} = (2\ 3)$. Can you see how to do the others?

 

[jackmell]

Yes, but not just those. We also have products involving $a^{-1}$ and $b^{-1}$. So a list of all elements generated by $a$ and $b$ would include:
$$1,\ a,\ b,\ a^{-1},\ b^{-1},\ a^2,\ ab,\ ab^{-1},\ ba,\ b^2,\ ba^{-1},\ a^{-1}b,\ a^{-2},\ a^{-1}b^{-1},\ b^{-1}a,\ b^{-1}a^{-1},\ b^{-2},\ \ldots$$

But this is the wrong approach in this case. Rather than trying to write out all products of the elements and their inverses and show that it contains the adjacent transpositions, it is better to take each adjacent transposition and try to find some specific product of the generators and their inverses which gives that transposition. E.g. if $a = (1\ 2)$ and $b=(1\ 2\ \ldots n)$, we can get $bab^{-1} = (2\ 3)$. Can you see how to do the others?

Thanks a bunch Citan. I've been struggling with it. It seems such an easy problem and I was not able to accomplish $S_4$ at all. Got other work to do also but will continue working on this and as you can see, I don't wish to look at the proof you provided just yet: proficiency in math comes from the struggle of trying to solve the problem yourself (until practical matters force you to just study the answer and move on of course). :)

You advice above will be helpful. Give me a little more time to try and figure it out.

Thanks,
Jack

Edit: Just tried $bab^{-1}$ for $S_4$:
$\begin{array}{ccccc} 1 & 2 & 3 & 4 & \text{identity} \\ 4 & 1 & 2 & 3 & b^{-1} \\ 4 & 2 & 1 & 3 & a \\ 1 & 3 & 2 & 4 & b \end{array}$
and that last one is of course the cycle $(2\;3)$ . Great! That's progress for me.

Wait, I think I see a trend now: I wish to test the following hypothesis:

Do enough inverses of $b$ to get $(1\;2)$ underneath the adjacent elements you wish to transpose. Then operate with $a$ to "prime" those positions. Then "left-shift" with a suitable $b^k$ to permute the $(1\;2)$ to the desired transposition.

Bet that's close :)

 

[Citan Uzuki]

Do enough inverses of $b$ to get $(1\;2)$ underneath the adjacent elements you wish to transpose. Then operate with $a$ to "prime" those positions. Then "left-shift" with a suitable $b^k$ to permute the $(1\;2)$ to the desired transposition.

Bet that's close :)

Yep, that's it exactly!

 

[jackmell]

Got $(4\;5)$ of $S_5$:
$\begin{array}{cccccc} 1 & 2 & 3 & 4 &5& \text{identity} \\ 5 & 1 & 2 & 3 & 4& b^{-1} \\ 4 & 5 & 1 & 2 & 3 & b^{-1} \\ 3 & 4 & 5 & 1 & 2 & b^{-1} \\\ 3 & 4 & 5 & 2 & 1 & a \\ 4 & 5 & 1 & 3 & 2 & b \\ 5 & 1 & 2 & 4 & 3 & b \\ 1 & 2 & 3 & 5 & 4 & b \end{array}$
with the net result of $b^3 ab^{-3}=(4\;5)$

Fantastic!

I think now I could probably generalize this for all adjacent permutations but will have to leave it there in the interest of other things I need to work on. Nice to know though.

Thanks again Citan!