Proving Permutation Inverses: (1 2 3) = (4 5 6)

[Justabeginner]

Homework Statement

Prove that there is a permutation sigma, such that sigma * (1 2 3) * sigma inverse= (4 5 6).

Homework Equations

The Attempt at a Solution

I know that since the order of the two cycles is the same there must be a sigma such that the two permutations are equal but I am stumped as to how to derive a specific one. Would I have to do proof by contradiction using identity as was done in an earlier problem I completed or am I way off?

Thank you!

 

[Fredrik]

Homework Statement

Prove that there is a permutation sigma, such that sigma * (1 2 3) * sigma inverse= (4 5 6).

Homework Equations

The Attempt at a Solution

I know that since the order of the two cycles is the same there must be a sigma such that the two permutations are equal but I am stumped as to how to derive a specific one. Would I have to do proof by contradiction using identity as was done in an earlier problem I completed or am I way off?

Thank you!

I don't see how to make sense of the product $\sigma(1\ 2\ 3)\sigma^{-1}$ unless I interpret (1 2 3) as a permutation (not as an element of the domain of $\sigma$). Is (x y z) your notation for the permutation f such that f(1)=x, f(2)=y, f(3)=z? In that case, (1 2 3) is the identity map, and the product is equal to (1 2 3) no matter what $\sigma$ is.

 

[gopher_p]

I don't see how to make sense of the product $\sigma(1\ 2\ 3)\sigma^{-1}$ unless I interpret (1 2 3) as a permutation (not as an element of the domain of $\sigma$). Is (x y z) your notation for the permutation f such that f(1)=x, f(2)=y, f(3)=z? In that case, (1 2 3) is the identity map, and the product is equal to (1 2 3) no matter what $\sigma$ is.

In an introductory abstract algebra course, and in the proper context, $(a_1\dots a_n)$ is standard notation denoting the cyclic permutation mapping $a_i$ to $a_{i+1}$ for $i<n$ and $a_n$ to $a_1$.

 

[gopher_p]

I know that since the order of the two cycles is the same there must be a sigma such that the two permutations are equal.

If the problem just asks you to prove the existence of such a permutation, then you can just invoke whatever theorem it is that is allowing you to make the above statement. You don't necessarily need to construct a permutation.

 

[pasmith]

Homework Statement

Prove that there is a permutation sigma, such that sigma * (1 2 3) * sigma inverse= (4 5 6).

Homework Equations

The Attempt at a Solution

I know that since the order of the two cycles is the same there must be a sigma such that the two permutations are equal but I am stumped as to how to derive a specific one. Would I have to do proof by contradiction using identity as was done in an earlier problem I completed or am I way off?

Thank you!

Hint: (1 4)(1 2 3)(1 4) = (2 3 4). Can you now see how to construct your sigma as a product of disjoint transpositions?

 

[Ray Vickson]

In an introductory abstract algebra course, and in the proper context, $(a_1\dots a_n)$ is standard notation denoting the cyclic permutation mapping $a_i$ to $a_{i+1}$ for $i<n$ and $a_n$ to $a_1$.

OK, but what does $(1\,2\,3)$ stand for when the permutations go over the numbers $1, \ldots, 6$ ?

 

[Justabeginner]

I am actually having a difficulty understanding how to construct permutations into disjoint cycles, and I am trying to read various sources but it still does not make sense. My book works from right to left for disjoint cycles. Can someone please explain it to me? Thank you.

 

[pasmith]

OK, but what does $(1\,2\,3)$ stand for when the permutations go over the numbers $1, \ldots, 6$ ?

The permutation which cyclically permutes 1, 2 and 3 and fixes 4, 5, and 6. By convention elements which are fixed are omitted from the cycle notation.

 

[Justabeginner]

The permutation which cyclically permutes 1, 2 and 3 and fixes 4, 5, and 6. By convention elements which are fixed are omitted from the cycle notation.

That helped me understand cycle notation a bit better, thank you.

So am I correct in making this assumption now?
(1 2 3 4 5 6
2 3 1 4 5 6) times sigma times sigma inverse equals:

