25
$\begingroup$

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?

$\endgroup$
5
  • 4
    $\begingroup$ If $h=(12\ldots n)$, the $(12)^{h}=(23)$, $(12)^{h^2}=(34)$, etc. $\endgroup$
    – user641
    Oct 9 '13 at 20:16
  • 2
    $\begingroup$ I'm confused by the exponents. Can you clarify? Thanks $\endgroup$
    – Dan H
    Oct 9 '13 at 20:33
  • 2
    $\begingroup$ @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. $\endgroup$
    – user14972
    Oct 11 '13 at 7:37
  • $\begingroup$ 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? $\endgroup$
    – user14972
    Oct 11 '13 at 7:43
  • $\begingroup$ (depending on your ordering conventions, $x^y$ might mean $yxy^{-1}$ -- I don't recall which one is standard) $\endgroup$
    – user14972
    Oct 11 '13 at 7:47
35
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Dan H
    Oct 9 '13 at 20:31
  • $\begingroup$ I edited it to include an answer now. $\endgroup$
    – tylerc0816
    Oct 9 '13 at 20:42
  • $\begingroup$ Isn't $c(1, 2)c^{-1} = (1,n)$? Doesn't change anything to the solution though. $\endgroup$
    – Quotenbanane
    Apr 29 at 22:30
  • $\begingroup$ @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. $\endgroup$
    – M Desmond
    Oct 14 at 8:23
3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ In what way is this different from the correct answer already given? $\endgroup$
    – ancient mathematician
    Jun 3 '20 at 11:56
  • $\begingroup$ It uses induction in a more rigorous way but the general idea is exactly the same $\endgroup$
    – Sofia
    Jun 3 '20 at 11:58
  • $\begingroup$ 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. $\endgroup$
    – ancient mathematician
    Jun 3 '20 at 13:51
  • $\begingroup$ 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. $\endgroup$
    – Sofia
    Jun 3 '20 at 14:51
  • $\begingroup$ I'm sorry, you are talking about natural numbers: and $n+1\not=1$. $\endgroup$
    – ancient mathematician
    Jun 3 '20 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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