32
$\begingroup$

$$\sigma=\begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 4&2&9&10&6&5&11&7&8&1&3 \end{pmatrix}$$

(1) I am asked to write this permutation in $S_{11}$ as a product of disjoint cycles and also as a product of transpositions.

(2) Also find the order of the element. Is this permutation even or odd?

I think these are the disjoint cycles

$E_{1}=(1,4,10)$, $\;\operatorname{order}E_1 =3$

$E_{2}= (3,9,8,7,11),\;$ $\operatorname{order}E_{2} =5$

$E_{3}=(5,6),\;$ $\operatorname{order}E_{3} =2$

$S_{11}$= $E_{1} \cdot E_{2}\cdot E_{3}$

The order of $\operatorname{order}E_{3}$ is even so the order of the permutation is even. Why are they asking this? And what is the significance of it being even or odd?

Transpositions – I have read this a couple times but the one example in my textbook is rather unclear, I am not sure what this means?

I think the transposition for $E_{1}$ is $(1,4)(1,10)$ but I'm not sure what this means.

$\endgroup$
6
  • $\begingroup$ So was my attempt for the cycle $E_{1}$ correct? $\endgroup$
    – Faust
    Mar 4, 2013 at 0:21
  • 6
    $\begingroup$ Nice job so far, Faust7. $E_1 = (1, 10)(1, 4)$ is one product of transpositions. $E_1 = (1, 4)(4, 10)$ is another product of transpositions of cycle one. There are many ways to write a permutation as a product of transpositions, but even so, every permutation can be expressed as either an even number of transpositions, like in this case, or an odd number of transposition. No permutation can be expressed as the product of both an even and odd number of transpositions. Hence the first cycle is even. $\endgroup$
    – amWhy
    Mar 4, 2013 at 0:27
  • 2
    $\begingroup$ $(1,4)(1,10)=(1,10,4)\neq (1,4,10)=(1,10)(1,4)$ $\endgroup$
    – borg
    Mar 4, 2013 at 0:29
  • $\begingroup$ So all i nee dot do is find one even cycle and im done, ok i think i can finish this =) Tyvm guys. one last thing why use Transpositions? why not leave them as disjoint cycles? $\endgroup$
    – Faust
    Mar 4, 2013 at 0:40
  • 4
    $\begingroup$ About "so the order of the permutation is even. Why are they asking this?" Look more closely at what they asked. They ask whether the permutation is even or odd, not whether its order is even or odd. A permutation is called even if it is the product of an even number of transpositions; it's called odd if it's the product f an odd number of transpositions. As amWhy said, a permutation can be written in many ways as a product of transpositions, but they will either all have an even number of factors or all have an odd number of factors. So the definition of even & odd permutations makes sense. $\endgroup$
    – Andreas Blass
    Mar 4, 2013 at 1:11

2 Answers 2

Reset to default
34
$\begingroup$

I'll use a longer cycle to help describe two techniques for writing disjoint cycles as the product of transpositions:

Let's say $\tau = (1, 3, 4, 6, 7, 9) \in S_9$

Then, note the patterns:

Method 1: $\tau = (1, 3, 4, 6, 7, 9) = (1, 9)(1, 7)(1, 6)(1, 4)(1, 3)$

Method 2: $\tau = (1, 3, 4, 6, 7, 9) = (1, 3)(3, 4)(4, 6)(6, 7)(7, 9)$

Both products of transpositions, method $1$ or method $2$, represent the same permutation, $\tau$. Note that the order of the disjoint cycle $\tau$ is $6$, but in both expressions of $\tau$ as the product of transpositions, $\tau$ has $5$ (odd number of) transpositions. Hence $\tau$ is an odd permutation.

Now, don't forget to multiply the transpositions you obtain for each disjoint cycle so you obtain an expression of the permutation $S_{11}$ as the product of the product of transpositions, and determine whether it is odd or even:

