5

Write the following permutation as product of disjoint cycles

$$(12)(13)(14)(15)$$

Could someone explain how to proceed with this question ? I have four more similar, so I just want somebody to solve this one so that I can have a basic example.

Thank you in advance

amir
  • 1,311

2 Answers2

9

We write this permutation on its standard form $$\sigma=\left(\begin{array}\\ 1&2&3&4&5\\ 5&1&2&3&4 \end{array}\right)$$ and this a cycle since $$1\overset \sigma\rightarrow5\overset \sigma\rightarrow4\overset \sigma\rightarrow3\overset \sigma\rightarrow2\overset \sigma\rightarrow1$$ so $$\sigma=(1\ 5\ 4\ 3\ 2)$$

  • I just want to make sure that I understood.

    I have the following example (123)(234)(345)

    We write this permutation on its standard form $$\sigma=\left(\begin{array}\ 1&2&3&4&5\ 2&3&4&5&3 \end{array}\right)$$

    But then how do you conclude the cycle ?

     – amir Aug 26 '13 at 04:38
  • 2
    In this second example $\sigma(1)=2$ and $\sigma(2)=1$ and $\sigma(3)=3$ and $\sigma(4)=5$ and $\sigma(5)=4$ so we have $2$ cycles and $\sigma=(12)(45)$ –  Aug 26 '13 at 04:47
  • Why is $\sigma(2)=1$ ? It should be $\sigma(2)=3$ since we have (123) – amir Aug 26 '13 at 04:54
  • @user43418: Your second example (in table form) can't be right. You have $\sigma(2)=3=\sigma(5)$, so it is not a permutation. – Jyrki Lahtonen Aug 26 '13 at 04:58
  • @JyrkiLahtonen But we have (123) so how can $\sigma(2)=1$ ? – amir Aug 26 '13 at 05:02
  • 1
    And to answer your question. The cycle $(345)$ keeps $2$ fixed. Then the cycle $(234)$ maps $2\mapsto3$. The cycle $(123)$ then maps that $3\mapsto1$, so the total effect is $2\mapsto 1$. I am reading the composition from right to left as is commonly done with functions. It is possible to want to do this left-to-right (see Brian's answer), but there is no universally accepted rule. Check your book. – Jyrki Lahtonen Aug 26 '13 at 05:04
  • 1
    First we apply the cycle $\sigma_1=(345)$ to $2$ but since $2$ isn't in the support of this cycle so $\sigma_1(2)=2$, then $\sigma_2=(234)$ and we have $\sigma_2(\sigma_1(2))=\sigma_2(2)=3$ and finally $\sigma_3=(123)$ and we have $\sigma_3(\sigma_2(\sigma_1(2)))=\sigma_3(3)=1$ –  Aug 26 '13 at 05:05
  • Now I understood. Thank you for both of your help – amir Aug 26 '13 at 05:08
  • @SamiBenRomdhane
    Here is what I found for the two last questions: (1234)(2345): (24153) and (12)(23)(34)(45)(51): (13452)     – amir Aug 26 '13 at 05:28
  • @user43418 No, there are mistakes. –  Aug 26 '13 at 05:33
  • @SamiBenRomdhane I think it is: (12453) for the first and (2345) for the second – amir Aug 26 '13 at 05:39
  • @user43418 Yes it's correct now. –  Aug 26 '13 at 09:16
  • +1 for doing the permutations into disjoint ones step by step. – Mikasa Aug 26 '13 at 16:14
3

Assuming that the transpositions are applied from left to right, this permutation first takes $1$ to $2$, and $2$ is unaffected by the remaining three transpositions. It takes $2$ to $1$, which the second transposition then takes to $3$; $3$ is unaffected by the last two transpositions, so the permutation takes $2$ to $3$. Now what does it do to $3$? The first transposition has no effect on $3$, the second takes it to $1$, and the third then takes this $1$ to $4$; since the last transposition does not affect the $4$, the net effect is to take $3$ to $4$. Similar reasoning shows that $4$ is unaffected by the first two transpositions and sent to $1$ by the third; this $1$ is then sent to $5$ by the last transposition, so the permutation ends up taking $4$ to $5$. Finally, $5$ is affected only by the last transposition, which takes it to $1$; there are no further transpositions to be applied at that point, so the permutation takes $5$ to $1$. The overall effect is therefore

$$1\mapsto 2\mapsto 3\mapsto 4\mapsto 5\mapsto 1\;,$$

which is represented by the single cycle $(12345)$. That is, this permutation is a cycle.

With another permutation we might initially have found that $1\mapsto 3\mapsto 4\mapsto 1$. In that case we’d then look to see what the permutation does to the first number missing from this cycle, namely, $2$. In this particular case we’d then find one of two things: either it takes $2$ to itself and $5$ to itself, or it takes $2$ to $5$ and $5$ to $2$. In the second case we have the permutation $(134)(25)$; in the first we have $(134)(2)(5)$, though the $1$-cycles are often omitted in practice.

If the permutation is $\pi$, the general idea is to find $\pi(1)$, $\pi\big(\pi(1)\big)$, and so on, until you close a cycle. Then take the first number not in that cycle and track its orbit under repeated applications of $\pi$. Keep doing this until all elements of the domain have been exhausted. These orbits never intersect, so you get the decomposition of $\pi$ into a product of pairwise disjoint cycles.

Brian M. Scott
  • 616,228