(1 2 3 4 5 6
1 2 3 5 6 4)

Am I allowed to simplify this?

 

[Justabeginner]

Shameless bump... sorry!

 

[Fredrik]

Gopher and pasmith explained the (x ... y) notation, but no one has explained what it means when it's broken up over two lines. Can I assume that
(1 2 3 4 5 6
2 3 1 4 5 6)
is the permutation that takes 1 to 2, 2 to 3, 3 to 1, and the other numbers to themselves? In other words, it means exactly the same as (1 2 3)? Then you're asking if $(1\ 2\ 3)\sigma\sigma^{-1}=(4\ 5\ 6)$? The left-hand side is obviously equal to (1 2 3), so no, this equality doesn't hold.

 

[Justabeginner]

Hi Fredrik, yes I believe (1 2 3) is just the shortened form of the cycle that takes 1 to 2, 2 to 3, 3 to 1, and maps 4, 5, 6 to themselves.
I was confused as to how that would hold too, and I am still not sure if I understood the meaning correctly.

 

[Fredrik]

Groups of permutations aren't commutative (Abelian), so you don't have xy=yx for all x,y. This means that you need to keep your factors in the correct order.

 

[Justabeginner]

So I should not expand the permutations and just keep them as they are written in the question? I do not understand how that will allow me to conclude anything, though.

 

[Fredrik]

pasmith gave you a huge hint in post #5. It would be hard to tell you more without completely solving the problem.

 

[Justabeginner]

pasmith gave you a huge hint in post #5. It would be hard to tell you more without completely solving the problem.

I do not wish to get the answer from others, nor do I want it to seem like that.
I am simply confused on how to make disjoint transpositions (from right to left) and I would appreciate it if I could get a detailed example and explanation, so I can understand this concept before attempting the problem. I've looked in various sources for explanations but I can't quite wrap my head around it.

 

[jbunniii]

I do not wish to get the answer from others, nor do I want it to seem like that.
I am simply confused on how to make disjoint transpositions (from right to left) and I would appreciate it if I could get a detailed example and explanation, so I can understand this concept before attempting the problem. I've looked in various sources for explanations but I can't quite wrap my head around it.

One way to transform (1 2 3) to (4 5 6) is to transpose 1 and 4, transpose 2 and 5, and transpose 3 and 6. Can you combine this fact with the hint given by pasmith?

 

[jbunniii]

Gopher and pasmith explained the (x ... y) notation, but no one has explained what it means when it's broken up over two lines. Can I assume that
(1 2 3 4 5 6
2 3 1 4 5 6)
is the permutation that takes 1 to 2, 2 to 3, 3 to 1, and the other numbers to themselves? In other words, it means exactly the same as (1 2 3)?

Yes, that's exactly what it means. This so-called two-line notation is due to Cauchy, according to Wikipedia:

http://en.wikipedia.org/wiki/Permutation#Definition_and_usage

 

[Justabeginner]

One way to transform (1 2 3) to (4 5 6) is to transpose 1 and 4, transpose 2 and 5, and transpose 3 and 6. Can you combine this fact with the hint given by pasmith?

Is the transposition you described equivalent to (1 4) (2 5) (3 6)?

And in that case would (1 2 3)= (1 3) (1 2)? Also, (4 5 6)= (4 6) (4 5)?

 

[jbunniii]

Is the transposition you described equivalent to (1 4) (2 5) (3 6)?

Yes, technically it's not a transposition (which interchanges exactly two elements and leaves the rest unchanged), but a composition of transpositions.

Now how can you use (1 4) (2 5) (3 6) to map (1 2 3) to (4 5 6)?

Hint: if $\sigma$ is any permutation, then $\sigma (x_1 x_2 \ldots x_n)\sigma^{-1} = (\sigma(x_1) \sigma(x_2) \ldots \sigma(x_n))$

 

[Justabeginner]

