Understanding Permutations: Transpositions, Compositions, and Order Explained

[cmurphy]

I am trying to read through and understand about permutations, and I have a couple of questions.

First, How do you write a permutation as a transposition?

The example that I have is (3, 10, 1, 4, 5, 7, 2, 8, 6, 9), and I said that it is equal to (3, 10)(10, 1)(1, 4)(4, 5)(5, 7)(7, 2)(2, 8)(8, 6)(6, 9). I think I followed how the book showed to do this, so I think my answer is corect (right?), but I have no idea WHY this works.

Am I correct in assuming that I use the (3, 10, 1, 4, 5, 7, 2, 8, 6, 9), since the original question writes this as (1 2 3 4 5 6 7 8 9 10
(3, 10, 1, 4, 5, 7, 2, 8, 6, 9).

Also, if you could answer Why this works, it would be very helpful.

Also, how exactly do I compute this long composition problem? I don't understand how it works. I understand that I work from right to left, but if I know that 6 goes to 9 and 9 goes to 6, how do I go backwards to where I started? (Hopefully that question makes sense).

Also, why is the order of two cycles equal to the least common multiple of elements in each cycle?

Am I correct in assuming that in the following cycle:
(1, 3, 10)(2, 4, 5, 7)(6, 8)(9), the order is lcm[3, 4, 2, 1] = 12?

Again, explaining why would be extremely helpful.

Thanks.
Colleen

 

[matt grime]

I am trying to read through and understand about permutations, and I have a couple of questions.

First, How do you write a permutation as a transposition?

you don't. a permutation may be written as a product of transpositions, not a transposition.

The example that I have is (3, 10, 1, 4, 5, 7, 2, 8, 6, 9), and I said that it is equal to (3, 10)(10, 1)(1, 4)(4, 5)(5, 7)(7, 2)(2, 8)(8, 6)(6, 9). I think I followed how the book showed to do this, so I think my answer is corect (right?), but I have no idea WHY this works.

it works because it's the right answer. the left hand side and righthand side are the same permutation. the way you figure it out is to notice early one that

(12)(23)=(123)

then you wonder in general, is

(12)(23)(34)=(1234)?

well, it certainly is (123)(34) and that's equal to (1234), so that's well and good, then you prove it in generaly. induction looks like a good idea here so try it.

Am I correct in assuming that I use the (3, 10, 1, 4, 5, 7, 2, 8, 6, 9), since the original question writes this as (1 2 3 4 5 6 7 8 9 10
(3, 10, 1, 4, 5, 7, 2, 8, 6, 9).

Also, if you could answer Why this works, it would be very helpful.

hopefully you see why it works (it's a proof, not an algorithm), but the first part i don't understand. perhaps becaue you think the justification from the imput box is preserved in the output? it isn't.

Also, how exactly do I compute this long composition problem? I don't understand how it works. I understand that I work from right to left, but if I know that 6 goes to 9 and 9 goes to 6, how do I go backwards to where I started? (Hopefully that question makes sense).

sadly it doesn't. what long composition problem? do you mean 'how do i simplify large permutations into easier to read ones?

eg simplify (123)(235)(57) into a product of disjoint cycles?

i#ll assume so, it's a usual question.

pick any element in the swap, say 7 and write down
(7
read wheree 7 goes to (from right to left)
7 goes to 5 in the first cycle, then that 5 is sent to 2 in the second cycle, then that 2 is sent to 3 in the first cycle so we have

(73

now put 3 in. the first cylce leaves it alone, the second sends 3 to 5, the last one leaves 5 alone so we write

(735

now put 5 in. 5 is sent to 7 by the first cycle, then 7 is left alone by all the others. 7 is what we started with so we can close off that bracket and write:

(735)

now pick some element that we've not written down and start a new bracket, say, 1:

(735)(1

1 is left alone by the first cycle,a nd the second, and sent to 2 in the last one so we write:

(735)(12

put 2 back in and see where it goes, etc when it returns to 1 close off the bracket and start a new one with any remaining unused elements.

Also, why is the order of two cycles equal to the least common multiple of elements in each cycle?

it isn't. that is only true if the cycles are disjoint, that is have no common elements in either cycle.

Am I correct in assuming that in the following cycle:
(1, 3, 10)(2, 4, 5, 7)(6, 8)(9), the order is lcm[3, 4, 2, 1] = 12?

Again, explaining why would be extremely helpful.

because the cycles are disjoint they commute. in *any* group if you have two elements x and y and xy=yx, then ord(xy)=lcm(ord(x),ord(y))
that is just a property of commutative groups, nothing to do with permutations.

remember cycles must be disjoint for this to work, eg

(12)(23) does not have order lcm(2,2), its order is 3.

 

[M98Ranger]

Hi Colleen,

I am happy to help you understand permutations and their different forms.

First, let's define what a transposition is. A transposition is a permutation that swaps two elements in a sequence while keeping all other elements in their original position. For example, in the sequence (1, 2, 3, 4), a transposition can be (1, 3, 2, 4) where 2 and 3 are swapped.

Now, to write a permutation as a transposition, you can break it down into a series of transpositions. In your example, you correctly wrote the permutation (3, 10, 1, 4, 5, 7, 2, 8, 6, 9) as a series of transpositions. The reason this works is because each transposition in the series only swaps two elements, while keeping all others in their original position.

To compute a long composition problem, you can use the fact that a permutation can be written as a composition of cycles. For example, if we have the permutation (1, 2, 3, 4, 5, 6), we can write it as (1, 2)(2, 3)(3, 4)(4, 5)(5, 6). To go backwards to where you started, you can simply reverse the order of the cycles. So, in the example you provided, if 6 goes to 9 and 9 goes to 6, we can write it as (6, 9) which is a transposition.

The order of a permutation is the number of times you have to apply the permutation to get back to the original sequence. In the cycle (1, 3, 10)(2, 4, 5, 7)(6, 8)(9), the order is indeed lcm[3, 4, 2, 1] = 12. This is because you have to apply the permutation 12 times to get back to the original sequence (1, 2, 3, 4, 5, 6, 7, 8, 9, 10).

I hope this helps you understand the concepts of permutations, transpositions, compositions, and order. If you have any further questions, please don't hesitate to ask. Understanding permutations is important in various fields of