# Determine the cycle decomposition of the permutations

#### mathmari

##### Well-known member
MHB Site Helper
Hey!! We have the following permutations in $\text{Sym}(14)$ :

- $\pi_1=(1 \ 2\ 4 \ 9)\circ(1 \ 3)\circ (6 \ 8\ 12)$
- $\pi_2=(2 \ 4\ 5 \ 8\ 7)\circ (1 \ 12 \ 6)\circ \ (13 \ 14)$
- $\pi_3=(1 \ 4 \ 5\ 8 \ 11)\circ (2 \ 4\ 6 \ 5 \ 1)$

1. Determine the cycle decomposition of $\pi_1, \pi_2, \pi_3$.
2. Determine $\pi_1^{-1}, \pi_2^{-1}, \pi_3^{-1}$.
3. Determine $\pi_4=\pi_1\circ \pi_2$, $\pi_5=\pi_2\circ\pi_3$, $\pi_6=\pi_2\circ\pi_1$.
4. Determine the signum of $\pi_1, \pi_2, \pi_3, \pi_4, \pi_5, \pi_6$.

1. We consider the composition fromright to left, or not? Thenfrom the last we consider the element $6$ that goes $8$ and since there is no other $8$ previously we have that $6\rightarrow 8$.

Is this the idea to get the cycles?

2. We get the inverse permutation by the cycle decompsition, right? Last edited:

#### Klaas van Aarsen

##### MHB Seeker
Staff member
1. We consider the composition fromright to left, or not? Thenfrom the last we consider the element $6$ that goes $8$ and since there is no other $8$ previously we have that $6\rightarrow 8$.

Is this the idea to get the cycles?
Hey mathmari !!

Yes, this is the way to decompose the permutation into disjoint cycles. 2. We get the inverse permutation by the cycle decompsition, right?
We can choose.
We get the inverse by reversing each cycle in combination with applying the constituent cycles in reverse.
We can do this with the permutation as given, or with the decomposition.

We can for instance already write:
$$\pi_1^{-1}=(12 \ 8\ 6)\circ(3 \ 1)\circ(9 \ 4\ 2 \ 1)$$
It may be intended to do this with the decomposition of $\pi_1$ though. #### mathmari

##### Well-known member
MHB Site Helper
Yes, this is the way to decompose the permutation into disjoint cycles. Aren't the first two permutations already the decomposition into disjoint cycles? As for $\pi_3$ we have the following:
$1$ goes to $2$
$5$ goes to $1$ and $1$ goes to $4$, so $5$ goes to $4$
$6$ goes to $5$ and $5$ goes to $8$, so $6$ goes to $8$
$4$ goes to $6$
$2$ goes to $4$ and $4$ goes to $5$, so $2$ goes to $5$
$11$ goes to $1$
$8$ goes to $11$

Is this correct? #### Klaas van Aarsen

##### MHB Seeker
Staff member
Aren't the first two permutations already the decomposition into disjoint cycles?
Yes.
But the third permutation could still conceivably overlap both of them, so that they might not actually end up as disjoint cycles in the decomposition. As for $\pi_3$ we have the following:
$1$ goes to $2$
$5$ goes to $1$ and $1$ goes to $4$, so $5$ goes to $4$
$6$ goes to $5$ and $5$ goes to $8$, so $6$ goes to $8$
$4$ goes to $6$
$2$ goes to $4$ and $4$ goes to $5$, so $2$ goes to $5$
$11$ goes to $1$
$8$ goes to $11$

Is this correct?
Yep.
Can we write it as disjoint cycles? #### mathmari

##### Well-known member
MHB Site Helper
Yep.
Can we write it as disjoint cycles? So we get $\pi_3=(1 \ 2 \ 5 \ 4 \ 6 \ 8 \ 11)$, or not? #### Klaas van Aarsen

