22
$\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
  • 1
    $\begingroup$ I'm confused by the exponents. Can you clarify? Thanks $\endgroup$ – Dan H Oct 9 '13 at 20:33
  • 1
    $\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
28
$\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$
2
  • $\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
2
$\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$
5
  • $\begingroup$ In what way is this different from the correct answer already given? $\endgroup$ – ancientmathematician 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$ – ancientmathematician 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$ – ancientmathematician 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.