So, sigma *((1 4) (2 5) (3 6)) * sigma^-1 = sigma(1 4) sigma (2 5) sigma (3 6).
There is one operation that transforms these to be equal to each other; is it a matter of guess and check to determine this, or can I systematically eliminate?

 

[jbunniii]

So, sigma *((1 4) (2 5) (3 6)) * sigma^-1 = sigma(1 4) sigma (2 5) sigma (3 6).
There is one operation that transforms these to be equal to each other; is it a matter of guess and check to determine this, or can I systematically eliminate?

No, that's not quite right. The goal is to transform (1 2 3) to (4 5 6). So let's start by writing what we hope to achieve:
$$\sigma (1 2 3) \sigma^{-1} = (4 5 6) = (\sigma(1) \sigma(2) \sigma(3))$$
Now we need to find a permutation $\sigma$ which makes this equation true. Let's do this in three steps, and then at the end, we will conclude what $\sigma$ must be.

If you take a look back at pasmith's hint, we have
$$(1 4) (1 2 3) (1 4) = (2 3 4)$$
I will rewrite the cycle on the right hand side in a more suggestive but equivalent way:
$$(1 4) (1 2 3) (1 4) = (4 2 3)$$
What this shows is that if we start with (1 2 3), and multiply on both sides by (1 4), we get (4 2 3). In other words, the 1 is replaced by 4 and everything else stays the same. So we have achieved one step out of three. Can you see what the next step is, to obtain (4 5 3) on the right hand side?

 

[Justabeginner]

In other words, the 1 is replaced by 4 and everything else stays the same. So we have achieved one step out of three. Can you see what the next step is, to obtain (4 5 3) on the right hand side?

So can one do (1 4) (1 5 3) (1 4) to obtain (4 5 3)?
And then to obtain (4 5 6) do (1 4) (1 6 3) (1 4)?

 

[jbunniii]

So can one do (1 4) (1 5 3) (1 4) to obtain (4 5 3)?

One can do that, but you didn't have (1 5 3) to start with, so this doesn't help. In the first step, we got as far as (4 2 3). How can we transform (4 2 3) to (4 5 3)?

And then to obtain (4 5 6) do (1 4) (1 6 3) (1 4)?

No... (1 4)(1 6 3)(1 4) would be (4 6 3).

 

[Justabeginner]

One can do that, but you didn't have (1 5 3) to start with, so this doesn't help. In the first step, we got as far as (4 2 3). How can we transform (4 2 3) to (4 5 3)?

No... (1 4)(1 6 3)(1 4) would be (4 6 3).

To get from (4 2 3) to (4 5 3) replace 2 with 5. So (1 4) (1 2 5) (1 4)?

 

[jbunniii]

To get from (4 2 3) to (4 5 3) replace 2 with 5. So (1 4) (1 2 5) (1 4)?

No, it should be of the form

(something) (4 2 3) (something) = (4 5 3)

What "something" will achieve this?

 

[Justabeginner]

No, it should be of the form

(something) (4 2 3) (something) = (4 5 3)

What "something" will achieve this?

I didn't realize I could change the equations on the outside because I thought I could only work with what was originally there.
(1 5) (4 2 3) (1 5) = (4 5 3)?

 

[jbunniii]

I didn't realize I could change the equations on the outside because I thought I could only work with what was originally there.
(1 5) (4 2 3) (1 5) = (4 5 3)?

No, neither 1 nor 5 appears in (4 2 3), so conjugating by (1 5) won't have any effect. You can also see this by working out the result of the composition explicitly.

If I want to transform (4 2 3) to (4 5 3), then I want to map 2 to 5, right?

 

[Justabeginner]

No, neither 1 nor 5 appears in (4 2 3), so conjugating by (1 5) won't have any effect. You can also see this by working out the result of the composition explicitly.

If I want to transform (4 2 3) to (4 5 3), then I want to map 2 to 5, right?

Yes, 2 has to be changed to 5.
Would it be (2 5) (4 2 3) (2 5)?

 

[jbunniii]

Yes, 2 has to be changed to 5.
Would it be (2 5) (4 2 3) (2 5)?

