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

[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?

 

[jbunniii]

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

Interesting. I don't think I've seen anyone use that notation before, but as the Wiki entry says, it's common in combinatorics and computer science.

In abstract algebra, every textbook I know of uses either the 2-line notation or cycle notation.

In the context of this problem, I have to assume that we are using cycle notation: the problem statement asks for a permutation $\sigma$ such that $\sigma$(1 2 3)$\sigma^{-1}$ = (4 5 6). If (1 2 3) was the identity, then $\sigma$(1 2 3)$\sigma^{-1}$ would also be the identity for any $\sigma$, so the question would make no sense. Also, I don't think (4 5 6) would be a valid permutation in the notation at your link.

 

[jbunniii]

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

Right, so (5 6 4 2 1 3) (1 2 3) (3 1 2 4 5 6) $\neq$ (4 5 6).

Also note that (3 1 2 4 5 6) is not the inverse of (5 6 4 2 1 3), so you don't have an expression of the form $\sigma$(1 2 3)$\sigma^{-1}$.

 

[pasmith]

In abstract algebra, every textbook I know of uses either the 2-line notation or cycle notation.

In the context of this problem, I have to assume that we are using cycle notation: the problem statement asks for a permutation $\sigma$ such that $\sigma$(1 2 3)$\sigma^{-1}$ = (4 5 6). If (1 2 3) was the identity, then $\sigma$(1 2 3)$\sigma^{-1}$ would also be the identity for any $\sigma$, so the question would make no sense. Also, I don't think (4 5 6) would be a valid permutation in the notation at your link.

Actually, if we aren't using cycle notation and we're working with a set of six elements then both (1 2 3) and (4 5 6) are meaningless, because they each fail to specify the images of three members of the domain. The identity element would be (1 2 3 4 5 6).

 

[jbunniii]

Actually, if we aren't using cycle notation and we're working with a set of six elements then both (1 2 3) and (4 5 6) are meaningless, because they each fail to specify the images of three members of the domain. The identity element would be (1 2 3 4 5 6).

Yes, good point. The problem doesn't state explicitly what set we are working with, but we can assume it must have at least six elements. Once nice thing about the cycle notation is that (1 2 3) and (4 5 6) maintain the same meaning whether or not the set contains other elements besides 1,2,3,4,5,6. Indeed, the set can even be infinite, which would pose a problem for the 2-line and 1-line notations.

 

[Justabeginner]

Right, so (5 6 4 2 1 3) (1 2 3) (3 1 2 4 5 6) $\neq$ (4 5 6).

Also note that (3 1 2 4 5 6) is not the inverse of (5 6 4 2 1 3), so you don't have an expression of the form $\sigma$(1 2 3)$\sigma^{-1}$.

(a b c d 2 1) (1 2 3) (1 2 d c b a) = (4 5 6)

Is this of correct form?

 

[jbunniii]

(a b c d 2 1) (1 2 3) (1 2 d c b a) = (4 5 6)

Is this of correct form?

Yes, there is at least one solution of this form.

By the way, notice that the goal is to map 1 to 4, 2 to 5, and 3 to 6. We can map 4,5,6 anywhere we like as long as the result is a permutation (bijection). This means that there are in fact 6 valid solutions to this problem.

 

[Justabeginner]

I've been trying to form cycles, but I'm not getting anywhere. This is the last one I just did:

(3 4 6 5 2 1) (1 2 3) (1 2 6 5 3 4)
I was trying to map 1 -> 2 -> 3 -> 4
Then to map 2 -> 6 - > 5.
Then 3 -> 4 -> 6.
But they are not inverses of each other...
I don't know if there is a quick method to get to the right cycle but I know my method is much too time-consuming!

 

[jbunniii]

I've been trying to form cycles, but I'm not getting anywhere. This is the last one I just did:

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

You need to be careful when forming the inverse cycle. (1 2 6 5 3 4) is not the inverse of (3 4 6 5 2 1).

I can give you another hint. Going back to what we were doing earlier (see post #32) with transpositions, recall that

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

Do you see how you can combine these three facts to get something of the form $\sigma$(1 2 3)$\sigma^{-1}$ = (4 5 6)? Hint: $\sigma$ will consist of multiple transpositions instead of a single longer cycle.

 

[Justabeginner]

You need to be careful when forming the inverse cycle. (1 2 6 5 3 4) is not the inverse of (3 4 6 5 2 1).

I can give you another hint. Going back to what we were doing earlier (see post #32) with transpositions, recall that

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

Do you see how you can combine these three facts to get something of the form $\sigma$(1 2 3)$\sigma^{-1}$ = (4 5 6)? Hint: $\sigma$ will consist of multiple transpositions instead of a single longer cycle.

(1 4) (2 5) (3 6) (1 2 3) (6 3) (5 2) (4 1) = (4 5 6)
So 1 -> 4
2 -> 5
3 -> 6

 

[jbunniii]

(1 4) (2 5) (3 6) (1 2 3) (6 3) (5 2) (4 1) = (4 5 6)
So 1 -> 4
2 -> 5
3 -> 6

Yes, that's correct. Note that this solution changes the cycle (1 2 3) to (4 5 6), and it changes the singleton cycles (4), (5), (6) to (1), (2), (3) respectively. In other words, writing out the full cycle notation including singletons:
$\sigma$(1 2 3)(4)(5)(6)$\sigma^{-1}$ = (4 5 6)(1)(2)(3)

There are five other solutions in which (4), (5), and (6) are mapped to different arrangements of (1), (2), and (3), for example:
$\sigma$(1 2 3)(4)(5)(6)$\sigma^{-1}$ = (4 5 6)(1)(3)(2)

The right hand side (4 5 6)(1)(3)(2) is the same permutation as (4 5 6)(1)(2)(3), since disjoint cycles commute, but we obtain it using a different $\sigma$.

If you're bored, you can try to find the other solutions. For example, to transform
(1 2 3)(4)(5)(6) to
(4 5 6)(1)(3)(2),

$\sigma$ needs to map as follows:
$1 \mapsto 4$
$4 \mapsto 1$
$2 \mapsto 5$
$5 \mapsto 3$
$3 \mapsto 6$
$6 \mapsto 2$
and therefore $\sigma$ = (1 4)(2 5 3 6) is another solution to the problem.

 

[Justabeginner]

Yes, that's correct. Note that this solution changes the cycle (1 2 3) to (4 5 6), and it changes the singleton cycles (4), (5), (6) to (1), (2), (3) respectively. In other words, writing out the full cycle notation including singletons:
$\sigma$(1 2 3)(4)(5)(6)$\sigma^{-1}$ = (4 5 6)(1)(2)(3)

There are five other solutions in which (4), (5), and (6) are mapped to different arrangements of (1), (2), and (3), for example:
$\sigma$(1 2 3)(4)(5)(6)$\sigma^{-1}$ = (4 5 6)(1)(3)(2)

The right hand side (4 5 6)(1)(3)(2) is the same permutation as (4 5 6)(1)(2)(3), since disjoint cycles commute, but we obtain it using a different $\sigma$.

If you're bored, you can try to find the other solutions. For example, to transform
(1 2 3)(4)(5)(6) to
(4 5 6)(1)(3)(2),

$\sigma$ needs to map as follows:
$1 \mapsto 4$
$4 \mapsto 1$
$2 \mapsto 5$
$5 \mapsto 3$
$3 \mapsto 6$
$6 \mapsto 2$
and therefore $\sigma$ = (1 4)(2 5 3 6) is another solution to the problem.

I did not know about singletons; thank you for that information!