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

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