$\sigma = (1, 4, 10)(3, 9, 8, 7, 11)(5, 6)$.

  • The order of $\sigma = \operatorname{lcm}(3, 5, 2) = 30$.

  • Expressing $\sigma $ as the product of transpositions:

    • $\sigma =(1, 4)(4, 10)(3, 9)(9, 8)(8, 7)(7, 11)(5, 6):\quad 7$ transpositions in all, so $\sigma $ is an odd permutation (which happens to be of even order).
$\endgroup$
5
  • $\begingroup$ Could $\tau$ be written as $\tau = (1, 3, 4, 6, 7, 9) = (1, 3)(1, 4)(1, 6)(1, 7)(1, 9)$? $\endgroup$
    – Trajan
    Jan 15, 2015 at 14:49
  • $\begingroup$ No: work it out and see for yourself if you get back the original permutation. $\endgroup$
    – amWhy
    Jan 15, 2015 at 14:51
  • $\begingroup$ We could write $(1,3)(3,4)(4,6)(6,7)(7, 9)$ or as $(1, 9)(1, 7)(1, 6)(1,(4)(1, 3)$. In each case, composing each product of transpositions from right to left, brings you back to the original cycle. So the order of $\tau$ is six. But since it can only be expressed as a product of an odd number of transpositions, the parity of $\tau$ is odd. $\endgroup$
    – amWhy
    Nov 6, 2017 at 20:02
  • $\begingroup$ What’s method 1? Method 2 looks more straight forward. $\endgroup$
    – Alper
    Feb 4 at 23:32
  • $\begingroup$ You just go back from the end? $\endgroup$
    – Alper
    Feb 4 at 23:36
2
$\begingroup$

If you missed the class on cycles, you can use the following mechanized approach to write $\sigma$ as a product of transpositions:

$(1 \; 4) \circ \begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 4&2&9&10&6&5&11&7&8&1&3 \end{pmatrix} =$ $\quad \quad \quad \begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 1 & 2&9&10&6&5&11&7&8&4&3 \end{pmatrix}$

$(3 \; 9) \circ \begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 1 & 2&9&10&6&5&11&7&8&4&3 \end{pmatrix} =$ $\quad \quad \quad \begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 1 & 2&3&10&6&5&11&7&8&4&9 \end{pmatrix}$

$(4 \; 10) \circ \begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 1 & 2&3&10&6&5&11&7&8&4&9 \end{pmatrix} =$ $\quad \quad \quad\; \, \begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 1 & 2&3&4&6&5&11&7&8&10&9 \end{pmatrix}$

$(5 \; 6) \circ \begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 1 & 2&3&4&6&5&11&7&8&10&9 \end{pmatrix} = $ $\quad \quad \quad \begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 1 & 2&3&4&5&6&11&7&8&10&9 \end{pmatrix}$

$(7 \; 11) \circ \begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 1 & 2&3&4&5&6&11&7&8&10&9 \end{pmatrix} = $ $\quad \quad \quad\; \, \begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 1 & 2&3&4&5&6&7&11&8&10&9 \end{pmatrix}$

$(8 \; 11) \circ \begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 1 & 2&3&4&5&6&7&11&8&10&9 \end{pmatrix} = $ $\quad \quad \quad \; \, \begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 1 & 2&3&4&5&6&7&8&11&10&9 \end{pmatrix}$

$(9 \; 11) \circ\begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 1 & 2&3&4&5&6&7&8&11&10&9 \end{pmatrix} = $ $\quad \quad \quad \; \, \begin{pmatrix} 1 & 2 &3 & 4& 5& 6&7 &8 &9 &10 & 11 \\ 1 & 2&3&4&5&6&7&8&9&10&11 \end{pmatrix}$

$ $

$\tag{ANS} \sigma = (1 \; 4)\,(3 \; 9)\,(4 \; 10)\,(5 \; 6)\,(7 \; 11)\,(8 \; 11)\,(9 \; 11)$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .