Welcome to our community

Be a part of something great, join today!

Determine the cycle decomposition of the permutations

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
3,958
Hey!! :eek:

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?

(Wondering)
 
Last edited:

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,599
Leiden
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. (Nod)

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. (Thinking)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
3,958
Yes, this is the way to decompose the permutation into disjoint cycles. (Nod)
Aren't the first two permutations already the decomposition into disjoint cycles? (Wondering)

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? (Wondering)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,599
Leiden
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. (Thinking)

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? (Wondering)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
3,958

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,599
Leiden

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
3,958
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? (Wondering)

At the first two do we consider the product of the cycles or the composition as we had initially? (Wondering)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,599
Leiden
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? (Worried)

At the first two do we consider the product of the cycles or the composition as we had initially?
Huh? :confused:
Which 'first two'?
Which question are we talking about?
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
3,958
The cycles in $\pi_1$ are not disjoint are they?
Isn't $1$ in multiple cycles? (Worried)
Oh yes, you are right! (Tmi)

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? (Wondering)


Huh? :confused:
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? (Wondering)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,599
Leiden
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? (Worried)

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. (Nerd)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
3,958
Doesn't $\pi_1$ have two cycles with $2$ in them now? (Worried)
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. (Wondering)

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? (Wondering)


Ah no, there is no difference.
The product of cycles is defined as the composition. They are the same. (Nerd)
Ahh ok!! (Malthe)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,599
Leiden
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. (Wondering)

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? (Wondering)
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$? (Worried)

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)$. (Nerd)

And yes, that is the same decomposition that you have, although the numbers are in a different order. (Happy)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
3,958
Don't we have $1\to 3$? (Worried)

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)$. (Nerd)

And yes, that is the same decomposition that you have, although the numbers are in a different order. (Happy)
Ahh that means that my result is also correct, isn't it? (Wondering)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,599
Leiden

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
3,958
Ok!!

As for the inverse permutations, do we reverse the cycles and also the elements of each cycle? (Wondering)

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)$

(Wondering)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,599
Leiden
Ok!!

As for the inverse permutations, do we reverse the cycles and also the elements of each cycle? (Wondering)

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. (Nod)

Btw, since the cycles are disjoint, their order does not matter. (Nerd)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
3,958
Yep. (Nod)

Btw, since the cycles are disjoint, their order does not matter. (Nerd)
That means that since these are disjoint it is enough to reverse the elements inside the cycles? (Wondering)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,599
Leiden

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
3,958
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? (Wondering)

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. (Wondering)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,599
Leiden
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. (Thinking)

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. (Worried)
Why is it in the list twice?
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
3,958
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. (Worried)
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$ ? (Wondering)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,599
Leiden
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. (Shake)
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. (Worried)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
3,958
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? (Wondering)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,599
Leiden
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)$. (Thinking)

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). (Nerd)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
3,958
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? (Wondering)

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? (Wondering)