Yes, that's right. So this gives you (2 5) (4 2 3) (2 5) = (4 5 3).

Now can you see how to map (4 5 3) to (4 5 6)?

 

[Justabeginner]

Yes, that's right. So this gives you (2 5) (4 2 3) (2 5) = (4 5 3).

Now can you see how to map (4 5 3) to (4 5 6)?

I think it should be (3 6) (4 5 3) (3 6)?

 

[jbunniii]

I think it should be (3 6) (4 5 3) (3 6)?

Yes, that's right. So let's recap:

(1 4) (1 2 3) (1 4) = (4 2 3)
(2 5) (4 2 3) (2 5) = (4 5 3)
(3 6) (4 5 3) (3 6) = (4 5 6)

Can you combine these three facts to get the form we need:

$\sigma$ (1 2 3) $\sigma^{-1}$ = (4 5 6)

What should $\sigma$ be in order to make this true?

 

[Justabeginner]

yes, that's right. So let's recap:

(1 4) (1 2 3) (1 4) = (4 2 3)
(2 5) (4 2 3) (2 5) = (4 5 3)
(3 6) (4 5 3) (3 6) = (4 5 6)

can you combine these three facts to get the form we need:

$\sigma$ (1 2 3) $\sigma^{-1}$ = (4 5 6)

what should $\sigma$ be in order to make this true?

Should sigma be (1 4 2 5 3 6)?

 

[jbunniii]

Should sigma be (1 4 2 5 3 6)?

You can check to see if it works. Is it true that

(1 4 2 5 3 6) (1 2 3) (1 4 2 5 3 6)$^{-1}$ = (4 5 6)?

Try calculating the left hand side and see what you get. First step: what is (1 4 2 5 3 6)$^{-1}$?

 

[Justabeginner]

You can check to see if it works. Is it true that

(1 4 2 5 3 6) (1 2 3) (1 4 2 5 3 6)$^{-1}$ = (4 5 6)?

Try calculating the left hand side and see what you get. First step: what is (1 4 2 5 3 6)$^{-1}$?

It should be the exact opposite? (6 3 5 2 4 1)?
Then that would mean 6 goes in the first position, but 4 should be.. so that is wrong?
I should have sigma = (4 x x x x x) (1 5 3) (x x x x x 4)?

 

[jbunniii]

It should be the exact opposite? (6 3 5 2 4 1)?

Correct.

Then that would mean 6 goes in the first position, but 4 should be.. so that is wrong?
I should have sigma = (4 x x x x x) (1 5 3) (x x x x x 4)?

Keep in mind that if you "rotate" the elements of a cycle, it's still the same permutation. So all six of the following are the same thing:

(6 3 5 2 4 1)
(3 5 2 4 1 6)
(5 2 4 1 6 3)
(2 4 1 6 3 5)
(4 1 6 3 5 2)
(1 6 3 5 2 4)

 

[Justabeginner]

Correct.

Keep in mind that if you "rotate" the elements of a cycle, it's still the same permutation. So all six of the following are the same thing:

(6 3 5 2 4 1)
(3 5 2 4 1 6)
(5 2 4 1 6 3)
(2 4 1 6 3 5)
(4 1 6 3 5 2)
(1 6 3 5 2 4)

So, (6 3 5 2 4 1) (1 2 3) (6 3 5 2 4 1) = (4 5 6), holds true. 4 is in the 1st position, 5 is in the 2nd position, and 3 is in the 3rd position.

 

[jbunniii]

So, (6 3 5 2 4 1) (1 2 3) (6 3 5 2 4 1) = (4 5 6)

That's not what I get:
$1 \mapsto 6 \mapsto 3$
$2 \mapsto 4 \mapsto 1$
$3 \mapsto 5 \mapsto 2$
$4 \mapsto 1 \mapsto 2 \mapsto 4$
$5 \mapsto 2 \mapsto 3 \mapsto 5$
$6 \mapsto 3 \mapsto 1 \mapsto 6$
Therefore, (6 3 5 2 4 1) (1 2 3) (6 3 5 2 4 1) = (1 3 2).

