Determine the cycle decomposition of the permutations

In summary, the conversation involved determining the cycle decomposition, inverse, composition, and signum of given permutations. There was also discussion about whether to consider the product or composition of cycles and how to properly write the cycle decompositions. Eventually, the correct cycle decompositions were determined for the given permutations.
  • #1
mathmari
Gold Member
MHB
5,049
7
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 by a moderator:
Physics news on Phys.org
  • #2
mathmari said:
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)

mathmari said:
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)
 
  • #3
Klaas van Aarsen said:
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)
 
  • #4
mathmari said:
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)

mathmari said:
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)
 
  • #5
Klaas van Aarsen said:
Yep.
Can we write it as disjoint cycles? (Wondering)

So we get $\pi_3=(1 \ 2 \ 5 \ 4 \ 6 \ 8 \ 11)$, or not? (Wondering)
 
  • #6
mathmari said:
So we get $\pi_3=(1 \ 2 \ 5 \ 4 \ 6 \ 8 \ 11)$, or not?

Yep. (Nod)
 
  • #7
Klaas van Aarsen said:
Yep. (Nod)

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)
 
  • #8
mathmari said:
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)

mathmari said:
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?
 
  • #9
Klaas van Aarsen said:
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)
Klaas van Aarsen said:
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)
 
  • #10
mathmari said:
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)

mathmari said:
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)
 
  • #11
Klaas van Aarsen said:
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)


Klaas van Aarsen said:
Ah no, there is no difference.
The product of cycles is defined as the composition. They are the same. (Nerd)

Ahh ok! (Malthe)
 
  • #12
mathmari said:
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)

mathmari said:
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)
 
  • #13
Klaas van Aarsen said:
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)
 
  • #14
mathmari said:
Ahh that means that my result is also correct, isn't it?

Yep. (Nod)
 
  • #15
Klaas van Aarsen said:
Yep. (Nod)

Ok!

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

mathmari said:
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)
 
  • #16
mathmari said:
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)
 
  • #17
Klaas van Aarsen said:
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)
 
  • #18
mathmari said:
That means that since these are disjoint it is enough to reverse the elements inside the cycles?

Yep. (Nod)
 
  • #19
mathmari said:
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)
 
  • #20
mathmari said:
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)

mathmari said:
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?
 
  • #21
Klaas van Aarsen said:
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)
 
  • #22
mathmari said:
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)
 
  • #23
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)
 
  • #24
mathmari said:
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)
 
  • #25
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)
 
  • #26
The original $\pi_2$ was already disjoint and contained (1 12 6). But it's not like that in both your cases, is it? (Worried)
 
  • #27
Klaas van Aarsen said:
The original $\pi_2$ was already disjoint and contained (1 12 6). But it's not like that in both your cases, is it? (Worried)

What do you mean? I got stuck right now. (Wondering)
 
  • #28
mathmari said:
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)$

You wrote (6 12 1) here.

mathmari said:
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 \ 1
4)$

And you wrote (1 12 6) here.
Shouldn't they be the same? (Wondering)

Did you perhaps accidentally write $\pi_2^{-1}$ instead of the decomposition? (Wondering)
 
  • #29
Klaas van Aarsen said:
You wrote (6 12 1) here.
And you wrote (1 12 6) here.
Shouldn't they be the same? (Wondering)

Did you perhaps accidentally write $\pi_2^{-1}$ instead of the decomposition? (Wondering)

Oh yes, you are right! I used theinverse accidentaly. (Tmi)

So we get the same result using the initial permutation and the cycle decomposition of it.
 

Related to Determine the cycle decomposition of the permutations

1. What is a cycle decomposition of a permutation?

A cycle decomposition is a way of representing a permutation as a product of disjoint cycles. It shows how the permutation rearranges the elements of a set.

2. How do you determine the cycle decomposition of a permutation?

To determine the cycle decomposition of a permutation, you first write out the permutation in cycle notation. Then, you identify the elements that are moved by the permutation and group them into cycles. Finally, you write out the cycles in order from left to right.

3. Can a permutation have more than one cycle decomposition?

No, a permutation can only have one cycle decomposition. This is because the cycle decomposition is a unique representation of a permutation.

4. How can the cycle decomposition of a permutation be useful?

The cycle decomposition of a permutation can be useful in solving problems related to permutations, such as finding the order of a permutation or determining whether two permutations commute.

5. Are there any shortcuts or tricks for determining the cycle decomposition of a permutation?

Yes, there are some techniques that can make determining the cycle decomposition of a permutation easier. These include looking for fixed points, using the inverse of the permutation, and using the disjoint cycle notation. However, these techniques may not work for all permutations and it is still important to understand the concept of cycle decomposition.

Similar threads

  • Linear and Abstract Algebra
Replies
23
Views
2K
  • Linear and Abstract Algebra
Replies
8
Views
999
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Linear and Abstract Algebra
Replies
8
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
916
  • Linear and Abstract Algebra
Replies
7
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
5
Views
1K
  • Linear and Abstract Algebra
Replies
13
Views
1K
Back
Top