permutation theory

Permutation Groups TomDavis tomrda [email protected] http://www .geometer .org/mathcircles April 2,2003 Abstract This paper describes permutations (rearrangements ofobjects): howtocombine them, andhowtoconstruct comple xpermutations from simpler ones. We’lltalkabitabout groups ofpermutations aswell. Some interesting examples here arerelated tosolving the“Rubik’ sCube” puzzle. Itmay help haveaRubik’ sCube with youasyou read along (and ascrewdrivertotakeitapart ifyoudon’tknowhowtosolveit). 1Permutations Apermutation isarearrangement ofobjects. Here wewillonly consider permutations ofafinite number ofobjects, and since theobject names don’treally matter ,wewilloften simply consider permutations ofthenumbers 1;2;3;:::;n. When weworkwith Rubik’ sCube, however,there arebetter names forthefaces than integers—see Section 3. Ofcourse we’lllearn about permutations firstbylooking atpermutations ofsmall numbers ofitems, butifyouthink ofthe54colored faces ofthelittle cubelets (“cubies”) onRubik’ sCube, youcanseethateverytime youtwist aside ofthecube, youarerearranging those little faces. There areplenty ofother examples ofpermutations, manyofwhich areextremely important andpractical. Forexam- ple,when youhavealistofitems tosort, either byhand orwith acomputer program, youareessentially faced with theproblem offinding apermutation oftheobjects thatwillputthem inorder after thepermutation. Ifweconsider permutations ofnobjects, there aren!ofthem. Toseethis, firstconsider where object number 1winds up.There arenpossibilities forthat. After thefateofobject 1isdetermined, there areonlyn1possible fatesfor object number 2.Thus there aren(n1)(n2)


