# Thread: How do I multiply permutations?

1. ## How do I multiply permutations?

I have
a=(1,3,5)(1,2)
b=(1,5,7,9)

and I have to calculate a^-1 * b * a

How do I do it?

2. Originally Posted by GIPC
I have
a=(1,3,5)(1,2)
b=(1,5,7,9)

and I have to calculate a^-1 * b * a

How do I do it?
Actually I learned it from practice and a few observations. Computing the inverse of a is the only hurdle I see here:

First of all,

a = (1,3,5)(1,2) = (1,2,3,5)

Fact *: $(a,b,c,d)^{-1} = (a,d,c,b)$ (Prove it!)

Using fact *, $a^{-1}ba = (1,5,3,2)(1,5,7,9)(1,2,3,5) = (1,7,9,5)$

3. Originally Posted by Isomorphism
Actually I learned it from practice and a few observations. Computing the inverse of a is the only hurdle I see here:

First of all,

a = (1,3,5)(1,2) = (1,2,3,5)

Fact *: $(a,b,c,d)^{-1} = (a,d,c,b)$ (Prove it!)
Is that really a fact? Because I have a solved example from my text-book which contradicts this:

The inverse of $\tau = (5, 4, 6, 2)(1, 3, 9, 10, 7)(8, 11)$

is $\tau^{-1}= (2, 6, 4, 5)(7,10,9,3,1)(11, 8)$.

We have to write the whole thing backward! I mean, if I used your method I would get

$\tau^{-1}= (5, 2,6,4)(1, 7,10,9,3)(8, 11)$, which is wrong.

4. Are you sure they aren't the the same

5. From a Google Search:

"Inverses: Every permutation has an inverse that undoes'' the operation. In other words, if you apply a permutation to a set and then apply its inverse, the result is that the final order is unchanged from the original. If is a permutation and is its inverse, we can write .
If you have a permutation written in cycle notation and you want to find its inverse, simply reverse all the cycles. For example, . To see why this works, multiply: . The result will be . "

Numbers didn't come through with copy/paste.

The link is: http://mathcircle.berkeley.edu/BMC3/perm/node4.html

But I couldn't find the definition of multiplication of permutations anywhere. What is it please, I'm curious.
Edit: Actually, the same link does explain multiplication of permutations but I couldn't understand it

6. Originally Posted by Isomorphism
Are you sure they aren't the the same
Oh I see. But I still don't understand why you gave that method in your first post. Isn't it easier to just write all the numbers in each cycle backward?

7. ## algorithm for multiplication?

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

is a permutation of 1 2 3 4 5 6 7. By definition of multiplication:

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

p1xp2=p3. So far so good. 1to2 from p1 then 2to4 from p2 gives 1to4 for p3 etc

In cyclic notation:
[(1,2,4,3,6)(5,7)][(1,5,3)(2,4,7,6)]=(4721653)

p1 says 1 goes to 2, 2 goes to 4, 4 goes to 3, 3 goes to 6, and 6 goes back to 1. and so on.

BUT HOW DO YOU DO THE MULTIPLICATION IN CYCLIC NOTATION?

How do you get (1,3,5)(1,2)=(1,2,3,5)?

If I convert it to the p1xp2=p3 notation above I get:

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

for the first permutation p1, (1,3,5) says 1 goes to 3, 3 goes to 5, 5 goes to 1, 2 goes to 2, and 4 goes to 4, and so on. The answer is not (1,2,3,5), or a cyclic permutation of it: 3152, 1523, 5231, 2315

8. ## An Algorithm for cyclic multiplication

OK. I can see a way to do the cyclic multiplication:
p1xp2 = (1,3,5)(1,2) says, by first applying p1 then p2:

1 to 3 then 3 to 3 = 1 to 3
2 to 2 then 2 to 1 = 2 to 1
3 to 5 then 5 to 5 = 3 to 5
4 to 4 then 4 to 4 = 4 to 4
5 to 1 then 1 to 2 = 5 to 2

