Problem: Consider the arbitrary 2-cycle $(a\ b)$ from $S_n$. Find a way to write this permutation as a product of adjacent 2-cycles.

What I do know:

A transposition is a single cycle of length 2. An adjacent transposition is of the form $(i\ i+1)$. For example, $(3\ 7)$ is a non-adjacent transposition, but $(3,4)$ is an adjacent transposition. It turns out that the set of transpositions for $S_n$ is a generating set for $S_n$.

So, to write the arbitrary 2-cycle $(a\ b)$ from $S_n$ as a product of 2 adjacent cycles, would it look something like this:

I can start at some arbitrary values, say, $(1\ 2)$. Then,

$(1\ 2)(a\ a+1)(a+1\ a+2)\cdots(b-2\ b-1)(b-1\ b)$ and eventually, I will get to $(a\ b)$?

I guess my question is, would this be a valid answer or would I need to generalize it more? And, is it ok to start at some arbitrary values such as the one I chose? Thanks for your help.

  • $\begingroup$ Are you familiar with the fact that for any permutation $\sigma\in S_n$ you have $$\sigma(a\ b)\sigma^{-1}=(\sigma(a),\sigma(b))?$$ $\endgroup$ – Servaes Mar 5 '19 at 22:17
  • $\begingroup$ @Servaes I am not. $\endgroup$ – Ryan Mar 6 '19 at 1:39

In general the product of adjacent transpositions $$(1\ 2)(a\ a+1)(a+1\ a+2)\cdots(b-2\ b-1)(b-1\ b),$$ does not eventually reach $(a\ b)$. For example, if $(a\ b)=(3\ 4)$ then your product is $$(1\ 2)(3\ 4)\neq(3\ 4).$$ A less degenerate example would be $(a\ b)=(4\ 8)$. Then your product is $$(1\ 2)(4\ 5)(5\ 6)(6\ 7)(7\ 8)=(1\ 2)(4\ 5\ 6\ 7\ 8)\neq(4\ 8).$$

In stead, use the fact that $$(c\ c+1)(a\ c)(c\ c+1)=(a\ c+1).$$ In this way, starting from $c=a+1$ we get $$(a+1\ a+2)(a\ a+1)(a+1\ a+2)=(a\ a+2),$$ then again with $c=a+2$ to get $$(a+2\ a+3)(a+1\ a+2)(a\ a+1)(a+1\ a+2)(a+2\ a+3)=(a\ a+3),$$ and you can continue this way all the way to $c=b-1$ to get $(a\ b)$.

  • $\begingroup$ So, if we have $$(a\ a+1)(a\ b)(a\ a+1)=(a+1\ b)$$ I guess I am not seeing the big picture and generalization on how this is writing $(a\ b)$ as adjacent 2-cycles. Thanks for your help. $\endgroup$ – Ryan Mar 6 '19 at 1:43
  • 1
    $\begingroup$ Perhaps it would have been better to suggest the 'reverse' equality, let me update my answer to be more clear. $\endgroup$ – Servaes Mar 6 '19 at 9:07
  • $\begingroup$ Thanks for the help. $\endgroup$ – Ryan Mar 6 '19 at 14:30

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.