1
$\begingroup$

Let $n \ge 2$, $n \in \mathbb N$ and set $\sigma=(1,2,3,...,n)$ and $\tau=(1,2)$. Show that $\mathrm{Sym}(n)=\left<\sigma,\tau\right>$.

Approach: Induction

Proof:

Base case $n=2$

$\sigma=(1,2)$
$\tau=(1,2)$

$Sym(2)=\{Id_2,(1,2)\}$ $(1,2)=\tau$ and $Id_2=\tau\sigma$

so base case holds

Inductive step assume $Sym(k)=<\sigma,\tau>$ where $\sigma=(1,2,3,4,...,k)$ and $\tau=(1,2)$

Show $Sym(k+1)=<\lambda,\tau>$ where $\lambda={1,2,...,k+1}$ and $\tau=<1,2>$

To prove the inductive step, I was thinking we have to use the fact that every $x\in Sym(k+1)$ can be represented as the product of pairwise disjoint cycles. I think that we can express $\lambda$ in terms of $\sigma$

$\endgroup$
0
$\begingroup$

Your previous question was about transpositions generating $S_n$. So we may try an approach where we attempt to generate all transpositions from the given two permutations.

First, conjugate $(12)$ by $(12\cdots n)$ repeatedly to obtain $(23),(34),\cdots,(n-1\,n)$.

This makes sense once you understand this: $\sigma(a_1\,a_2\,\cdots\,a_k)\sigma^{-1}=(\sigma(a_1)\,\sigma(a_2)\,\cdots\,\sigma(a_k))$.

Second, see if you can conjugate $(i\,i+1)$ by $(j\,j+1)$s systematically to get any $(i\,k)$. For example, conjugating $(12)$ by $(23)$ gives $(13)$, then conjugating that by $(34)$ gives $(14)$.

$\endgroup$
  • $\begingroup$ I am quite lost, so we are trying to generate every transposition from $Sym(n)$? $\endgroup$ – TheMathNoob Aug 8 '16 at 7:20
  • $\begingroup$ That's the approach I said I'm discussing in my answer, yes. $\endgroup$ – arctic tern Aug 8 '16 at 7:29
  • $\begingroup$ and you want me to get somehow $(12)^k(12*****n)^l=(23),(34),....,(n-1,n)$ $\endgroup$ – TheMathNoob Aug 8 '16 at 7:31
  • $\begingroup$ No. Do you know what conjugate means? $\endgroup$ – arctic tern Aug 8 '16 at 7:32
  • $\begingroup$ I guess it means somehow to use different combinations of the two permutations to get some desired transposition? $\endgroup$ – TheMathNoob Aug 8 '16 at 7:33

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.