Which gives (1,3,5)(1,2) = (3,1,5,4,2) = (3,1,5,2) (4 goes to 4 so leave it out), which is same answer I got doing it the long way.

9. The following is instructive. Consider the permutation (2,4,5,1,3), which is short-hand for:
(1,2,3,4,5)
(2,4,5,1,3)
It says change 1 to 2, 2 to 4, 4 to 1, 1 to 4 etc cyclically, or, in short, (1,2,4) = (2,4,1) = (4,1,2) , which all say the same thing.
Also change 3 to 5, 5 to 3, 3 to 5, etc cyclically, or, in short, (3,5) = (5,3)
Then (1,2,4)(3,5) is the same prescription for creating the permutation as the original. In long hand it is:
(1,2,3,4,5)(1,2,3,4,5)=(1,2,3,4,5)
(2,4,3,1,5)(1,2,5,4,3) (2,4,5,1,3)
which says:
1 to 2 then 2 to 2 = 1 to 2
2 to 4 then 4 to 4 = 2 to 4
3 to 3 then 3 to 5 = 3 to 5
4 to 1 then 1 to 1 = 4 to 1
5 to 5 then 5 to 3 = 5 to 3
The same prescription in cyclical notation is:
(124)(35)=(2,4,5,1,3) which is word for word the same as above.

Real quick then (1,3,2,4)(4,3,2)=(2,3,4,1) ((1,3,2,4) then (4,3,2))
The thought process is, what happens to 1, then 2, then 3, etc.
1>3 then 3>2 = 2
2>4 then 4>3 = 3
3>2 then 2>4 = 4 (remember cyclical pattern)
4>1 then 1>1 = 1

(5,2) says change 5 to 2 and 2 to 5 and leave everything else unchanged, so in long hand it is:
(1,2,3,4,5,6,7...)
(1,5,3,4,2,6,7...)

The inverse of
(1,2,3,4)
(3,1,4,2)
is
(1,2,3,4)
(2,4,1,3)

The inverse of 1 to 3 is 3 to 1, etc. Also (2,4,1,3)=(4,1,3,2)=(1,3,2,4) =(3,2,4,1) =(2,4,1,3) because they all say the same thing. Take 3 to 2, 4 to 1, 1 to 3, 3 to 2, cyclically

Which answers original post, "How do I multiply permutations?," which in my opinion wasn't answered yet.

10. The preceding post is right as far as it goes. A problem arises when you try to do abc in cyclical notation. To do it in cyclical notation, lets say you do ab first per last post, which gives a result WHICH IS NOT IN CYCLICAL NOTATION, so you have to change it to cyclical notation before multiplying by c.

(1234)(1234) (1234)
(3412)(2431)=(3124)
p1xp2=p3 think of top and bottom parentheses as one parenthesis.
to do the same multiplication in cyclical notation, both terms on left have to be in cyclical form:
(1,3)(2,4)(1,2,4) = [3124] = (132)
[XXX] means the actual permutation of 1234
Now mutiply (p1xp2)xp4
(1234)(1234) (1234)
(3124)(1342)=(4132)=[4132]=(142)
in cyclical notation:
(132)(234)=[4132]=(142)
if a = (1234) then the inverse is (3124) = (1234)
(3124) (1234) (2314)
[3124]=(132) [3124]^-1 = [2314] = (123)
So let's try the post 1 problem
a=(1,3,5)(1,2)
b=(1,5,7,9)
and I have to calculate a^-1 * b * a
ba=(1579)(135)(12)=[215476983]=(12)(3579)
a=(135)(12)=[31542], a^-1=[25143]=(1253)
a^-1ba=(1253)(12)(3579)=[172456983]=(2793)

I'm sure there is a way to multiply cyclics to get another cyclic. Isomorphism seems to know but he won't give us the rationale, rule, or reference.

11. Isomorphism,

I have another example from my book: $(1,2,3).(2,4)(1,3,5)=(1,4,2,5)$

So, what happened to 3?? This is how I've done it:

$1 \to 2 \to 4$

