0
$\begingroup$

I want to write $(1,2,4,3)$ as a product of adjacent transpositions, i.e., transpositions of the form $(k \;\; k +1)$.

Well, I manage to change this cycle to $(1,3)(1,4)(1,2)$, and $(1,3)=(1,2)(2,3)(1,2)$, $(1,4)=(1,2)(2,3)(3,4)(2,3)(1,2)$. Hence, $(1,2,4,3)=(1,2)(2,3)(1,2)(1,2)(2,3)(3,4)(2,3)(1,2)(1,2)$. And, since transposition is self-inverse, we have $(1,2,4,3)=(1,2)(3,4)(2,3)$. Is my work correct? But still, I can change $(1,2,4,3)$ to $(1,2)(2,4)(4,3)$. And $(2,4)=(2,3)(3,4)(2,3)$, so I got $(1,2)(2,3)(3,4)(2,3)(3,4)$, which should equal $(1,2)(3,4)(2,3)$, but I don't know how to manipulate it properly. Can anyone tell me how to do it?

$\endgroup$
  • $\begingroup$ $(2,3)(3,4)(2,3)(3,4)=(2,4)(3,4)=(3,2,4)=(3,4)(2,3)$ $\endgroup$ – J. W. Tanner Nov 3 '19 at 19:44
  • $\begingroup$ Well, I know how to prove that (2,4)(3,4)=(3,4)(2,3). But is there a formula or something like that to do it, or you just find it by pluging numbers? $\endgroup$ – Chang Henry Nov 3 '19 at 19:55
  • $\begingroup$ Do you want to write $(1,2,4,3)$ as a product of adjacent transpositions? Because this is not clear to me from reading the question. $\endgroup$ – rawbacon Nov 3 '19 at 20:03
  • $\begingroup$ I just did it by plugging numbers, but also $(2,3)(3,4)(2,3)=(2,4)$ is a conjugation $\endgroup$ – J. W. Tanner Nov 3 '19 at 20:04
0
$\begingroup$

For completeness, an adjacent transposition is a transposition of the form $(k \; \; k+1)$. I want to explain how to express arbitrary permutations as products of adjacent transpositions. I think you're doing okay.

The general procedure goes as follows. Each cycle $(a_1 \; \cdots a_n)$ can be expressed as a product of adjacent transpositions using
$$(a_1 \; \cdots \; a_n) = (a_1\; a_2)\cdots (a_n \; a_{n-1}).$$ E.g., $$(4\; 5\; 6\;7) = (7\; 6)(6\;5)(5\;4).$$ After that, this answer points out the following. Let $m < n$. Then you can express the transposition $(n \; m)$ as a product of adjacent transpositions by using $$(n \; m) = (m + 1 \; \; m)\cdots (n-1 \; \; n-2)(n \; \; n-1)(n-1 \;\;n-2)\cdots(m+1 \;\;m),$$ (which you might or might not know, judging from your question). For example, $$(7 \; 2) = (3\;2)(4\;3)(5\;4)(6\;5)\cdot (7\; 6) \cdot (6\;5)(5\;4)(4\;3)(3\;2).$$

Edit: To then move on to try to use as few transpositions as possible, you might want to apply the following formulas. If the numbers $k, m, n, \ell$ are pairwise distinct, then we have that $(k\; m)(n \; ell)$ commute, i.e., $$(k \; m)(n \; \ell) = (n \; \ell)(k \; m).$$ Moreover, for any $k$ we have that $(k-1 \;\; k)$ and $(k \;\; k+1)$ satisfy the so-called braid relation $$ (k−1\;\;k)(k\;\;k+1)(k−1\;\;k)=(k\;\;k+1)(k−1\;\;k)(k\;\;k+1). $$ A Theorem by Tits (explained, e.g., in these notes on Coxeter groups in Section 4.3) states that after writing a permutation as a product of adjacent permutations, this expression can be turned into an expression that is as short as possible by applying only commutativity (where it applies), the braid relation (where it applies) and the fact that transpositions are self-inverse.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I do understand this. Only a few questions. First, transpostion is self-inverse? (a,b)=(b,a)? And, for my question, there're two different ways of transform a cycle into transpositions. One is using (1 , the last term), (1, the second last term) and so on. Another is what you wrote and I included it as second method in my question. $\endgroup$ – Chang Henry Nov 4 '19 at 9:03
  • $\begingroup$ Yes, this is correct. $\endgroup$ – rawbacon Nov 4 '19 at 9:04
  • $\begingroup$ Then, I can have two different combination of transpositions, and they are equivalent as I can plug numbers to verify it. Next step is to change it into adjacent transpositon. By the first method, I can simplify it into 3 adjacent transpositions with the help of self-inverse. But with second method, I got 5 adjacent transpositions and the product is equal to that of 3 transpositions, which can still be verified. The question is, how can I transform it into( or simplify) the 3-form without knowing that 3 form at the beginning? $\endgroup$ – Chang Henry Nov 4 '19 at 9:10
  • $\begingroup$ The adjacent transposition decomposition is not unique, but what you can do is note that if two transpositions that appear next to each other do not share an entry, then they commute (you can swap the order in which you apply the transposition). Like this you might obtain shorter forms. $\endgroup$ – rawbacon Nov 4 '19 at 9:15
  • $\begingroup$ Also, you might want to use that $(k-1 \;\; k)(k \;\; k +1)(k-1 \;\; k) =(k \;\; k +1)(k-1 \;\; k)(k \;\; k +1)$ (let's call this the braid relation). A theorem by Tits (his so-called solution to the word problem in Coxeter groups, whatever that means) then says that you can obtain any of the shortest adjacent cycle decomposition by applying commutativity and the braid relation. $\endgroup$ – rawbacon Nov 4 '19 at 9:20

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.