##### MHB Seeker
Staff member
So we get $\pi_3=(1 \ 2 \ 5 \ 4 \ 6 \ 8 \ 11)$, or not?
Yep. #### mathmari

##### Well-known member
MHB Site Helper
Yep. Therefore, the cycle decompositions of the permutations are:
- $\pi_1=(1 \ 2\ 4 \ 9) \ (1 \ 3)\ (6 \ 8\ 12)$
- $\pi_2=(2 \ 4\ 5 \ 8\ 7)\ (1 \ 12 \ 6) \ (13 \ 14)$
- $\pi_3=(1 \ 2 \ 5 \ 4 \ 6 \ 8 \ 11)$

Right? At the first two do we consider the product of the cycles or the composition as we had initially? #### Klaas van Aarsen

##### MHB Seeker
Staff member
Therefore, the cycle decompositions of the permutations are:
- $\pi_1=(1 \ 2\ 4 \ 9) \ (1 \ 3)\ (6 \ 8\ 12)$
- $\pi_2=(2 \ 4\ 5 \ 8\ 7)\ (1 \ 12 \ 6) \ (13 \ 14)$
- $\pi_3=(1 \ 2 \ 5 \ 4 \ 6 \ 8 \ 11)$

Right?
The cycles in $\pi_1$ are not disjoint are they?
Isn't $1$ in multiple cycles? At the first two do we consider the product of the cycles or the composition as we had initially?
Huh? Which 'first two'?
Which question are we talking about?

#### mathmari

##### Well-known member
MHB Site Helper
The cycles in $\pi_1$ are not disjoint are they?
Isn't $1$ in multiple cycles? Oh yes, you are right! So, the cycle decompositions of the permutations are:
- $\pi_1=(12 \ 6 \ 8)\ (3 \ 2)\ (9 \ 1 \ 2 \ 4)$
- $\pi_2=(2 \ 4\ 5 \ 8\ 7)\ (1 \ 12 \ 6) \ (13 \ 14)$
- $\pi_3=(1 \ 2 \ 5 \ 4 \ 6 \ 8 \ 11)$

Right? Huh? Which 'first two'?
Which question are we talking about?
My question is: Is there a difference between $(12 \ 6 \ 8)\ (3 \ 2)$ and $(12 \ 6 \ 8)\circ (3 \ 2)$ ? Is the product and the composition symbol equivalent? #### Klaas van Aarsen

##### MHB Seeker
Staff member
Oh yes, you are right!

So, the cycle decompositions of the permutations are:
- $\pi_1=(12 \ 6 \ 8)\ (3 \ 2)\ (9 \ 1 \ 2 \ 4)$
Doesn't $\pi_1$ have two cycles with $2$ in them now? My question is: Is there a difference between $(12 \ 6 \ 8)\ (3 \ 2)$ and $(12 \ 6 \ 8)\circ (3 \ 2)$ ? Is the product and the composition symbol equivalent?
Ah no, there is no difference.
The product of cycles is defined as the composition. They are the same. #### mathmari

##### Well-known member
MHB Site Helper
Doesn't $\pi_1$ have two cycles with $2$ in them now? Ah yes!