Also, your map is not of the form $\sigma$ (1 2 3) $\sigma^{-1}$.

 

[Justabeginner]

That's not what I get:
$1 \mapsto 6 \mapsto 3$
$2 \mapsto 4 \mapsto 1$
$3 \mapsto 5 \mapsto 2$
$4 \mapsto 1 \mapsto 2 \mapsto 4$
$5 \mapsto 2 \mapsto 3 \mapsto 5$
$6 \mapsto 3 \mapsto 1 \mapsto 6$
Therefore, (6 3 5 2 4 1) (1 2 3) (6 3 5 2 4 1) = (1 3 2).

Also, your map is not of the form $\sigma$ (1 2 3) $\sigma^{-1}$.

I don't understand how 1 maps to 6, which maps to 3, etc.
I'm not able to follow that.
(6 3 5 2 4 1) (1 2 3) (1 4 2 3 5 6) =

 

[jbunniii]

I don't understand how 1 maps to 6, which maps to 3, etc.
I'm not able to follow that.
(6 3 5 2 4 1) (1 2 3) (1 4 2 3 5 6)

In your previous post #37, you said that the solution is (6 3 5 2 4 1) (1 2 3) (6 3 5 2 4 1). Now you wrote (6 3 5 2 4 1) (1 2 3) (1 4 2 3 5 6). These are not the same thing. Which one is your solution?

 

[Justabeginner]

In your previous post #37, you said that the solution is (6 3 5 2 4 1) (1 2 3) (6 3 5 2 4 1). Now you wrote (6 3 5 2 4 1) (1 2 3) (1 4 2 3 5 6). These are not the same thing. Which one is your solution?

(6 3 5 2 4 1) (1 2 3) (1 4 2 3 5 6) is my solution because the form is of sigma * (1 2 3) * sigma inverse = (4 5 6).

 

[jbunniii]

(6 3 5 2 4 1) (1 2 3) (1 4 2 3 5 6) is my solution because the form is of sigma * (1 2 3) * sigma inverse = (4 5 6).

OK, so let's compute what (6 3 5 2 4 1) (1 2 3) (1 4 2 3 5 6) does to each element in $\{1,2,3,4,5,6\}$:
It maps them as follows:

$1 \mapsto 4 \mapsto 1$
$2 \mapsto 3 \mapsto 1 \mapsto 6$
$3 \mapsto 5 \mapsto 2$
$4 \mapsto 2 \mapsto 3 \mapsto 5$
$5 \mapsto 6 \mapsto 3$
$6 \mapsto 1 \mapsto 2 \mapsto 4$

So it is equivalent to (2 6 4 5 3), not (4 5 6).

 

[Justabeginner]

OK, so let's compute what (6 3 5 2 4 1) (1 2 3) (1 4 2 3 5 6) does to each element in $\{1,2,3,4,5,6\}$:
It maps them as follows:

$1 \mapsto 4 \mapsto 1$
$2 \mapsto 3 \mapsto 1 \mapsto 6$
$3 \mapsto 5 \mapsto 2$
$4 \mapsto 2 \mapsto 3 \mapsto 5$
$5 \mapsto 6 \mapsto 3$
$6 \mapsto 1 \mapsto 2 \mapsto 4$

So it is equivalent to (2 6 4 5 3), not (4 5 6).

I don't understand how you conclude 1 maps to 4 maps to 1, 2 maps to 3 maps to 1 maps to 6.. Can you explain that please?

 

[Fredrik]

I don't understand how you conclude 1 maps to 4 maps to 1, 2 maps to 3 maps to 1 maps to 6.. Can you explain that please?

(1 4 2 3 5 6) maps 1 to 4. (1 2 3) maps 4 to 4. (6 3 5 2 4 1) maps 4 to 1.
So (6 3 5 2 4 1) (1 2 3) (1 4 2 3 5 6) maps 1 to 1.

