7
$\begingroup$

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

$\endgroup$
3
  • 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, 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 Lahtonen
    Aug 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$
    – user1729
    Aug 20, 2014 at 16:12

6 Answers 6

Reset to default
11
$\begingroup$

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$.

$\endgroup$
5
$\begingroup$

$S_3$ can be generated by a 2 cycle and a 3 cycle. For example $(12)$ and $(1 2 3)$.

$\endgroup$
1
  • 1
    $\begingroup$ Given that $(123)=(12)(23)$ one can also generate $S_3$ by two transpositions. $\endgroup$
    – Quang Hoang
    Aug 19, 2014 at 17:38
5
$\begingroup$

You can generate $S_3$ with a rotation $(1\:2\:3)$ and a flip $(1\:2)$, think geometrically.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

Any permutation in any $S_n$ can be expressed as a product of transpositions (2-cycles), so they constitute a generating set.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.