I tried that again and now I get $(12 \ 6 \ 8)\ (3 \ 2 \ 4 \ 9 \ 1)$ but there must be a mistake (but I don't know wheat I have done wrong) because at the initlal permutation $1$ goes to $2$ but not here. From the initial permutation $\pi_1$ we get:

$12 \rightarrow 6$
$6 -\rightarrow 8$
$8 \rightarrow 12$
$3 \rightarrow 1 \rightarrow 2$
$9 \rightarrow 1$
$1 \rightarrow 2$
$2 \rightarrow 4$
$4 \rightarrow 9$

Or not? Ah no, there is no difference.
The product of cycles is defined as the composition. They are the same. Ahh ok!! #### Klaas van Aarsen

##### MHB Seeker
Staff member
Ah yes!

I tried that again and now I get $(12 \ 6 \ 8)\ (3 \ 2 \ 4 \ 9 \ 1)$ but there must be a mistake (but I don't know wheat I have done wrong) because at the initlal permutation $1$ goes to $2$ but not here. From the initial permutation $\pi_1$ we get:

$12 \rightarrow 6$
$6 -\rightarrow 8$
$8 \rightarrow 12$
$3 \rightarrow 1 \rightarrow 2$
$9 \rightarrow 1$
$1 \rightarrow 2$
$2 \rightarrow 4$
$4 \rightarrow 9$

Or not? We have the following permutations in $\text{Sym}(14)$ :

- $\pi_1=(1 \ 2\ 4 \ 9)\circ(1 \ 3)\circ (6 \ 8\ 12)$
Don't we have $1\to 3$? Anyway, here's a slightly different way to find it.
Let's start with $1$.
$1 \to 3$ for $(1\,3\,\ldots)$.
$3\to 1 \to 2$ for $(1\,3\,2\,\ldots)$.
$2\to 4$ for $(1\,3\,2\,4\,\ldots)$.
$4\to 9$ for $(1\,3\,2\,4\,9\,\ldots)$.
$9\to 1$, which completes the cycle $(1\,3\,2\,4\,9)$.
Now we start a new cycle with the first missing number, which is $6$.
$6\to 8$ for $(6\,8\,\ldots)$.
$8\to 12$ for $(6\,8\,12\,\ldots)$.
$12\to 6$, which completes the cycle $(6\,8\,12)$.
So $\pi_1=(1\,3\,2\,4\,9)(6\,8\,12)$. And yes, that is the same decomposition that you have, although the numbers are in a different order. #### mathmari

##### Well-known member
MHB Site Helper
Don't we have $1\to 3$? Anyway, here's a slightly different way to find it.
Let's start with $1$.
$1 \to 3$ for $(1\,3\,\ldots)$.
$3\to 1 \to 2$ for $(1\,3\,2\,\ldots)$.
$2\to 4$ for $(1\,3\,2\,4\,\ldots)$.
$4\to 9$ for $(1\,3\,2\,4\,9\,\ldots)$.
$9\to 1$, which completes the cycle $(1\,3\,2\,4\,9)$.
Now we start a new cycle with the first missing number, which is $6$.
$6\to 8$ for $(6\,8\,\ldots)$.
$8\to 12$ for $(6\,8\,12\,\ldots)$.
$12\to 6$, which completes the cycle $(6\,8\,12)$.
So $\pi_1=(1\,3\,2\,4\,9)(6\,8\,12)$. And yes, that is the same decomposition that you have, although the numbers are in a different order. Ahh that means that my result is also correct, isn't it? #### Klaas van Aarsen

##### MHB Seeker
Staff member
Ahh that means that my result is also correct, isn't it?
Yep. #### mathmari

##### Well-known member
MHB Site Helper
Yep. Ok!!

As for the inverse permutations, do we reverse the cycles and also the elements of each cycle? So, the cycle decompositions of the permutations are:
- $\pi_1=(12 \ 6 \ 8)\ (3 \ 2 \ 4 \ 9 \ 1)$
- $\pi_2=(2 \ 4\ 5 \ 8\ 7)\ (1 \ 12 \ 6) \ (13 \ 14)$
- $\pi_3=(1 \ 2 \ 5 \ 4 \ 6 \ 8 \ 11)$
So do we get the following?

- $\pi_1^{-1}=(1 \ 9 \ 4 \ 2 \ 3) \ (8 \ 6 \ 12)$
- $\pi_2^{-1}=(14 \ 13) \ (6 \ 12 \ 1) \ (7 \ 8 \ 5 \ 4 \ 2)$
- $\pi_3^{-1}= (11 \ 8 \ 6 \ 4 \ 5 \ 2 \ 1)$ #### Klaas van Aarsen

##### MHB Seeker
Staff member
Ok!!

As for the inverse permutations, do we reverse the cycles and also the elements of each cycle? So do we get the following?

- $\pi_1^{-1}=(1 \ 9 \ 4 \ 2 \ 3) \ (8 \ 6 \ 12)$
- $\pi_2^{-1}=(14 \ 13) \ (6 \ 12 \ 1) \ (7 \ 8 \ 5 \ 4 \ 2)$
- $\pi_3^{-1}= (11 \ 8 \ 6 \ 4 \ 5 \ 2 \ 1)$
Yep. Btw, since the cycles are disjoint, their order does not matter. #### mathmari

##### Well-known member
MHB Site Helper
Yep. Btw, since the cycles are disjoint, their order does not matter. That means that since these are disjoint it is enough to reverse the elements inside the cycles? #### Klaas van Aarsen

##### MHB Seeker
Staff member
That means that since these are disjoint it is enough to reverse the elements inside the cycles?
Yep. #### mathmari

##### Well-known member
MHB Site Helper
3. Determine $\pi_4=\pi_1\circ \pi_2$, $\pi_5=\pi_2\circ\pi_3$, $\pi_6=\pi_2\circ\pi_1$.
Do we just write each permutation or is it maybe meant to find the cycle decomposition also of these ones? We have the following:

$\pi_4=\pi_1\circ \pi_2=(12 \ 6 \ 8)\ (3 \ 2 \ 4 \ 9 \ 1)(2 \ 4\ 5 \ 8\ 7)\ (1 \ 12 \ 6) \ (13 \ 14)$

From that we get:

14 -> 13

13-> 14

6 -> 1 -> 3

1 -> 12 -> 6

12 -> 6 -> 8

7 -> 2 -> 4

2 -> 4 -> 9

4 -> 5

5 -> 8 -> 12

8 -> 7

1 -> 3

3 -> 2

2 -> 4

4 -> 9

9 -> 1

8 -> 12

12 -> 6

6 -> 8

Have I done that correctly? Because now for example the element $2$ goes to two different elements. #### Klaas van Aarsen

##### MHB Seeker
Staff member
Do we just write each permutation or is it maybe meant to find the cycle decomposition also of these ones?
I suspect that when they write 'determine' that they mean to find a cycle decomposition.
Otherwise the answer would be trivial - that is, we could simply write the given transformations after each other. We have the following:

$\pi_4=\pi_1\circ \pi_2=(12 \ 6 \ 8)\ (3 \ 2 \ 4 \ 9 \ 1)(2 \ 4\ 5 \ 8\ 7)\ (1 \ 12 \ 6) \ (13 \ 14)$

From that we get:

14 -> 13
...
6 -> 8

Have I done that correctly? Because now for example the element $2$ goes to two different elements.
I didn't check them all, but indeed it can't be right that $2$ is in this list twice, nor that it maps to two different elements. Why is it in the list twice?

#### mathmari

##### Well-known member
MHB Site Helper
I didn't check them all, but indeed it can't be right that $2$ is in this list twice, nor that it maps to two different elements. Why is it in the list twice?
We start from the right-most cycle, right? Then we have the element $2$ and see that this goes to $4$ and $4$ goes to $9$, so $2$ goes to $9$.
At the second cycle we have again the element $2$. When we reach this cycle do we check again the element $2$ ? #### Klaas van Aarsen

##### MHB Seeker
Staff member
We start from the right-most cycle, right? Then we have the element $2$ and see that this goes to $4$ and $4$ goes to $9$, so $2$ goes to $9$.
At the second cycle we have again the element $2$. When we reach this cycle do we check again the element $2$ ?
No. When we consider the image of an element such as $2$, we must evaluate all cycles from right to left. We are not supposed to start in the middle. #### mathmari

##### Well-known member
MHB Site Helper
Ok !!

Now I think I got the right results :

$\pi_4=\pi_1\circ\pi_2=(14\ 13) \ (6\ 3\ 2\ 9\ 1)\ (12\ 8\ 7\ 4\ 5)$

$\pi_5=\pi_2\circ\pi_3=(1\ 4) \ (2\ 8\ 11\ 12\ 6\ 7)\ (13\ 14)$

$\pi_6=\pi_2\circ\pi_1=(3 \ 4 \ 9 \ 12\ 1) \ (2\ 5\ 8\ 6\ 7)\ (13 \ 14)$

For the signum we have to write each permutation as a product of cycles of two elements, right? How can we do that? #### Klaas van Aarsen

##### MHB Seeker
Staff member
For the signum we have to write each permutation as a product of cycles of two elements, right? How can we do that?
We can write $(a\,b\,c\,d)$ for instance as either $(a\,d)(a\,c)(a\,b)$ or $(a\,b)(b\,c)(c\,d)$. Note that more generally a cycle with an even number of elements can be written as an odd number of 2-cycles (signum -1).
And a cycle with an odd number of elements can be written as an even number of 2-cycles (signum +1). #### mathmari

##### Well-known member
MHB Site Helper
I am looking aagain at the previous question, at the calculation of $\pi_4$. Do we get the same results if we use the initially given $\pi_1$ and $\pi_2$ and the same if we use the cycle decomposition of them? I get the following from the cycle decomposition:

$\pi_1=(8 \ 6 \ 12)\ (1 \ 9 \ 4 \ 2 \ 3 )$

$\pi_2=(7 \ 8 \ 5 \ 4 \ 2)\ (6 \ 12 \ 1 ) \ (14 \ 13)$

$\pi_4=\pi_1\circ\pi_2=(8 \ 6 \ 12)\ (1 \ 9 \ 4 \ 2 \ 3 ) \ (7 \ 8 \ 5 \ 4 \ 2)\ (6 \ 12 \ 1 ) \ (14 \ 13)$

$14\rightarrow 13$

$13\rightarrow 14$

$6\rightarrow 12\rightarrow 8$

$12\rightarrow 1\rightarrow 9$

$1\rightarrow 6\rightarrow 12$

$7\rightarrow 8\rightarrow 6$

$8\rightarrow 5$

$5\rightarrow 4\rightarrow 2$

$4\rightarrow 2\rightarrow 3$

$2\rightarrow 7$

$9\rightarrow 4$

$3\rightarrow 1$

So $\pi_4=(14 \ 13) \ (6 \ 8 \ 5 \ 2 \ 7) \ (12 \ 9 \ 4 \ 3 \ 1)$.

And from the initially given forms:

$\pi_1=(1 \ 2\ 4 \ 9)\ (1\ 3)\ (6 \ 8 \ 12)$

$\pi_2=(2 \ 4\ 5 \ 8 \ 7)\ ( 1 \ 12 \ 6) \ (13 \ 14)$

$\pi_4=\pi_1\circ\pi_2=(1 \ 2\ 4 \ 9)\ (1\ 3)\ (6 \ 8 \ 12) \ (2 \ 4\ 5 \ 8 \ 7)\ ( 1 \ 12 \ 6) \ (13 \ 14)$

$13 \rightarrow 14$

$14\rightarrow 13$

$1\rightarrow 12 \rightarrow 6$

$12\rightarrow 6\rightarrow 8$

$6\rightarrow 1 \rightarrow 3$

$2\rightarrow 4\rightarrow 9$

$4\rightarrow 5$

$5\rightarrow 8\rightarrow 12$

$8\rightarrow 7$

$7\rightarrow 2\rightarrow 4$

$3\rightarrow 1\rightarrow 2$

$9\rightarrow 1$

So $\pi_4=(13 \ 14) \ (1 \ 6 \ 3 \ 2 \ 9 ) \ (12 \ 8 \ 7 \ 4 \ 5)$.

Have I done something wrong or is it correct that we get different results? 