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

  • Thread starter Justabeginner
  • Start date
  • Tags
    Permutation
In summary: I do not know how to start this problem. I am not looking for a specific answer, just a place to begin. I do not see how that hint helps me get to the answer, I am sorry if I am being a burden.In summary, the conversation is about proving the existence of a permutation sigma such that sigma * (1 2 3) * sigma inverse= (4 5 6). The conversation includes discussions on the notation for permutations, constructing permutations as products of disjoint cycles, and hints on how to approach the problem. The summary concludes with the participant stating that they are looking for a place to begin and not a specific answer.
  • #36
Justabeginner said:
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)
 
Physics news on Phys.org
  • #37
jbunniii said:
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.
 
  • #38
Justabeginner said:
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}##.
 
  • #39
jbunniii said:
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) =
 
  • #40
Justabeginner said:
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?
 
  • #41
jbunniii said:
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).
 
  • #42
Justabeginner said:
(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).
 
  • #43
jbunniii said:
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?
 
  • #44
Justabeginner said:
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.
 
Last edited:
  • #45
Fredrik said:
(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.
 
  • #46
Justabeginner said:
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.
 
  • #47
Justabeginner said:
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.
 
  • #48
Fredrik said:
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
 
  • #49
jbunniii said:
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).
 
  • #50
jbunniii said:
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?
 
  • #51
Fredrik said:
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.
 
  • #52
Justabeginner said:
(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}##.
 
  • #53
jbunniii said:
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).
 
  • #54
pasmith said:
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.
 
  • #55
jbunniii said:
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?
 
  • #56
Justabeginner said:
(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.
 
  • #57
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!
 
  • #58
Justabeginner said:
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.
 
  • #59
jbunniii said:
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
 
  • #60
Justabeginner said:
(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. :biggrin: 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.
 
  • #61
jbunniii said:
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. :biggrin: 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!
 

Similar threads

Back
Top