How to Multiply Permutations: A Quick Guide for Beginners

[DEMJ]

Homework Statement

Multiply the permutation (246)(12)(47)

The Attempt at a Solution

This has got to be so easy yet I cannot figure it out on my own. I understand that for (246) it means that 2 \mapsto 4, 4 \mapsto 6, 6 \mapsto 2. Could anyone lead me on what I should do next with (12)? Do I do something with 1 \mapsto 2 and multiplication?

 

[tiny-tim]

Hi DEMJ!

(just type -> for "goes to" )

Just start at the right, and try each number separately.

For example, where does 7 go? Where does 4 go? etc …

 

[DEMJ]

If I start at the right 7 -> 4 then 4 goes back to 7. Then 2 -> 1 then 1 goes back to 2.

or should I think of it as 7 -> 4 then 4 -> 2 then 2 -> 1 then 1 -> 6 and so on. Which is

the correct way to think for permutation multiplication?

 

[tiny-tim]

You have to do each bracket in turn:

Where does (47) send 7 to? Then where does (12) send that to? Then where does (246) send that to?

 

[DEMJ]

I am doing awful with this, but I understand (47) sends 7 to 4, but I do not understand where (12) sends 7 -> 4 to? If it sends it (246) does it change (246) to (276) ?

 

[tiny-tim]

If it sends it (246) does it change (246) to (276) ?

A cycle (a bracket) only moves the elements around, it doesn't move other cycles around.

I am doing awful with this, but I understand (47) sends 7 to 4, but I do not understand where (12) sends 7 -> 4 to?

(12) only affects 1 and 2 … it leaves 4 where it is.

Now can you see what (246) does?

 

[tiny-tim]

hmm … a friend of mine has just suggested I should ask whether your book multiplies different brackets from right to left or from left to right …

I've been assuming right to left (that's the usual algebraic way, I didn't know there was any other), so that (47) is used first …

does your book do it that way, or does it use left to right, so that (246) is used first?

 

[jambaugh]

You can use the following rules (cycles act from the left on sequences and the notation for their action is defined so that these rules hold)

* A cycle: (a,b,c...,y,z) can be written as a product of 2-cycles via:
(a,b,c,...,y,z) = (ab)(bc)(c .) ... (. y)(yz)

* The terms in a cycle can be cycled and it's the same cycle:
(a,b,c,...y,z) = (b,c,...y,z,a) = (c,...y,z,a,b) = ... = (z,a,b,c,...,y)

( in particular (ab)=(ba) )

* Disjoint cycles commute:
(abcd)(pqr) = (pqr)(abcd) where none of p,q,r equal any of a,b,c,d.

Add to this that 2-cycles square to the identity (ab)(ab)=1 and you can always simplify permutation products.

There is a short cut you can derive from the above base rules. You can always split off a transpose (2-cycle) from either end of a general cycle (or recombine going the other way)
(a,b,c,...x,y)(y,z) = (abc...xyz) = (ab)(bc...xyz).
When combining a 2-cycle with a general cycle you must make sure here that the 2-cycle and general cycle have only one term in common and cycle both so it is positioned on the adjacent ends of each.

This is correct: (ab)(bcd) = (abcd)
but do not use: (ab)(bcad) != (abcad) as cycles with repeated terms are forbidden!
In such a case you want to factor and recombine cycle and combine again:
(ab)(bcad) = (ab)(bc)(cad) = (abc)(cad) = (bca)(cad) = (bc)(ca)(ca)(ad)=(bc)(ad).

More generally:
** you can split a cycle into a product of two cycles with one common term or append two cycles with one common term:
(abcd)(defgh...) = (abcdefgh...) With some practice you can get quite efficient at this permutation arithmetic. You can always continue until any common terms have been combined and you have a product of disjoint cycles.

Note the action of a cycle notated to obey these rules is for example:
(123)[abcd]
=(12)(23)[abcd]
=(12)[acbd] {(23) swapped 2nd and 3rd elements.}
=[cabd] {then (12) swapped first and 2nd elements.}
The net result is that the cycle (123) maps positions: 1-->2-->3-->1
Similarly for general cycles (abcd...z) maps a-->b-->c-->...-->z-->a.
(This is the notation you indicted.)

If the notion being used is the reverse of this then use a dot or star to distinguish the two notations
(123)* = (321)
and then just reverse to this notation solve and reverse back.

Example. Simplify:
P=(24)(1245)(35)(24)
=(24)(1245)(24)(35) {commuting disjoint cycles}
=(42)(2451)(24)(35) {cycle to get 2's adjacent ***}
=(42)(24)(451)(24)(35) {split off 24 transpose from 4-cycle since 2 terms in common.}
=(451)(24)(35) {square 2-cycle to identity}
=(514)(42)(35) {cycle to get 4's adjacent}
=(5142)(35) {combine cycles since only one common term}
=(1425)(53) {cycle to get 5's adjacent}
=(14253) {combine since only one common term.}
Done!
P = (14253)

*** you could have cycled to get 4's adjacent but since two terms are in common and adjacent you want to pull off both together. If two are in common but not adjacent that's fine. It will work out either way pulling out one at a time.

Some exercises:
Work out that (ax)(abcd)(ax) = (xbcd)
Work out that (ax)(abxyz)(xa) = (xbayz) (adjoint action of a transpose)
Work out that (abcd...z)(z...dcba) = 1 (reversed cycles are inverses)
Work out: (abc)(xaybzc)(cba)=? (adjoint action of a 3-cycle)
Work out: (123)(123) = (321)

Have fun.

 

[jambaugh]

Here's an interesting aside.

The algebra of permutations can be extended by appending signs and allowing (ab)= -(ba) and (ab)(ab) = -1. This central extension is how one defines projective representations of the permutation group. This relates to projective and gauge statistics for theoretical particles.