$2 \to 3 \to 5$

$3 \to 1 \to 3$

$4 \to 2$

$5 \to 1$

I would end up with $(1,4,2,5)(3)$. But why did they omit the cycle (3)?

12. Originally Posted by demode
Isomorphism,

I have another example from my book: $(1,2,3).(2,4)(1,3,5)=(1,4,2,5)$

So, what happened to 3?? This is how I've done it:

$1 \to 2 \to 4$

$2 \to 3 \to 5$

$3 \to 1 \to 3$

$4 \to 2$

$5 \to 1$

I would end up with $(1,4,2,5)(3)$. But why did they omit the cycle (3)?
It's implied. Say I was working in S_{143567346245779566435341786267053257789}. Then writing $(123)$ including all the fixed points would take...a long time. And multiplying would be awful - you'd have to make sure someone hadn't tucked in a sneaky $(12345 12346)$ in the midst of it all! This is the power of cyclic notation over writing normal permutations.

13. Originally Posted by demode
Isomorphism,

I have another example from my book: $(1,2,3).(2,4)(1,3,5)=(1,4,2,5)$

So, what happened to 3?? This is how I've done it:

$1 \to 2 \to 4$

$2 \to 3 \to 5$

$3 \to 1 \to 3$

$4 \to 2$

$5 \to 1$

I would end up with $(1,4,2,5)(3)$. But why did they omit the cycle (3)?

Thanks for the example demode. In case somebody missed the crucial step, the above gives the permutation [45321] which results from applying the three cyclic permutations. It was put in cyclic form by noting 1->4->2->5->1 = (1425). It also says 3 doesn't change so leave it out, its extraneous. The cyclic form is just a recipe for getting the original permutation of 12345:
It says change 1 to 4, 2 to 5, 3 to 3, 4 to 2, 5 to 1 = [45321]

14. At this point we have pretty much nailed it. Just to summarize and tie up loose ends:

(3,27,85) means 1->1, 2->2, 3->27, 4->4, 5->5, ...., 26->26, 27->85, 28->28,....., 84->84, 85->3

Ex 1: (remove arrow head to ease typing)
(3,25,57)(6,83,25)= 1-1-1, 2-2-2, 3-25-6, 4-4-4,....,6-6-83,...,25-57-57,.....,
57-3-3,....., 83-83-25. or
3-6, 6-83, 25-57, 57-3, 83-25, which becomes in cyclic notation,
3-6-83-25-57-3 = (3,6,83,25,57,3)

Ex 2: check against example in link above, which only gives answer:
(1345)(243)(163)
(1345)(243)=1-3-2, 2-2-4, 3-4-3, 4-5-5 = 1-2-4-5-1 = (1245)
(1245)(163)= 1-2, 2-4, 3-1, 4-5, 5-6, 6-3 = 1-2-4-5-6-3-1 = (124563)

in one step:
(1345)(243)(163)=1-3-2, 2-4, 3-4-3-1, 4-5, 5-1-6, 6-3 = 1-2-4-5-6-3-1 = (124563)

Ex 3: illustrate with result with more than one cycle
(2143)(5246)=1-6, 2-1, 3-4, 4-3, 5-2, 6-5=(1-6-5-2-1)(3-4-3)=(1652)(34)

Cyclic Inverse:
b^-1 = [(145)(342)]^-1 = (243)(541)
bb^-1= (145)(342)(243)(541) = (145)(1)(541) = 1
b^-1b= (243)(541)(145)(342) = 1

b^-1 = [(145)(342)(2516)]^-1 = (6152)(243)(541)
bb^-1 = (145)(342)(2516)(6152)(243)(541) =(145)(342)(1)(243)(541)

(1) = 1-1, 2-2, 3-3, 4-4, 5-5,.......

HW Do problem in post 1

15. Originally Posted by demode
Oh I see. But I still don't understand why you gave that method in your first post. Isn't it easier to just write all the numbers in each cycle backward?
Yes it is. Both are same anyway.

Page 1 of 2 12 Last