I am trying to find the generator(s) of the Symmetric Group $S_3$ and I have attempted this via brute force by listing the permutations of $S_3$ and composing and repeating them but I have not found any generators. - thanks
6
$\begingroup$
$\endgroup$
-
1$\begingroup$ Any group is generated by all of its elements. In particular, if you've listed all the elements, you've got a set of generators. Are there other conditions your generating set must meet? $\endgroup$ – James Aug 19 '14 at 17:28
-
1$\begingroup$ If $n>2$ the group $S_n$ cannot be generated by a single element, because it is not abelian. It can always be generated by two elements. Popular choices are $(12)$ and $(12345\cdots n)$ and also $(12)$ and $(2345\cdots n)$. Using these two bits it is easy to see that you can also generate $S_n\times S_n$ with two elements. The moral: a single generator is a very special (and simple case) - with two generators you can get almost anything. $\endgroup$ – Jyrki Lahtonen Aug 19 '14 at 20:01
-
$\begingroup$ Although all of the answers here are correct, I feel that I cannot most of them simply because they state a fact. Why don't they prove the fact?... $\endgroup$ – user1729 Aug 20 '14 at 16:12
4
$\begingroup$
$\endgroup$
$S_3$ can be generated by a 2 cycle and a 3 cycle. For example $(12)$ and $(1 2 3)$.
-
1$\begingroup$ Given that $(123)=(12)(23)$ one can also generate $S_3$ by two transpositions. $\endgroup$ – Quang Hoang Aug 19 '14 at 17:38
7
$\begingroup$
$\endgroup$
As James noted in his comment, generating sets are not unique, since if $A$ is a set that generates the group, then any set containing $A$ will also be a generating set. However, I assume you are trying to find a smallest set of generators.
If you allow an element $g$ to be a generator, then everything in the cyclic group $\langle g \rangle = \{1,g,g^2,\ldots \}$ will be taken care of. In particular, if you have one $3$-cycle, then you get the other one ($(1\,2\,3)^2=(1\,3\,2)$ and $(1\,3\,2)^2=(1\,2\,3)$). So if you have one $3$-cycle as a generator, you only need to get the three transpositions. By inspection, if you take any one of them as a generator, you can get the other two transpositions by multiplying it with the $3$-cycles.
In general, for the symmetric group $S_n$, the following are generating sets. $$\{(1\,2), (2\, 3), \ldots, (n-1,n)\}$$ $$\{(1\,2), (1\,3), \ldots, (1\,n)\}$$ This also implies that the transpositions generate $S_n$.
answered Aug 19 '14 at 17:38
5
$\begingroup$
$\endgroup$
You can generate $S_3$ with a rotation $(1\:2\:3)$ and a flip $(1\:2)$, think geometrically.
3
$\begingroup$
$\endgroup$
There is a generalization to $S_n$. The generators $\alpha_1,\cdots,\alpha_{n-1}$, such that
- $\alpha_i^2 = 1$,
- $\alpha_i\alpha_j = \alpha_j\alpha_i$ if $j \neq i\pm 1$,
- $\alpha_i\alpha_{i+1}\alpha_i = \alpha_{i+1}\alpha_i\alpha_{i+1}.$
$\alpha_i$ ``swaps the $i$th and $(i + 1)$-th position''.
See Wikipedia, which says the following:
Other popular generating sets include the set of transpositions that swap $1$ and $i$ for $2 ≤ i ≤ n$ and a set containing any $n$-cycle and a $2$-cycle of adjacent elements in the $n$-cycle.
So for $S_3$, just let $n=3$.
3
$\begingroup$
$\endgroup$
Any permutation in any $S_n$ can be expressed as a product of transpositions (2-cycles), so they constitute a generating set.
2
$\begingroup$
$\endgroup$
Regarding to @Sanath's post and that you already knew the structure of $S_3$'s structure, we may treat the group with the following presentation:
$$\langle a,b\mid a^2=b^3=(ab)^2=1\rangle$$ It is good to know that $S_3=D_6$, the dihedral group of order $6$.
protected by Saad Oct 10 '18 at 13:20
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