3
2
1=n!permutations ofasetofnobjects. Forexample, ifweconsider allpossible rearrangements ofthesetf1;2;3g,there are3!=3
2
1=6ofthem, listed inTable 1. 11!12!23!3 21!22!13!3 31!32!23!1 41!12!33!2 51!22!33!1 61!32!13!2 Table 1:Permutations of3objects Agood waytothink ofpermutations isthis(using permutations ofthree objects asanexample): Imagine thatthere arethree boxeslabeled “1”, “2”, and“3”, andinitially ,each contains aballlabeled with thesame number —box 1 contains ball1,andsoon.Apermutation isarearrangement oftheballs butinsuch awaythatwhen you’redone there isstillonly asingle ballineach box. Inthetable above,thenotation a!bindicates thatwhate verwasinboxamovestotheboxlabeled b,sotoapply permutation number 3abovemeans totakewhate verballisinbox1andmoveittobox3,toleavethecontents ofbox 2alone, andtotaketheballfrom box3andputitintobox1.Inother words, permutation number 3abovetells usto swapthecontents ofboxes1and3. 1 Thenotation aboveispretty clumsy .Here areacouple ofother possibilities: 1.1TwoRowNotation Write thepermutation likethis:1234 4213 where theexample aboveindicates thatthecontents ofbox1movestobox4,box2isunchanged, theballinbox3 movestobox1,andtheballinbox4movestobox3. Theadvantage tothisnotation isthatitisveryeasy tofigure outwhere everything goes. Thedisadv antage isthatit requires writing downeach number twice. Since thetoprowcanalwaysbeputinorder ,however,there isnorealneed towrite it,sosimply listing thesecond rowissufficient (assuming there isanobvious waytoputtheboxesinorder). Butthere isanother waythatisoften farmore useful. 1.2CycleNotation Write theexample abovelikethis: (143) This indicates thatthecontents ofbox1movestobox4,thecontents ofbox4tobox3,andthecontents ofbox3 movesback intobox1.Thesystem iscalled “cycle notation” since thecontents oftheboxesinparentheses moveina cycle: 1to4,4to3,and3back to1. Some permutations havemore than onecycle. Forexample, thecycle notation forthepermutation corresponding to: 1234 3412 is (13)(24) : There aretwo“cycles”. 1movesto3and3movesback to1.Atthesame time, 2movesto4,and4back to2.Inother words, thecontents ofboxes1and3arecycled, andatthesame time, thecontents ofboxes2and4arecycled. Incycle notation, there cannot beanyduplicate elements inthevarious cycles that makeupthepermutation, so something like(13)(12) isnotavalidform. Aswewill seeinthenextsection, something like(13)(12) canbe reduced toavalidform—in thisparticular case to(132) . Asafinal example, consider thispermutation off1;2;3;4;5;6;7;8g: (135)(2768) : Itmovestheballinbox1tobox3,3to5,and5back to1.Atthesame time, itmoves2to7,7to6,6to8,and8back to1.Notice that4isnotinvolved,soitstays fixed.Ifyouwanttomakeitclear that4isamember ofthesetofitems under consideration, butthatinthisparticular permutation itisnotmoved,youcanwrite: (135)(2768)(4) : Infact,thespecial permutation thatdoes notmoveanything isoften written as:(1). Note alsothattheordering doesn’ tmatter aslong aseach item tobepermuted appears only once, andthatyoucanlist acycle beginning with anymember ofit.Allofthefollo wing indicate exactly thesame permutation: (135)(2768) (2768)(135) (7682)(135) (351)(6827) (8276)(513) (6827)(513) 2 Since there aresomanypossible waystolabel aparticular permutation, ifthere isnoconvention about thelabeling, it may bedifficult totelliftwopermutations arethesame ordifferent astheexample aboveillustrates. Ifitiseasy toassign anorder totheelements being permuted asintheexample above,then itisbest tochoose the representation ofapermutation asfollo ws,where weassume theyelements are1;2;3;:::;n: 1.Beginwith thesmallest element. Ifitismoved,listthepermutation beginning with thatsmallest element asthe firstentry inthecycle. 2.After listing thecomplete cycle, check toseeifthere areother elements movedbythepermutation thatdonot appear inthecycle. Ifso,choose thesmallest remaining, andrepeat theprocess until allmovedelements are listed. Intheexample above,this“canonical” representation would bethefirstonelisted: (135)(2768) . Intherestofthisdocument, we’llusethecycle notation andunless there isagood reason todootherwise, wewilllist permutations using their canonical representations. 2Combining Permutations Ofcourse it’snice tohaveamethod towrite downapermutation, butthings begintogetinteresting when wecom- bine them. Ifyoutwist onefaceofRubik’ sCube andthen twist another one, each twist jumbles thefaces, andthe combination oftwotwists usually causes ajumbling thatismore complicated than either ofthetwoindividual twists. Rather than beginwith Rubik’ sCube, let’sbeginbylooking atpermutations ofjust3objects. Welisted them in Table 1,butthere weused averyclumsy notation. Here arethesixpossible permutations ofthree items listed inthe same order asinTable 1: (1);(12);(13);(23);(123);(132): What happens ifwebeginwith ball1inbox1,ball2inbox2,andball3inbox3,andthen weapply(12) follo wed by(13)? Agood waytothink about thisistofollo wthecontents oftheboxesoneatatime. Forexample, ball1begins inbox 1,butafter(12) ithasmovedtobox2.Thesecond permutation, (13),does notmovethecontents ofbox2,soafter both permutations havebeen applied, ball1willhavemovedtobox2.Sothefinal result willlook likethis: (12


where we’renotsure what comes next.Wedon’tknowif2willgoback tooneandthecycle willclose, orwhether it willcontinue toanother box. Sosince thefateof2isinquestion, let’sseewhere itgoes. The first permutation, (12) movesbox2tobox1,andthen(13) will movebox1tobox3,sonowweknowthe combination ofpermutations looks likethis: (123


Since there areonly three objects, weknowthat3willgoback to1andclose thecycle, but(especially when you’re beginning), it’sgood totrace each ball, including ball3inthiscase. The first permutation, (12),does notmovethecontents ofbox3,butthesecond, (13) movesittobox1,sothe combination of(12) follo wed by(13) isequivalent tothesingle permutation (123) . Combining permutations asaboveiswritten justlikeamultiplication inalgebra, andwecanwrite ourresult as follo ws1: (12)(13) =(123): 1Inotherplaces,sometimes thisªmultiplicationº ofpermutations iswrittenintheoppositeorder: (13)(12) =(123).Therearegoodreasons tochooseeitherordering, butherewe'llwritethemintheordertheyoccurfromlefttoright,so(12)(13) meansthat®rst(12)isapplied,followed by(13). 3 Beware,however.This isnotthesame asmultiplication thatyou’reused toforrealnumbers. Bydoing thesame analysis asabove,convince yourself that: (13)(12) =(132) 6=(123) =(12)(13) : Inother words, theorder ofmultiplication makesadifference. IfP1andP2aretwodifferent permutations, itmay not betruethatP1P2=P2P1.Multiplication ofpermutations isnotcommutati ve. Testyour understanding ofmultiplication ofpermutations byverifying alloftheentries inthe“multiplication table” forthepermutations ofthree objects inTable 2. (1) (12) (13) (23) (123) (132) (1) (1) (12) (13) (23) (123) (132) (12) (12) (1) (132) (123) (23) (13) (13) (13) (123) (1) (132) (12) (23) (23) (23) (132) (123) (1) (13) (12) (123) (123) (13) (23) (12) (132) (1) (132) (132) (23) (12) (13) (1) (123) Table 2:Multiplication table ofpermutations Remember thattheorder ofmultiplication isimportant. InTable 2,ifyouaretrying tolook uptheproduct of(12)(13) , findthecolumn labeled (12) andtherowlabeled (13).Ifyouusetherowlabeled (12) andthecolumn labeled (13) youwillbelooking uptheproduct (13)(12) which may bedifferent. Asafinal check onyour understanding ofmultiplication ofpermutations, verify thefollo wing multiplications of permutations: (1342)(3645)(1623) =(126435) (12)(23)(34)(45) =(15432) (135)(32)(54321)(413)(13) =(1) Here aresome general properties ofmultiplication ofpermutations. Theyhold forthesetsofpermutations ofanynum- berofelements, butyoushould check toseethattheydohold intheparticular case ofthethree-element permutations inTable 2. Closure:IfPandQaretwopermutations, then theproducts PQandQPboth makesense inthattheresult is alsoapermutation. This isobviously truesince arearrangement ofarearrangement isitself arearrangement. Identity: Thepermutation (1)thatleaveseverything fixedisanidentity under multiplication. IfPisanyper- mutation, thenP(1)=(1)P=P.Inother words, thepermutation (1)beha vesforpermutation multiplication justlikethenumber 1beha vesformultiplication ofrealnumbers. Sometimes theidentity iswritten ase.Itis nothard toprovethattheidentity isunique. Inverses: Everypermutation hasaninversethat“undoes” theoperation. Inother words, ifyouapply apermu- tation toasetandthen apply itsinverse, theresult isthatthefinal order isunchanged from theoriginal. IfPis apermutation andP1isitsinverse, wecanwritePP1=P1P=(1)=e. Ifyouhaveapermutation written incycle notation andyouwanttofinditsinverse, simply reverseallthecycles. Forexample, [(134)(256)]1=(652)(431) .Toseewhy thisworks, multiply: (134)(256)(652)(431) .The result willbe(1)2. 2Noticethatwehavereversednotonlythecontentsofeachcycle,butalsotheorderofthecycles.Forcyclesinthecanonical form,reversing theorderofcyclesisnotimportant, butifthepermutation isnotincanonical form,reversingbothorderswillproducetheinverse,nomatterwhat. 4 Associativity: IfP,Q,andRareanythree permutations, thenP[QR]=[PQ]R.Inother words, ifyouhave tomultiply 3ormore permutations together ,itdoesn’ tmatter howyougroup them todothemultiplications. Weusebraces “[“and“]”toindicate thegrouping since we’veused parentheses toindicate thecycles ofthe permutations. Forexample, let’sworkout(1345)(243)(163) twodifferent ways. First we’llmultiply (1345) by(243) and then takethatresult andmultiply itby(163) .Then we’lldothemultiplication beginning with thelasttwo permutations (check these yourself): [(1345)(243)](163) =(1245)(163) =(124563) (1345)[(243)(163)] =(1345)(16324) =(124563) Not(necessarily) Commutati vity: This isreally justareminder thatthecommutati velawdoes nothold in general. Ifyouswaptheorder ofaproduct, theresult may change, soPQandQParenotnecessarily thesame. There aresome cases, however,where things docommute. Forexample, ifyour permutations aretwocycles that share noelements incommon, theorder inwhich theyoccur does notmatter .So(123)(45) =(45)(123) .This isobviously truesince each cycle rearranges adifferent subset ofelements, sotheir operations arecompletely independent andcanbereversed inorder with noeffectonthefinal outcome. 2.1PowersofCycles Because theassociati velawholds, itmakessense towrite something likePnwhere Pisapermutation andnisa positi veinteger.P4=PPPP,andbecause theoperation ofpermutation multiplication isassociati ve,yougetthe same answer nomatter howyouchoose tomultiply them together . Forexample, let’scompute P3,where P=(134)(25) . P3=PPP=(134)(25)(134)(25)(134)(25) =(25): Infact,it’seasy toseehowpowers workoncycles. Let’slook atP=(123456) ,forexample. Here arethevarious powers ofP: P1=(123456) P2=(135)(246) P3=(14)(25)(36) P4=(153)(264) P5=(165432) P6=(1) When raising acycle toapowerk,each elements “steps forw ard” byksteps, cycling back tothebeginning, if necessary .It’sjustlikemodular (clock) arithmetic. Clearly ifthecyclePisnitems long, thenPn=(1)=e. It’sagreat exercise tocalculate Pkforallpowers ofk,where Pisacycle whose length isaprime number .Tryitwith P=(1234567) andcalculate P1,P2,P3,P4,P5,P6,andP7. Ifapermutation iswritten inproper cycle form where there ispossibly more than onecycle, butthere arenoitems thatappear inmore than onecycle, then taking powers ofsuch apermutation iseasy—just raise theindividual cycles tothepowerandcombine theresults. This isbecause individual cycles thatdonotshare items docommute, so,for example, [(123)(45)]3=(123)(45)(123)(45)(123)(45) ; butthe(123) andthe(45) cycles commute, sotheright hand sidecanberearranged tobe: [(123)(45)]3=(123)(123)(123)(45)(45)(45) =(123)3(45)3: Clearly ,ifPisacycle oflength n,thenPn=ebecause each application ofthecycle movesalltheelements inthe cycle onestep forw ard. Foranypermutation, wesaythattheorder ofthepermutation isthesmallest powerofthat 5 permutation thatistheidentity .Thus ifPisacycle of17elements, itwillhaveorder 17,since 17applications ofit willreturn everyballtoitsoriginal box. IfPisnotacycle, butiswritten inproper cycle form, then theorder ofPistheleast common multiple ofthe cycle lengths. This ispretty obvious—consider thepermutation P=(12345)(678) .Ifweconsider thatPn= (12345)n(678)n,then tomakePn=e,wemust havethatboth(12345)n=eand(678)n=e.Thefirstwillbetrue ifnisamultiple of5;thesecond ifnisamultiple of3.Forboth tobetrue,nmust beamultiple ofboth 5and3,and thesmallest number thatisboth istheleast common multiple ofthetwo:15inthiscase. 3The “Befuddler” Notation From nowwewilluseRubik’ sCube forsome ofourexamples ofpermutations. Forthatreason, weneed areasonable notation todescribe themovesthatcanbemade. Here wearetalking only about thestandard 333cube, although much ofwhat wedocaneasily beapplied toother versions. Thecube hassixfaces, each ofadifferent color ,butdifferent cubes havedifferent coloring patterns, soitisuseful to haveanotation thatisindependent oftheparticular coloring ofacube. Here isagood method todescribe ageneral move.Imagine thatyouhold thecube infront ofyoulooking directly at thecenter ofoneface, andwith thetopandbottom faces parallel totheground. There aresixfaces—the front and back, theupanddown,andtheleftandright. Conveniently ,thefirstletters ofthese words arealldifferent: F,B, U,D,L,R.Rearrange them as“BFUDLR”,anditreminds youoftheEnglish word, “befuddler”, which isalso appropriate fordescribing thegeneral difficulty oftheproblems presented bythecube. There aresixprimiti vemovesthatcanbemade—an yofthesixfaces canbeturned 1/4turn clockwise. Obviously , ifyouwanttoturn afacecounter -clockwise, that’swhat youwould do,buttokeepthedescription mathematically simple using theminimum number ofprimiti veoperations, remember thatasingle twist counter -clockwise isthesame asthree clockwise twists. By“clockwise” ismeant thatifthefaceinquestion isgrasped intheright hand, itisturned inthedirection pointed to bytheright thumb . Wewill usethebefuddler letters asnames forthese primiti vemoves.Thus themove“F”means that thefront faceisturned 1/4turn clockwise, etcetera. Wecancombine letters aswell. “FUB”means first twist thefront faceclockwise, then twist theupface, then theback face. Alltwists are1/4turn clockwise. Toturn thefront face by1/2turn or3/4turn (3/4 turn clockwise =1/4turn counter -clockwise), usethenotation F2orF3.Note that F4=B4=U4=D4=L4=R4=e,sowecould writeF3asF1equally well. Wewilltend tousetheF1form here. Asafinal example, F2U3TBDmeans toturn thefront faceahalf turn, then twist theupface1/4turn counter - clockwise, follo wed bya1/4clockwise twist ofthetop,then back, andthen downfaces. Ifyouthink oftheentire cube asbeing composed ofabunch ofsmaller “cubies”, thebefuddler notation givesagood method toname theindividual cubies. Thecubies inthecorners areidentified bythethree faces theyshare. Thecube ontheupright front canbecalled URF,andsoon.The edge cubies areidentified bythetwofaces itlieson,so theoneontheupandfront faces would becalled UF.Butinorder todistinguish between thecubie UFandthe transformation thatisarotation about theupfacefollo wed byarotation about thefront face,wewillputboxesaround thecubie names: URFandUFforthecubes justmentioned. Withthiscubie notation, wecandescribe (using ourpermutation cycle notation) certain results thattransformations may achie ve.Forexample, (LDFDRD)refers toanoperation that cycles theleft-do wn,front-do wn,and right-do wncubies. Theleft-do wncubie movesintofront-do wnpostion, etcetera. The notation stillisn’tperfect. You’llfind thatwhen yousolveRubik’ scube thatsometimes acubie will beinthe right place inthecube, butrotated (ifit’sacorner cubie) orflipped (ifit’sanedge cubie). Butwecandescribe itas follo ws.Suppose there isanoperation thatleaveseverything fixed,butflipsUBandULinplace. Wecanwrite this as:UB,UL!BU,LU. 6 4Groups andSubgr oups Agroup isasystem consisting ofasetofobjects andabinary operation thatproduces from anytwoobjects another object thatsatisfies theconditions listed inSection 2(having anidentity ,aninverse, andwith anassociati veoperation). Thesetofallpossible permutations ofasetofelements isaspecial group called the“symmetric group”. Thesymmetric group onnobjects isthegroup consisting ofallpermutations ofnelements, soitcontains n!elements—in other words, thesymmetric groups getbigpretty fastasngetslarger.Inthispaper wewilldenote thesymmetric group on nelements bySn. Most practical applications useonly asubset ofthepossible permutations. InRubik’ sCube, forexample, although there are54little colored faces, itisclear thattheones inthecorners willalwaysbeinsome corner ,theones onthe edges remain ontheedges, andtheones inthecenters ofthefaces remain centers offaces. Thus inthecollection of permutations reachable from asolvedcube, there arenone thatmove,say,acorner toanedge. Wewillbeinterested inspecial subsets ofgroups thatarethemselv esgroups—in other words, anon-empty subset of thepermutations sothatanyproduct ofpermutations inthesubset isanother permutation inthesubset. Inourearlier example ofSn(thesymmetric group onthree elements), there arethefollo wing subgroups (including thegroup thatcontains only theidentity andtheentire symmetric group): f(1)g;f(1);(12)g;f(1);(13)g;f(1);(23)g;f(1);(123);(132)g; f(1);(12);(13);(23);(123);(132)g: There aren’ tanyothers. Ifyoutrytoconstruct some, you’llseewhat happens. Asanexample, suppose wetrytomake onethatcontains (12) and(123) . Itwillhavetocontain (12)2=(1)and(123)2=(132) .Itwillalsohavetocontain (123)(12) =(23) and(132)(12) = (13).Butnowwe’veshownthatitmust contain allthepermutations inthesymmetric group, soS3isthegroup generated by(12) and(123) . Ifyouareabeginner with Rubik’ sCube andyouwanttopractice with some operations thatjumble thecube butdonot jumble itintoanightmare, consider restricting yourself toasubgroup ofalltheallowable moves.Here areacouple of good examples: Only allowmovesthatconsist of180turns oftwoopposite faces atthesame time. Basically ,there areonly 3 moves:R2L2,U2D2,andF2B2.These generate some nice patterns aswell. This isaverysimple subgroup. This oneismore complicated, butstillnottoobad. It’sbasically thesame astheoneabove,except thatyou’re allowed todosingle turns oftheopposite faces, such asLR1,UD1,andFB1.Byrepeating these moves youcan, ofcourse, gettoanyposition inthesubgroup above,butthere aremany more possibilities. 5EvenandOdd Permutations Beginwith thefollo wing exercise: verify thefollo wing products ofpermutations: (12) =(12) (12)(13) =(123) (12)(13)(14) =(1234) (12)(13)(14)(15) =(12345) Although theexpressions ontheleftarenotinproper cycle notation, thisdoes showthatanycycle canbeexpressed asaproduct of2-cycles, orexchanges. This example showsthatacycle ofnobjects canbewritten asaproduct of (n1)2-cycles. 7 Infact,there areclearly aninfinite number ofwaystoexpress anypermutation asaproduct of2-cycles: (123) =(12)(13) =(12)(13)(12)(12) =(12)(13)(12)(12)(12)(12) =


Butitistruethatifapermutation canbewritten asanevennumber ofcycles, anyrepresentation willcontain aneven number ofcycles. Intheexample above,(123) wasexpressed as2;4;6;


cycles. Similarly ,ifapermutation allows arepresentation asanoddnumber ofcycles, allits2-cycle representations willcontain anoddnumber of2-cycles. All permutations canbedivided intothese “even”and“odd” permutations. Itrequires proof, ofcourse, thatitisimpossible torepresent apermutation with both anevenandanoddnumber of 2-cycles, andthatwillbeshowninSection 5.1. Theidentity isanevenpermutation (zero 2-cycles), andclearly ifyoumultiply anyevenpermutation byanother even permutation, youwillgetanevenpermutation. Thus thesetofallpermutations thatareevenform asubset ofthefull symmetric group. This iscalled the“alternating group”, andthealternating group onnobjects iscalled An. Table 3isthemultiplication table forthealternating group A4.Itisagreat example ofagroup thatiscomplicated, butnottoocomplicated. Seewhat subgroups ofityoucanfind. (1) (123) (124) (134) (234) (132) (142) (143) (243) (12)(34) (13)(24) (14)(23) (1) (1) (123) (124) (134) (234) (132) (142) (143) (243) (12)(34) (13)(24) (14)(23) (123) (123) (132) (13)(24) (234) (12)(34) (1) (143) (14)(23) (124) (134) (243) (142) (124) (124) (14)(23) (142) (13)(24) (123) (134) (1) (243) (12)(34) (143) (132) (234) (134) (134) (124) (12)(34) (143) (13)(24) (14)(23) (234) (1) (132) (123) (142) (243) (234) (234) (13)(24) (134) (14)(23) (243) (142) (12)(34) (123) (1) (132) (143) (124) (132) (132) (1) (243) (12)(34) (134) (123) (14)(23) (142) (13)(24) (234) (124) (143) (142) (142) (234) (1) (132) (14)(23) (13)(24) (124) (12)(34) (143) (243) (134) (123) (143) (143) (12)(34) (123) (1) (142) (243) (13)(24) (134) (14)(23) (124) (234) (132) (243) (243) (143) (14)(23) (124) (1) (12)(34) (132) (13)(24) (234) (142) (123) (134) (12)(34) (12)(34) (243) (234) (142) (124) (143) (134) (132) (123) (1) (14)(23) (13)(24) (13)(24) (13)(24) (142) (143) (243) (132) (234) (123) (124) (134) (14)(23) (1) (12)(34) (14)(23) (14)(23) (134) (132) (123) (143) (124) (243) (234) (142) (13)(24) (12)(34) (1) Table 3:TheAlternating Group A4 5.1ParityPreservation Earlier inthissection weshowed thatitispossible torepresent anypermutation asaproduct of2-cycles, andwestated without proof thatanysuch representation ofagivenpermutation willalwayscontain anevennumber ofcycles orit willalwayscontain anoddnumber ofcycles. Wewillprovethatfactbyshowing thatitispossible toassign aparity (evenorodd) toanypermutation inaunique wayandthatmultiplication ofanevenpermutation bya2-cycleproduces anoddpermutation andvice-v ersa. When written incanonical form, apermutation willhaveacertain number c1of1-cycles, c2of2-cycles, c3of3-cycles andsoon.Wedefine theparity ofsuch apermutation as: X ncn(n+1)mod2: (1) This makessense from theobserv ation that(123


n)=(12)(13)


(1n)soeverycycle oflength ncanbewritten asaproduct ofn1different 2-cycles. What wewillshowisthatifthispermutation ismultiplied byanother 2-cycle thattheparity ofthesum inequation 1switches. Assume thateveryelement islisted inthecanonical permutation representation including those elements thatdonot movewhich arelisted as1-cycles. Ifthispermutation ismultiplied bythe2-cycle(km)then there aretwopossibilities: either thetwoelements kandmareinthesame cycle ortheyappear indifferent cycles (where thecycles inwhich theyappear may havelength 1). 8 First consider thecase where theylieinthesame cycle. That cycle will look likethis:(kk2k3


kimm2


mj). This cycle contains i+jelements andwillthus addi+j+1tothesum inequation 1.Ifthiscycle ismultiplied onthe right by(km),weobtain: (kk2


ki)(mm2


mj).Thetworesulting cycles oflengths iandjwilladdi+1+j+1 tothesum, sotheparity willswitch. Finally ,ifkandmappear indifferent cycles: (kk2k3


ki)(mm2


mj),then ifthisismultiplied ontheright by (km)weobtain: (kk2


kimm2


mj).Inthiscase, theoriginal cycle form contrib utedi+1+j+1tothesum in equation 1andafter multiplication thesingle cycle result contrib utesi+j+1,soagain, theparity changes. 5.2The44SlidingBlockPuzzle Youhaveprobably seen thesliding block puzzle with44spaces and15blocks numbered 1through 15,andthe object istotrytoslide them until theyareinorder .Ifyoubeginwillallofthem inorder except that14and15are reversed, there isnosolution. Inother words, there isnowaytoconvertthesituation shownbelowonthelefttothe “solv ed”condition ontheright. 1 2 3 4 5 6 7 8 9 10 11 12 13 15 141 2 3 4 5 6 7 8 9 10 11 12 13 14 15 This canbeprovedbyshowing thatthesliding operation islikeapermutation group, andthattheswapping oftwo blocks amounts toanoddpermutation inthatgroup, buttheoperation ofsliding ablock isanevenpermutation. No matter howmanyevenpermutations youputtogether ,itwillneverbeodd. ABCD E FG HIJK LMNOABCD E FGK HIJO LMNABCD E IFG HJKO LMN The basic idea isillustrated inthediagrams above.Suppose thatinitially thesituation isasshownintheleft-most diagram where thevariables Athrough Nrepresent thenumbers 1through 15insome order .Foranysuch situation where theopen square isnotinthelower-right corner ,weagree toconvertittothatform firstbymoving allpossible blocks totheleftandthen moving allpossible blocks up.Theresult ofthiswhen applied totheleftdiagram isthe diagram inthecenter .After these movesaremade, thesituation isapure permutation ofthenumbers 1through 15 which haseither evenoroddparity . Ontheleft,there arefour possible moves.IfEorFismoved,then thesituation isunchanged after moving theblank square tothelower-right asdescribed above.ButifblockIismovedupthen after themovement oftheblank square tothelower-right corner isshowninthediagram ontheright. Itiseasy tocheck thatthisisobtained from theone inthemiddle bythepermutation (FIJKG)–anevenpermutation. Thus inboth cases, theresult ofamovement ofa single block results inanevenpermutation oftheblocks. Obviously afewother cases need tobeconsidered, butthe results willbesimilar .Hence, itisimpossible toreversejustonepairofblocks such asswapping the14and15pair. 9 6Generators Suppose youpick some complete symmetry group andchoose some number ofpermutations from it.Then youcon- struct thesmallest subgroup thatcontains allofthem. This isthesubgroup generated bytheinitial setofpermutations youchose. Using again S3asourexample, what isthesubgroup generated byf(123)g?Well,ithastocontain (123) itself, (123)2=(132) ,(123)3=(1)andnothing elsesince higher powers of(123) start repeating: (123)4=(123)3(123) = (1)(123) =(123) .Ingeneral, ifn>=3,(123)n=(123)n3.Weknowthatf(1);(123);(132)gisasubgroup of S3soitisthesubgroup generated by(123) . Using Rubik’ sCube asanexample, ifyou’veplayed with it,youknowthatthere arebillions (acutally ,there arealot more!) ofpermutations inthe“Rubik’ sCube group”, butifweconsider asagenerator a1/4-twist ofthefront (inother words, theFmove),youcanseethatifthatistheonly operation you’reallowed todo,there areonly four possible rearrangments ofthecube youcanachie ve.Sothatparticular generator willgenerate asubgroup ofsize4. Ifyouhaveacube handy ,here’ sanexercise. Beginwith asolvedcube. Youareonly allowed tomaketwosorts ofmove:F2andR2,inother words, only180rotations about thefront andright faces areallowed. These moves certainly arepermutations ofthecube’ sfaces. Showthattheorder ofthesubgroup theygenerate is6.Inother words, showthatyoucanonly getthecube into6different patterns (including the“solv ed”pattern) ifF2andR2aretheonly allowed moves. Ifwehaveafinite group (and that’stheonly sortweconsider inthispaper), everyelement hassome finite order .The proof iseasy: LetPbesome permutation, andconsider P1;P2;P3;:::.eventually ,since there areonly afinite number ofelements inthegroup, there hastobesomeiandjsuch thatPi=Pj.Assume j>i.ThenPjiPi=Pj=Pi.Thus Pji=e,theidentity . Wecanalso seethatit’struesince everypermutation expressed inproper cycle form willhaveanorder equal tothe least common multiple ofthelengths ofitscycles aswestated previously .Theadvantage oftheproof intheprevious paragraph isthatitapplies toallfinite groups—not justpermutation groups. Ontheother hand, itissometimes quite difficult toguess what theorder ofanelement ofthepermutation group might be.Forexample, consider thefollo wing permutation ofRubik’ sCube: FR.Suppose thatitisoneindivisible move. itisobvious thatboth theFandRmovesbythemselv eshaveorder 4—4 such turns return thecube totheoriginal condition. Butifyouconsider thepairofturns tobeasingle move,what istheorder ofthat? Theanswer turns outto be105—not anobvious result! Myinitial (and verypainful) solution tothecube wasbased ontheaboveconcept. Iknewthatanyoperation, if repeated enough times, would return aninitially solvedcube back tothesolvedcondition. Butbyexperimentation, I found thatifmyoperation required, say,24repeats togetfrom solvedtosolved,veryoften thecondition after 12or8 moves(these aredivisors of24)would leavemost ofthecubies fixed. Itispretty obvious why thisworks. Imagine apermutation with acycle structure likethis:P=(123)(4567)(89) .We knowthatP12=e,butwhat doesP6orP4look like?Workitout:P6=(46)(57) ,P4=(123) .Doyouseewhat’ s going on? Here isaninteresting exercise. Showthatifyouhaveasubgroup ofSnthatcontains (12) and(123


n),then the subgroup istheentire group Sn.Inother words, anypossible permutation ofnobjects canbeexpressed assome product ofa2-cycle andann-cycle. (Hint: IfP=(123


n),consider thepermutations P(12)P1,P2(12)P2, ...,Pn(12)Pn.) 7Conjugates IfPandQareanypermutations, then thepermutation PQP1iscalled aconjugate ofP.Ingroup theory ,aconjugate operation isverymuch likeachange incoordinate system. 10 Here’ saconcrete example from Rubik’ sCube. Suppose thatyouknowhowtoswaptwocorner pieces thatareonthe same edge (see Section 10.1; let’scallthisoperation Q),butyou’refaced with acube where thecorners youwould liketoswaparenotonthesame edge. Noproblem—find asimple operation (call itP)thatbrings thetwocorners of interest tobeonthesame edge. Ifyouperform P,thenQ,andthen “undo” P(inother words, perform P1,thenet effectwillbetomovethecorners tothesame edge, swapthecorners onthatedge, andthen movethecorners back to where theybegan. Doing P,thenQ,thenP1isthesame asdoing PQP1—aconjugate ofQ. 8Commutators IfPandQareanypermutations, then thecommutator ofPandQisPQP1Q1.It’sjustaconjugate with one additional operation ofQ1tagged onto theend. Here’ sanexample ofacommutator inaction. Suppose thatyouwanttofindanoperation thatflips twoedge cubies on thesame faceinplace without affecting anyoftheother cubies. It’snothard tofindaseries ofmovesthatleavesone facecompletely fixedexcept forflipping asingle cubie onitbutperhaps hopelessly jumbles therestofthecube. Call theoperation thatdoes thisP.NowletQbeasingle twist ofthatfacethatputs another cubie inthesame slotwhere theflipped cubie was.What doesPQP1Q1do? Pflips thecubie (buttrashes therestofthecube that’snotontheface).Qmovesadifferent cubie tothatslot.P1 then undoes allofthedamage caused byPontherestofthecube, butflips thenewcubie. Q1justrotates thefacein question back toitsoriginal condition. Theoperation inSection 10.4 isjustsuch acommutator . 9Repr esentations ofArbitrary Groups InSection 4westated thatgroups areusually defined without reference topermutations. Themathematical definition ofagroup issimply asetofelements andabinary operation onthatsetthathasanidentity ,inverses ofeach element, andisassociati ve.Infact,the“multiplication table” listed belowrepresents avalidbinary operation ontheelements E;A;B;andCwhere Eistheidentity: EABC EEABC AAECB BBCEA CCBAE Itiseasy toprove,however,thatforanysuch group itispossible todefine apermutation group thatbeha vesinexactly thesame way.Here ishowtodoitforthegroup above:E$(e)(a)(b)(c),A$(ea)(bc),B$(eb)(ac)and C$(ec)(ab).Doyouseehowthisisrelated tothegroup multiplication table? Check toseethattheoperations workthesame. Forexample, showthatifAB=C,then theproduct ofthepermuta- tions corresponding toAandByield thepermutation thatcorresponds toC,etcetera. Thus, inasense,allgroups canbeconsidered tobepermutation groups. 10 Inter esting Rubik Permutations (Spoiler!) This section contains enough information foryoutosolveyour cube without much thinking. Don’ tlook atitifyou liketosolvepuzzles byyourself. Here aresome operations thatmay provetobeuseful insolving thecube puzzle. Thefirstthree movethecubies as indicated, butsome ofthem alsomay fliptheedges orrotate thecorners. Thefinal twooperations leaveallthecubies inplace, butflipedge cubies orrotate corner cubies asindicated. 11 There arealmost certainly better methods available—these arejusttheones Ifound myself. Fortheinitial stages of solving acube, theyarealso toopowerful. Ifyou’rejusttrying togetthetopfacecorrect from acompletely jumbled cube, youdon’treally care what youdototheother cubies, butalltheexamples belowareveryrestricti ve—only the indicated cubies move;theothers areleftfixedbytheoperations. Warning: Ifyou’restarting with apure cube, becareful tofollo wtheinstructions belowexactly—one error andyour cube will betrashed. Takeitslowlyandremember thatBis“back”, not“bottom”. Also remember thattoundo anoperation, youcanreverse thesteps starting from theback. Forexample, toreverseFL1D2RUR1,perform RU1R1D2LF1.Also, besure tokeepthetopcube ontopandtheright cube ontheright asyou dothese operations. Forexample, ifthetopcube iswhite when youbegin,makesure itstays white through alltheoperations. Another waytoavoidproblems when youareabeginner isalwaystotwist thefaces with your right hand. Then ifitis oneofF,B,L,R,U,orD,youwilltwist inthedirection ofyour thumb .Iftheoperation isamong F1,B1,L1, R1,U1,orD1,you’lltwist awayfrom your thumb .Ifyou’releft-handed, think different. Finally ,itismuch easier tostudy movements ifyoucanbeginwith asolvedcube, butit’spretty easy tomakeanerror andtowind upwith acube that’stotally jumbled. Ifyouhavenoidea howtosolveit,thissituation canbepretty depressing. Butthere isawaytocheat— justtakethecube apart, andputitback together inthesolvedconfiguration. Totakethecube apart, theeasiest wayistotakeascrewdriverandtoputitbetween thecenter cubie ofafaceandone oftheedge cubies, andthen topryouttheedge cubie. Once it’sout,itiseasy toremo vealltherestofthecubies, leaving acentral “skeleton”. From theskeleton, putthecubies back oneatatime intotheir correct positions. 10.1SwapTwoCorners This operation swapstwocorners, butalso jumbles some edge cubies. Useitifyou’replanning togetthecorners in place first, andthen workontheedges. Inaddition tothepermutation specified, italsotwists LFD. (RBDLBD)(RBFDBDLD):RD1R1D1B1DB. 10.2CycleThreeEdgeCubies (LDFDRD):R1LBRL1D2R1LBRL1. (UFUBDB):R1LU2RL1B2. 10.3CycleThreeCornerCubies (LUFRUBLUB):URU1L1UR1U1L. 10.4FlipUBandULInPlace UB,UL!BU,LU:R1LB2RL1D1R1LBRL1ULR1B1L1RDLR1B2L1RU1. 10.5Rotate URBandURFInPlace URB,URF!RBU,RFU:FD2F1R1D2RUR1D2RFD2F1U1. 12