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
-
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$– JamesAug 19, 2014 at 17:28
-
2$\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 LahtonenAug 19, 2014 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$– user1729Aug 20, 2014 at 16:12
6 Answers
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$.
$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$ Aug 19, 2014 at 17:38
You can generate $S_3$ with a rotation $(1\:2\:3)$ and a flip $(1\:2)$, think geometrically.
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$.
Any permutation in any $S_n$ can be expressed as a product of transpositions (2-cycles), so they constitute a generating set.
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$.