(1 4 2 3 5 6) maps 2 to 3. (1 2 3) maps 3 to 1. (6 3 5 2 4 1) maps 1 to 6.
So (6 3 5 2 4 1) (1 2 3) (1 4 2 3 5 6) maps 2 to 6.

...and so on.

Edit: Wait a second. This contradicts Wikipedia's definition of the notation. Let me think for a minute.

OK, according to Wikipedia (1 4 2 3 5 6) takes 1 to 1, 2 to 4, 3 to 2, and so on. Not 1 to 4, 4 to 2, and so on. I'm confused. What notation are we using in this problem? I thought (1 2 3) was supposed to be the permutation that takes 1 to 2, 2 to 3 and 3 to 2, but with Wikipedia's convention, (1 2 3) is the identity map.

 

[Justabeginner]

(1 4 2 3 5 6) maps 1 to 4. (1 2 3) maps 4 to 4. (6 3 5 2 4 1) maps 4 to 1.
So (6 3 5 2 4 1) (1 2 3) (1 4 2 3 5 6) maps 1 to 1.

(1 4 2 3 5 6) maps 2 to 3. (1 2 3) maps 3 to 1. (6 3 5 2 4 1) maps 1 to 6.
So (6 3 5 2 4 1) (1 2 3) (1 4 2 3 5 6) maps 2 to 6.

...and so on.

Okay, I think I understand now. First it maps within the cycle, then to the next cycle if the number is contained in the cycle, but if the number isn't (like the first one) then the number maps to itself.

 

[jbunniii]

Okay, I think I understand now. First it maps within the cycle, then to the next cycle if the number is contained in the cycle, but if the number isn't (like the first one) then the number maps to itself.

Yes, that's correct. And if the number appears at the end of the cycle, then you "wrap around" to the beginning. So for example, (1 2 3) maps 3 to 1.

Also, I'm assuming that composition is from right to left, which is the usual convention, for consistency with function notation. Just as $f \circ g \circ h$ means "first apply $h$, then $g$, then $f$", (6 3 5 2 4 1) (1 2 3) (1 4 2 3 5 6) means "first apply (1 4 2 3 5 6), then (1 2 3), then (6 3 5 2 4 1)." Some people (mostly old-fashioned group theorists) write mappings from left to right.

 

[Fredrik]

Okay, I think I understand now. First it maps within the cycle, then to the next cycle if the number is contained in the cycle, but if the number isn't (like the first one) then the number maps to itself.

I was just using that the "product" in a group of permutations is composition of functions. So (fgh)(x)=f(g(h(x))). But I may also have used the wrong definition of the one-line notation. See the edit of my previous post.

 

[jbunniii]

OK, according to Wikipedia (1 4 2 3 5 6) takes 1 to 1, 2 to 4, 3 to 2, and so on. Not 1 to 4, 4 to 2, and so on. I'm confused. What notation are we using in this problem? I thought (1 2 3) was supposed to be the permutation that takes 1 to 2, 2 to 3 and 3 to 2, but with Wikipedia's convention, (1 2 3) is the identity map.

Which Wikipedia entry are you reading? The entry here is consistent with the notation as I've always seen it used:

http://en.wikipedia.org/wiki/Cycle_notation

 

[Fredrik]

Which Wikipedia entry are you reading? The entry here is consistent with the notation as I've always seen it used:

http://en.wikipedia.org/wiki/Cycle_notation

This is the one that was linked to earlier: http://en.wikipedia.org/wiki/Permutation#Definition_and_usage

It says that (1 4 2 3 5 6) is an abbreviation for \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6\\ 1 & 4 & 2 & 3 & 5 & 6\end{pmatrix} So $1\mapsto 2$, $2\mapsto 4$, etc. (The idea is that when there's a natural way to order the elements in the first line, we only write the second line).

 

[Justabeginner]

So it is equivalent to (2 6 4 5 3), not (4 5 6).

(5 6 4 2 1 3) (1 2 3) (3 1 2 4 5 6) = (4 5 6)

This map does not seem to be correct, it maps:
3 -> 1 -> 2 -> 1
4 -> 5 -> 6

Is that right?