# $(12)$ and $(123\dots n)$ are generators of $S_n$

Show that $S_n$ is generated by the set $\{ (12),(123\dots n) \}$.

I think I can see why this is true. My general plan is (1) to show that by applying various combinations of these two cycles you can get each transposition, and then (2) to show that each cycle is a product of transpositions.

I'm just having trouble on the first step. Any ideas?

• If $h=(12\ldots n)$, the $(12)^{h}=(23)$, $(12)^{h^2}=(34)$, etc.
– user641
Oct 9 '13 at 20:16
• I'm confused by the exponents. Can you clarify? Thanks Oct 9 '13 at 20:33
• @Dan: Conjugation is often written as exponentiation, so $x^y$ means $y^{-1} x y$. It does satisfy the suggested identities: $(xy)^z = x^zy^z$ and $x^{yz} = (x^y)^z$. More general group automorphisms are also often written with similar notation.
– user14972
Oct 11 '13 at 7:37
• And it's useful to actually think in this way: e.g. conjugation by $h$ turns out to be a fairly natural operation on cycles (it adds one to each number appearing in the cycle). What might conjugation by $(23)$ do?
– user14972
Oct 11 '13 at 7:43
• (depending on your ordering conventions, $x^y$ might mean $yxy^{-1}$ -- I don't recall which one is standard)
– user14972
Oct 11 '13 at 7:47

Let $c = (1, 2, \dotsc, n)$. We see that \begin{align*} c (1, 2) c^{-1} &= (2, 3) \\ c (2, 3) c^{-1} &= (3, 4) \\ &\vdots \\ c (n-2, n-1) c^{-1} &= (n-1, n), \end{align*} so that $(i, i+1) \in \langle (1, 2), c \rangle$ for all $1 \leq i \leq n-1$. Next, we have \begin{align*} (2, 3) (1, 2) (2, 3)^{-1} &= (1, 3) \\ (3, 4) (1, 3) (3, 4)^{-1} &= (1, 4) \\ &\vdots \\ (n-1, n) (1, n-1) (n-1, n)^{-1} &= (1, n), \end{align*} so that $(1, i) \in \langle (1, 2), c \rangle$ for all $1 \leq i \leq n$. Choose any $1 \leq i < j \leq n$, then $$(i, j) = (1, i) (1, j) (1, i)^{-1} \in \langle (1, 2), c \rangle.$$ Therefore, $\langle (1, 2), c \rangle$ contains all transpositions. Hence, $\langle (1, 2), c \rangle = S_n$.

• I was thinking that would be true so that I could get that the set is equivalent to all transpositions, and every cycle can be written as a product of transpositions, but I'm not sure why its true. Oct 9 '13 at 20:31
• I edited it to include an answer now. Oct 9 '13 at 20:42
• Isn't $c(1, 2)c^{-1} = (1,n)$? Doesn't change anything to the solution though. Apr 29 at 22:30
• @Quotenbanane yes you can generate (1n) and then you have to look for another n order element to generate one more 2 cycles, it's pretty cumbersome, rather just find a way to generate (12) , (13)... (1n) then (23), (24),... It's easy to get track here. Oct 14 at 8:23

## First, we use Induction to prove that: $$\forall k \in \{1,2,3...n\}: (k \ k+1) \in \ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$$

Base Case:

$$(1 \ 2) \in \ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$$

Induction Step:

Suppose: $$(k \ k+1) \in \ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$$

Then: $$(1 \ 2 \ 3 \ 4\ ..n)(k \ k+1)(1 \ 2 \ 3 \ 4\ ..n)^{-1}= (k+1 \ k+2)$$

## Further, we will prove that: $$\forall k \in \{1,2,3...n\} : (1 \ k) \in \ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$$

Base Case:

$$(1 \ 2) \in \ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$$

Induction Step:

Suppose: $$(1 \ k) \in \ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$$

Then: $$(k \ k +1) ( 1\ k) (k \ k+1)^{-1}=(1 \ k+1)$$

## Finally, we show that: $$\forall a ,b \in \{1,2,3...n\} : (a \ b) \in \ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$$

Let $$a,b \in \{1,2,3...n\}$$ be arbitrary.

Then: $$(1 \ a)(1 \ b)(1 \ a) = (a \ b)$$

Thus: $$( a \ b) \in \ < (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$$

## Concustion

All transpositions can be generated by $$< (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$$ that means that $$S_n$$ is generated by $$< (1 \ 2),(1 \ 2 \ 3 \ 4\ ..n) >$$

• In what way is this different from the correct answer already given? Jun 3 '20 at 11:56
• It uses induction in a more rigorous way but the general idea is exactly the same Jun 3 '20 at 11:58
• Doesn't look very rigorous to me: in fact it is plain false. $(n n+1)\not\in\langle (12),(12\dots n)\rangle$. And so on. Jun 3 '20 at 13:51
• You are totally right. But now I think it is correct. Because $(n \ n+1)$ actually is in $<(12)(12...n)>$, if I am not mistaken. Given that $n+1=1$ as we are talking about a cyclic group. Jun 3 '20 at 14:51
• I'm sorry, you are talking about natural numbers: and $n+1\not=1$. Jun 3 '20 at 16:13