ERROR LOADING HTML FROM SOURCE (http://ncf.sobek.ufl.edu//design/skins/UFDC/html/header_item.html)

Sudoku Scheming

Permanent Link: http://ncf.sobek.ufl.edu/NCFE004416/00001

Material Information

Title: Sudoku Scheming Am Algebraic Combinatorial Approach to Discovering Properties of Sudoku Graphs using Association Schemes
Physical Description: Book
Language: English
Creator: Myer, Ziva
Publisher: New College of Florida
Place of Publication: Sarasota, Fla.
Creation Date: 2011
Publication Date: 2011

Subjects

Subjects / Keywords: Sudoku
Graph Theory
Association Schemes
Genre: bibliography   ( marcgt )
theses   ( marcgt )
government publication (state, provincial, terriorial, dependent)   ( marcgt )
born-digital   ( sobekcm )
Electronic Thesis or Dissertation

Notes

Abstract: In a 2009 paper, Dahl introduced S-permutation matrices and the operation S-interchange performed on these matrices. These concepts combine to make the Sudoku Graph of order N (which we call ?N). Dahl offered an upperbound and lowerbound for the diameter of the Sudoku Graph. Using his work as a starting point, we focused mainly on the Sudoku Graphs for N=4,9. We found ?4 to be the hypercube graph, and studied the association scheme, the Hamming Scheme, on its distances, showing it to be distance regular. Forming an alternative notation, Block Coordinate Notation (BCN), for S-permutation matrices, we wrote a program in Python to assist with counting distances in the much larger graph ?9. We found that is not distance regular, even though the distances are consistent for any starting vertex. Lastly, we proved that the diameter of ?9 is 12 and proposed a general conjecture for the diameter of ?N.
Statement of Responsibility: by Ziva Myer
Thesis: Thesis (B.A.) -- New College of Florida, 2011
Electronic Access: RESTRICTED TO NCF STUDENTS, STAFF, FACULTY, AND ON-CAMPUS USE
Bibliography: Includes bibliographical references.
Source of Description: This bibliographic record is available under the Creative Commons CC0 public domain dedication. The New College of Florida, as creator of this bibliographic record, has waived all rights to it worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law.
Local: Faculty Sponsor: Piomenidou, Eirini

Record Information

Source Institution: New College of Florida
Holding Location: New College of Florida
Rights Management: Applicable rights reserved.
Classification: local - S.T. 2011 M99
System ID: NCFE004416:00001

Permanent Link: http://ncf.sobek.ufl.edu/NCFE004416/00001

Material Information

Title: Sudoku Scheming Am Algebraic Combinatorial Approach to Discovering Properties of Sudoku Graphs using Association Schemes
Physical Description: Book
Language: English
Creator: Myer, Ziva
Publisher: New College of Florida
Place of Publication: Sarasota, Fla.
Creation Date: 2011
Publication Date: 2011

Subjects

Subjects / Keywords: Sudoku
Graph Theory
Association Schemes
Genre: bibliography   ( marcgt )
theses   ( marcgt )
government publication (state, provincial, terriorial, dependent)   ( marcgt )
born-digital   ( sobekcm )
Electronic Thesis or Dissertation

Notes

Abstract: In a 2009 paper, Dahl introduced S-permutation matrices and the operation S-interchange performed on these matrices. These concepts combine to make the Sudoku Graph of order N (which we call ?N). Dahl offered an upperbound and lowerbound for the diameter of the Sudoku Graph. Using his work as a starting point, we focused mainly on the Sudoku Graphs for N=4,9. We found ?4 to be the hypercube graph, and studied the association scheme, the Hamming Scheme, on its distances, showing it to be distance regular. Forming an alternative notation, Block Coordinate Notation (BCN), for S-permutation matrices, we wrote a program in Python to assist with counting distances in the much larger graph ?9. We found that is not distance regular, even though the distances are consistent for any starting vertex. Lastly, we proved that the diameter of ?9 is 12 and proposed a general conjecture for the diameter of ?N.
Statement of Responsibility: by Ziva Myer
Thesis: Thesis (B.A.) -- New College of Florida, 2011
Electronic Access: RESTRICTED TO NCF STUDENTS, STAFF, FACULTY, AND ON-CAMPUS USE
Bibliography: Includes bibliographical references.
Source of Description: This bibliographic record is available under the Creative Commons CC0 public domain dedication. The New College of Florida, as creator of this bibliographic record, has waived all rights to it worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law.
Local: Faculty Sponsor: Piomenidou, Eirini

Record Information

Source Institution: New College of Florida
Holding Location: New College of Florida
Rights Management: Applicable rights reserved.
Classification: local - S.T. 2011 M99
System ID: NCFE004416:00001


This item is only available as the following downloads:


Full Text

PAGE 1

SudokuScheming: AnAlgebraicCombinatorialApproachtoDiscoveringPropertiesof SudokuGraphsusingAssociationSchemes ZIVAKAYEMYER AThesis SubmittedtotheDivisionofNaturalSciences NewCollegeofFlorida inpartialfulllmentoftherequirementsforthedegree BachelorofArts UnderthesponsorshipofProfessorEiriniPoimenidou Sarasota,Florida May,2011

PAGE 2

Acknowledgements IwouldrstliketothankProfessorEiriniPoimenidouforeverythingshe'sdone tohelpmewithmythesisandallherguidanceandadvisingthisyear.Iespecially appreciatehernever-endingcondenceinmeandoverallsupport!Abigthanksalso toProfessorPatMcDonald,foralltheadviceandanecdotesovertheyears{boththe onesthatmademelaughandtheonesthatfreakedmeoutgraduateschoolhorror stories....I'velearnedsomuchaboutmathfrombothofyou,andyou'vebothreally helpedmeappreciatethebeautyinpuremathematics. ThankyoualsotoProfessorGeorgeRuppeinerforagreeingtobeonmybaccalaureatecommittee.It'sbeenapleasureworkingwithyouduringmytimeatNew College! AveryspecialthankyoutoDavidWyde,myPythonhero,forpatientlyteaching mehowtoprogram,helpingmedesignmyprogram,andxingallmymistakessoI couldnishmythesis.Icouldn'thavedoneitwithoutyou! Alastbutcertainlynotleastthankyoutomymother,Lori-NanKaye,forall heramazingsupportthisyearandmyentirelife.Iloveyou!

PAGE 3

SudokuScheming: AnAlgebraicCombinatorialApproachtoDiscoveringPropertiesofSudokuGraphs usingAssociationSchemes ZivaKayeMyer NewCollegeofFlorida,2011 ABSTRACT Ina2009paper,Dahlintroduced S -permutationmatricesandtheoperation S interchangeperformedonthesematrices.Theseconceptscombinetomakethe SudokuGraphoforder N whichwecall )]TJ/F34 7.9701 Tf 8.081 -1.793 Td [(N .Dahloeredanupperboundand lowerboundforthediameteroftheSudokuGraph.Usinghisworkasastarting point,wefocusedmainlyontheSudokuGraphsfor N =4 ; 9.Wefound )]TJ/F31 7.9701 Tf 8.08 -1.793 Td [(4 tobe thehypercubegraph,andstudiedtheassociationscheme,theHammingScheme,on itsdistances,showingittobedistanceregular.Forminganalternativenotation, BlockCoordinateNotationBCN,for S -permutationmatrices,wewroteaprogram inPythontoassistwithcountingdistancesinthemuchlargergraph )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 .Wefound thatisnotdistanceregular,eventhoughthedistancesareconsistentforanystartingvertex.Lastly,weprovedthatthediameterof )]TJ/F31 7.9701 Tf 8.081 -1.794 Td [(9 is12andproposedageneral conjectureforthediameterof )]TJ/F34 7.9701 Tf 8.081 -1.793 Td [(N ProfessorEiriniPoimenidou DivisionofNaturalSciences

PAGE 4

Contents Chapter1.Introduction1 Chapter2.SudokuPermutationMatricesandtheSudokuGraph5 1.IntroductiontotheSudokuGraph5 2.BlockCoordinateNotation8 Chapter3.AssociationSchemes16 1.ThePartitionDenitionofAssociationSchemes16 2.TheMatrixDenitionofAssociationSchemes19 3.Distance-regulargraphs20 4.CharacterizationsofAssociationSchemesontheCube22 Chapter4.The n =2Case25 Chapter5.The n =3Case31 1.Propertiesof )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 31 2.AnAssociationSchemeon )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 ?43 Chapter6.ConclusionandFurtherWork47 AppendixA.Code50 Bibliography56 iii

PAGE 5

CHAPTER1 Introduction Figure1. WhyMath?"{acomicfromSpikedMath[ 12 ]onSudoku Sudokuisapopulargamethatmostpeopleconsidertobealogicpuzzleasopposedtoamathpuzzle,asthewebcomicabovefromSpikedMath[ 12 ]jokesabout. Thereis,however,anunderlyingmathematicalnatureofthepuzzlethatmanymathematicianshavestudied.WepresentexamplesofsomeofthemathematicsofSudoku inthisintroduction,andthendevotetherestofthethesistoexplainingandclassifyingonespecicproblem,thediameterofSudokuGraphsasdenedbyDahl[ 4 ]in 2009. ThemostcommonSudokupuzzleisa9 9gridsplitupintonine3 3blocks, withsomestartingpositionslledin.Acompletedpuzzlewillcontaineverynumber from1to9exactlyonceineveryrow,column,andblock.Wecanalsoconsiderother sizesofSudokupuzzlesas n 2 blocks,eachofsize n n ,inan n 2 n 2 grid.Inthe generalcase,whencompleted,everyrow,column,andblockwillcontaineveryinteger from1to n 2 exactlyonce. Sudokuisaspecialcaseofa latinsquare, an n n arraylledwith n dierent symbols,witheachsymbolappearingexactlyonceineveryrowandcolumn.Infact, Sudokuisalsoaspecialcaseofa gerechtedesign ,an n n Latinsquaredivided into n regionswith n cellsineachregion.Acompletedgerechtedesignwillbea 1

PAGE 6

completedLatinsquarewiththeadditionalconstraintthattheremustbeexactly oneofeveryintegerfrom1to n ineveryregion.Bailey,Cameron,andConnelly[ 2 ] studiedtheseandspecicSudokuarrangementsinrelationtoahandfulofdierent topics,includingcodingtheoryandanespaces.Theyrelatedthesetoaspecic application:gerechtedesignsareanimportanttoolinagriculturalexperimentsin relationtolayingoutcropsmosteectivelygivenasetofvariationsinaeld,such ascropvarietiesorvaryingamounts/typesoffertilizer.Anexampleisshowninthe picturebelow,from[ 2 ]. Figure2. A2004agriculturalexperimentina6 6latinsquareto comparemethodsofcontrollingaphids,byLesleySmartatRothamsted Research,pictureandinformationtakenfrom[ 2 ] MostotherSudokumathresearchconcernsitselfwithpropertiesofSudokupuzzles,completedandincomplete.Apopularproblem,untilitwassolvedbyFelgenhauerandJarvis[ 5 ],wastocountthenumberofSudokupuzzlesuptoequivalence. EquivalentSudokugridsreferstooperationssuchaspermutingthenumbers,transposingthematrix,andcertainrow/columnoperationsthatpreservethepuzzle.They foundthenumberofpossibleSudokupuzzlestobe6 ; 670 ; 903 ; 752 ; 021 ; 072 ; 936 ; 960 6 : 671 10 21 beforeaccountingforvariousequivalences,astherearemanydierent waystodothat. 2

PAGE 7

Constructingminimalpuzzlesi.e.,puzzlesthathavetheleastnumberofgiven entriesbutstillhaveauniquesolutionhasbeenanotherpopularprobleminSudoku math.Itiswidelybelievedthattheminimalnumberofstartingentriesnecessaryto produceauniquesolutionis17,butthishasnotbeenproven.GordonRoyle[ 11 ]has collectedalmost50,000non-equivalentSudokupuzzleswith17entries.Noonehas foundauniquepuzzlewith16entries. HerzbergandMurty[ 8 ]consideredaSudokupuzzleasagraphadierentgraph thantheoneswewillinvestigateinthisthesis.Theverticesarethe81squaresina Sudokupuzzle,andtwoverticesareconnectediftheyareinthesamerow,column, orblock.Thentherewillbeavertexcoloringofthegraphwithninecolorssuch thatnotwoadjacentverticesarethesamecolorifandonlyifthepuzzleissolvable. ThisgivesanewwaytoconsideralotoftheotherSudokumathproblems,likethe minimaluniquepuzzleone,forinstance. TherearemanymoretopicsinSudokumathresearch:algorithmstosolvepuzzles andSudokupuzzlesgeneratedbycertaingroupmultiplicationtablesareacouplemore examplesthatwewillnotexplorefurther.Instead,weoerabriefoverviewofthe restofthethesis: WewillspendthenextchapterexploringDahl'swork[ 4 ]on S -permutationmatrices, S -interchanges,andtheSudokuGraphbuiltonthesedenitions.OneimportanttheoremofhisgivesupperandlowerboundsforthediameterofSudoku Graphs.Then,Inthesecondhalfofthechapter,weintroduceanewnotationfor S permutationmatrices.Thisnotationallowsustogivemoreintuitiveproofsforsome ofDahl'sresultsandisthefoundationformanynewresultsofourownthroughout thethesis. Thenextchapterisanoverviewofvariousdenitionsofassociationschemes. Thesearebinaryrelationscalledassociateclassesonasetwithacoupleofdeningproperties,likesymmetry.Associationschemesaroseinstatisticsbuthavesince 3

PAGE 8

becomeveryimportantintheeldofalgebraiccombinatorics.Thevariousclassicationsofassociationschemescoveredinthethirdchapterillustratethenumerous wayswecanconsiderourobjectsofstudy.Weareespeciallyinterestedintheassociationschemeformedonthedistancesofdistanceregulargraphs.Weformsuchan associationschemeinthethirdchapterwhenweexplorethe n =2case.Weshow thattheSudokugraphforthiscaseisthehypercubegraph,andformanassociation schemeonit. Lastly,weexaminethe n =3caseof S -permutationmatricesofthesizemost commonlyassciatedwithaSudokupuzzle.Wedidnotndthisgraphtobedistance regular,butweoermanyresultsregardingpropertiesofthisgraph,includinga distancefunctionbetweenanytwoverticesinthegraphandaproofthatthediameter is12.WenishthechapterbydescribingaPythonprogramwewroteandtheresults foundfromit{mainly,thatthereisnoassociationschemeonthedistancesasinthe n =2case.Lastly,weoutlinepossiblefutureworkandconcludewithaconjecture forthegeneralcasethatthediameterwillalwaysbetheupperboundprovidedby Dahl. 4

PAGE 9

CHAPTER2 SudokuPermutationMatricesandtheSudokuGraph 1.IntroductiontotheSudokuGraph Let N = n 2 for n 2 N .Weconsider N N matriceswith N squareblockseach oforder n .Moreprecisely,a block isthesetofpositions f i;j : k )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 n
PAGE 10

wherethe P i 'saredisjoint S -permutationmatrices. Example 2.3 Inthisexamplefor N =4 ,notethatthe S -permutationmatrices inthedecompositionofthecompletedSudokupuzzlearedisjointandthattheysum to J 4 ,thematrixofall1's. A = 2 6 6 4 24 31 13 24 31 42 42 13 3 7 7 5 =1 2 6 6 4 00 01 10 00 01 00 00 10 3 7 7 5 +2 2 6 6 4 10 00 00 10 00 01 01 00 3 7 7 5 +3 2 6 6 4 00 10 01 00 10 00 00 01 3 7 7 5 +4 2 6 6 4 01 00 00 01 00 10 10 00 3 7 7 5 Wedenotethesetofall S -permutationmatricesoforder N = n 2 by N .When werefertothe k thblockrow ,wemeanthesetofpositionsspanningthe i coordinates k )]TJ/F25 11.9552 Tf 11.367 0 Td [(1 n
PAGE 11

the1'sinthe i +1thblockrow.Thus,wehave j N j = n n n n n )]TJ/F25 11.9552 Tf 11.956 0 Td [(1 n ::: n !2 n n !1 n = n n n n = n 2 n asrequired. Considerthetwomatrices L 2 = 01 10 and I 2 = 10 01 Definition 2.5 An S-interchange inamatrix A 2 N isareplacementofa submatrixthatisequalto L 2 with I 2 orviceversa,andthissubstitutionmustoccur inthesameblockroworblockcolumnof A Example 2.6 Belowisaseriesofthree S -interchangesperformedonanelement A 2 4 .The1'sthatareaectedbythe S -interchangesareinbold.Notethateach matrixappearingbelowisadistinctelementof 4 A = 2 6 6 4 00 0 1 0 1 00 10 00 00 10 3 7 7 5 2 6 6 4 01 00 00 0 1 10 00 00 1 0 3 7 7 5 2 6 6 4 01 00 00 10 1 0 00 00 0 1 3 7 7 5 2 6 6 4 01 00 00 10 00 01 10 00 3 7 7 5 Example 2.7 For N =9 ,hereisanexampleofavalid S -interchangetothe matrix B .Here,thesubmatrix I 2 inrows2and8,columns1and3,isswitchedto L 2 .Whenthis S -interchangeoccurs,weobtainanotherelementof 9 .Thisisavalid S -interchangebecauseitoccursinasubmatrixcontainedinoneblockrow/columninthiscase,therstblockcolumn. B = 2 6 6 6 6 6 6 6 6 6 6 6 4 000 010 000 1 00 000 000 000 000 010 010 000 000 000 000 100 000 001 000 000 100 000 00 1 000 000 000 000 001 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 010 000 001 000 000 000 000 010 010 000 000 000 000 100 000 001 000 000 100 000 100 000 000 000 000 001 3 7 7 7 7 7 7 7 7 7 7 7 5 7

PAGE 12

Notethat N isclosedunder S -interchanges:ifweapplyan S -interchangeto an S -permutationmatrixoforder N weobtainadierent S -permutationmatrixof order N .Thismotivatesthedenitionofourobjectofstudy: Definition 2.8 The SudokuGraphoforderN ,denoted )]TJ/F34 7.9701 Tf 8.08 -1.793 Td [(N ,isthegraph whosevertexsetis N ,thesetofall N NS -permutationmatrices,withanedge betweentwo S -permutationmatricesifthereexistsan S -interchangethattransforms oneintotheother. Theorem 2.9 )]TJ/F34 7.9701 Tf 8.081 -1.793 Td [(N isconnectedwithdiameteratleast = 2 n 2 andatmost 2 n n )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 ThistheoremisprovedbyDahl[ 4 ],butwewilloeramodiedproofafterwe introduceanalternativenotationfortheelementsof N inthefollowingsection. 2.BlockCoordinateNotation Drawingout S -permutationmatricesisnotveryecientandcomeswithalarge chanceoferrors,soitisusefultointroduceanewandmoresuccinctnotationforthe elementsof N thatwewillcall BlockCoordinateNotationBCN .Theconceptis simple:Consideran S -permutationmatrixoforder N asthelarger N N matrix asopposedtoasetof N matricesofsize n n .Thenifwelisttherowandcolumn positionsofthe N onesinthelargermatrix,wehavealltheinformationweneedto drawit,sinceallotherpositionswillbe0's. BeforewedeneBCNpreciselyinthegeneral n caseandexamineproperties ofmatricesinthisnotation,itisusefultodeneitfor n =3andconsiderafew examples.First,weorderthenineblocksofan S -permutationmatrix A 2 9 from righttoleft,asshowninthematrixbelow,witheachnumberrepresentinga3 3 block. 2 4 1 2 3 4 5 6 7 8 9 3 5 8

PAGE 13

Eachoftheseblocks,bydenition,containsexactlyone1,soweidentify A with thesetoftheninecoordinatepairsofthepositionsofthe1'sinthe9 9matrix.We write A = f i k ;j k g 9 k =1 where i k ;j k isthepositionofthe1inthe k -thblock.Then, sinceweorderedtheblocks,each i k and j k canbeoneofthreenumbersforittobe inthe k -thblock.Forexample,sincethefourthblockisinthesecondblockrowand therstblockcolumn,weknow i 4 2f 4 ; 5 ; 6 g and j 4 2f 1 ; 2 ; 3 g .Sincetherecanonly beone1ineveryrowandeverycolumn,if i k = i k 0 or j k = j k 0 ,then k = k 0 .With thesetwoproperties,wecanwrite f i 1 ;i 2 ;i 3 g = f j 1 ;j 4 ;j 7 g = f 1 ; 2 ; 3 g f i 4 ;i 5 ;i 6 g = f j 2 ;j 5 ;j 8 g = f 4 ; 5 ; 6 g f i 7 ;i 8 ;i 9 g = f j 3 ;j 6 ;j 9 g = f 7 ; 8 ; 9 g Example 2.10 ConsiderthefollowingthreematricesinBCN.Weexamineeach separatelytodeterminewhicharevalid S -permutationmatrices. A = f ; 2 ; ; 4 ; ; 8 ; ; 3 ; ; 5 ; ; 7 ; ; 1 ; ; 6 ; ; 9 g B = f ; 1 ; ; 5 ; ; 6 ; ; 2 ; ; 7 ; ; 8 ; ; 3 ; ; 4 ; ; 9 g C = f ; 3 ; ; 5 ; ; 9 ; ; 2 ; ; 4 ; ; 7 ; ; 1 ; ; 5 ; ; 8 g First,wechecktoseethateverynumberisonlyusedonceasarowpositionandonce asacolumnposition.Thisisthecasefor A and B ,butnotfor C where j 2 = j 8 =5 soweknow C isnotan S -permutationmatrix.Next,wecheckthateachblockonlyhas one1init,usingthesetsdescribedabove.Wendthat A and C haveeachnumber inanappropriateplace,butin B j 3 and j 5 donotbelongtothecorrectsets.Thus, outofthethree, A istheonlyvalid S -permutationmatrix.Thisiseasilynoticedin matrixnotation: 9

PAGE 14

A = 2 6 6 6 6 6 6 6 6 6 6 6 4 000 100 000 000 000 010 010 000 000 001 000 000 000 000 100 000 010 000 000 000 001 100 000 000 000 001 000 3 7 7 7 7 7 7 7 7 7 7 7 5 B = 2 6 6 6 6 6 6 6 6 6 6 6 4 100 000 000 000 001 000 000 010 000 010 000 000 000 000 010 000 000 100 000 100 000 000 000 001 001 000 000 3 7 7 7 7 7 7 7 7 7 7 7 5 C = 2 6 6 6 6 6 6 6 6 6 6 6 4 000 010 000 001 000 000 000 000 001 000 100 000 010 000 000 000 000 100 000 010 000 100 000 000 000 000 010 3 7 7 7 7 7 7 7 7 7 7 7 5 NowwecangeneralizeBCNforthegeneral n case:wewritethe S -permutation matrix A 2 N astheorderedsetoforderedpairs A = f i k ;j k g N k =1 suchthat a i k j k =1in A Aswedidinthe N =9case,weordertheblocks1 :::N = n 2 infromlefttorightas inthefollowingdiagramwitheachnumberrepresentingan n n block: 2 6 6 4 1 2 ::: n 2 n n 2 3 7 7 5 An S -permutationmatrixinBCNwillhavethefollowingpropertiesandcharacterizations: Everynumberbetween1and N occurs exactlyonceasan i k rowposition and exactlyonceasa j k columnposition.Moreformally, 8 k;k 0 ;l;l 0 2 10

PAGE 15

f 1 ; 2 ;:::;N g i k = i k 0 i k = k 0 and j l = j l 0 i l = l 0 .Thispropertycorrespondstotherequirementthat A isapermutationmatrix,i.e.,thatevery rowandeverycolumncontainsexactlyone1. Theanalogoftherequirementthateachblockhasexactlyone1isalittle morediculttoexpress.First,partitiontheset f 1 ; 2 ;:::;n 2 g into n sets eachofsize n andindexthem: n 1 = f 1 ; 2 ;:::;n g n 2 = f n +1 ;n +2 ;:::; 2 n g n n = f n )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 n +1 ; n )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 n +2 ;:::;n 2 g Ifthe k -thblockintheorderingabovecorrespondstotheintersectionofthe l -thblockrowandthe m -thblockcolumn,thenitcontainsthepositions A lm = f i;j : i 2 n l ;j 2 n m g .Thus, i k ;j k 2 A lm ,andnootherordered pairintheBCNrepresentationof A willbeinthesameset A lm for A tobe avalid S -permutationmatrix. Thesepropertiesleadtoaneasiercharacterizationofan S -interchange:In thisnotation,an S -interchangeisatranspositionoftworownumbersor columnnumbersinthesameset n i .Weillustratethisnotationbyrevisiting theexamplesfromtheprevioussection. Example 2.11 InExample2.6,wesawseriesof S -interchangesappliedtoan element A 2 4 .WepresenttheseinBCN,withtheindicesabouttobetransposed inbold: A = f 2 ; 2 ; 1 ; 4 ; ; 1 ; ; 3 g!f ; 2 ; ; 4 ; ; 1 ; ; 3 g !f ; 2 ; ; 3 ; 3 ; 1 ; 4 ; 4 g!f ; 2 ; ; 3 ; ; 1 ; ; 4 g 11

PAGE 16

Hereweseetheadvantageofwritingtheorderedpairsinblockorder.Noticethat n 1 = f 1 ; 2 g and n 2 = f 3 ; 4 g .Thus,an S -interchangewillbeoneofthetranspositions 2 or 4 ineitheraroworacolumnposition. Example 2.12 InExample2.7,wesawanexampleofan S -interchangeforan S -permutationmatrixin 9 .Writingitoutinmatrixnotationtakesupalotofspace, andndingthe S -interchangeinthebinaryseacanbedicultontheeyes.InBCN thesame S -interchangeismucheasiertospot,andtakesupsignicantlylessspace: B = f ; 1 ; ; 5 ; ; 8 ; ; 2 ; ; 6 ; ; 7 ; ; 3 ; ; 4 ; ; 9 g !f ; 3 ; ; 5 ; ; 8 ; ; 2 ; ; 6 ; ; 7 ; ; 1 ; ; 4 ; ; 9 g WecannowoeraproofforTheorem2.9.Ourproofisanadaptedversionofthe oneDahloered[ 4 ]{themethodisthesame,butinBCN.Werestatethetheorem: Theorem 2.13 )]TJ/F34 7.9701 Tf 8.081 -1.793 Td [(N isconnectedwithdiameteratleast = 2 n 2 andatmost 2 n n )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 Proof. Considertwo S -permutationmatricesinBCN, A = f i k ;j k g N k =1 and B = f i 0 k ;j 0 k g N k =1 .Weconsideranalgorithmfortransforming A into B using S interchanges.Westartwiththerstblock,transforming i 1 ;j 1 into i 0 1 ;j 0 1 bya seriesofatmosttwo S -interchangesexactlytwoif i 1 6 = i 0 1 and j 1 6 = j 0 1 .Wecan continuethisway,onlyperforming S -interchangeswithblockseithertotherightor belowtheblockwearecurrentlyworkingon.Moreprecisely,whileweareinblock k wetransform i k ;j k into i 0 k ;j 0 k byonlyperforming S -interchangeswithpairs i l ;j l suchthat l>k .Thispreservesthecorrectpositionsofthepreviousblocks.Moreover, ifthepreviousblockshavealreadybeencorrected,thenumberweneedtochange ourcurrentpositionintowillhavetobeinahighernumberedblock.Whenwereach theendofaroworcolumn,therewillbeonlyone S -interchangerequired,andthe lastblockwillrequirenone,sowecountthe S -interchanges:2foreachblockinthe 12

PAGE 17

n )]TJ/F25 11.9552 Tf 11.046 0 Td [(1by n )]TJ/F25 11.9552 Tf 11.045 0 Td [(1innersquarematrixandoneforthe n )]TJ/F25 11.9552 Tf 11.046 0 Td [(1blocksinthelastcolumn andlastrow.Summingthisup,weobtainourupperbound: 2 n )]TJ/F25 11.9552 Tf 11.956 0 Td [(1 2 +2 n )]TJ/F25 11.9552 Tf 11.955 0 Td [(1=2 n n )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 Sincewehaveshownhowtotransformageneral S -permutationmatrixintoanother, ourgraphisconnected.Thelowerboundisobtainedfromnoticingthatthereexist completelydistinct S -permutationmatricesinBCN i k 6 = i 0 k and j k 6 = j 0 k 8 k 2 f 1 ; 2 ;:::;N g andone S -interchangecanx,atmost,twoofthe N 1's.Thisgives usalowerboundonthediameterof = 2 n 2 Weshownextthat )]TJ/F34 7.9701 Tf 8.08 -1.793 Td [(N isaregulargraph.Thisisaveryimportantpropertyof theSudokuGraphs{Understandingthereasonfortheregularityofthegraphsis integraltounderstandingthegraphsthemselves. Theorem 2.14 )]TJ/F34 7.9701 Tf 8.081 -1.793 Td [(N isregularwithvalency n )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 N Proof. Toseethis,wemustlookcloseratwhathappenswhenweperforman S -interchangetoan S -permutationmatrix P 2 N .An S -interchange,asdened above,isthereplacementofasubmatrix L 2 with I 2 orasubmatrix I 2 with L 2 that occursinthesameblockroworblockcolumnof P .Weconsider S -interchangesthat occurinthesameblockrowandthosethatoccurinthesameblockcolumnseparately intwocases: Thetwoonesinthesubmatrixoccurinblocksinthesameblockrow:Considerthepositionsofthetwo1'sinthelarge N N matrix,say i 1 ;j 1 and i 2 ;j 2 .Sincethe1'sareinthesameblockrow,therearenorestrictionsonthe j -coordinates,butthe i -coordinatesmustbeinthesame n -set f kn +1 ;:::;kn + n g for0 k n )]TJ/F25 11.9552 Tf 12.092 0 Td [(1.Withoutlossofgenerality,assume j 1 i 2 ,the submatrixformedis I 2 andotherwiseitis L 2 .Notethat,ineithercase,there isonlyonesubmatrixeither I 2 or L 2 thatcanbeformedwiththetwo1's. 13

PAGE 18

Thetwoonesinthesubmatrixoccurinblocksinthesameblockcolumn: Again,let i 1 ;j 1 and i 2 ;j 2 bethepositionsofthetwo1'sinthelarge N N matrix.Here, i 1 and i 2 areanytwodistinctnumbersin f 1 ;:::;N g aslongastheyareindierentblocksetsandwithoutlossofgeneralitywe canassume i 1
PAGE 19

f ; 3 ; ; 5 ; ; 7 ; 6 ; 2 ; 4 ; 6 ; ; 8 ; ; 1 ; ; 4 ; 9 g f ; 3 ; ; 5 ; ; 7 ; ; 2 ; 5 ; 6 ; 6 ; 8 ; ; 1 ; ; 4 ; 9 g f ; 3 ; ; 4 ; ; 7 ; ; 2 ; ; 6 ; ; 8 ; ; 1 ; ; 5 ; 9 g f ; 3 ; ; 5 ; ; 7 ; ; 2 ; ; 4 ; ; 8 ; ; 1 ; ; 6 ; 9 g f ; 3 ; ; 6 ; ; 7 ; ; 2 ; ; 5 ; ; 8 ; ; 1 ; ; 4 ; 9 g f ; 3 ; ; 5 ; ; 7 ; ; 2 ; ; 6 ; ; 8 ; 7 ; 1 ; ; 4 8 ; 9 g f ; 3 ; ; 5 ; ; 7 ; ; 2 ; ; 6 ; ; 8 ; ; 1 ; 7 ; 4 9 ; 9 g f ; 3 ; ; 5 ; ; 7 ; ; 2 ; ; 6 ; ; 8 ; 9 ; 1 ; 8 ; 4 ; 9 g f ; 3 ; ; 5 ; ; 8 ; ; 2 ; ; 6 ; ; 7 ; ; 1 ; ; 4 ; 9 g f ; 3 ; ; 5 ; ; 9 ; ; 2 ; ; 6 ; ; 8 ; ; 1 ; ; 4 ; 7 g f ; 3 ; ; 5 ; ; 7 ; ; 2 ; ; 6 ; ; 9 ; ; 1 ; ; 4 ; 8 g 15

PAGE 20

CHAPTER3 AssociationSchemes Whilethetheoryofasociationschemeswasdevelopedforstatisticalexperiments, itisusedtodayinavarietyofmathematicaltopicsfromcodingtheorytogroup representations.Weareinterestedinitsapplicationtodistanceregulargraphs.There areafewdierentwaystocharacterizeassociationschemes,andwewillexplore variousequivalentdenitionswithmanyexamples.Notethatouruseofassociation schemerefersto symmetric associationschemesinallcases.Allofthematerialin thischapterthatisnotcitedtoelsewhereisfromBailey[ 1 ]. 1.ThePartitionDenitionofAssociationSchemes Consideraniteset.Weareinterestedinrelationsonthesetoforderedpairs = f ; : 2 ; 2 g Definition 3.1 An associationscheme with s classeson isapartitionof into associateclasses C 0 ; C 1 ;:::; C s withthefollowingproperties: C 0 = Diag = f !;! : 2 g C i issymmetric 8 i ,i.e.,if ; 2C i then ; 2C i 8 i;j;k 2f 0 ; 1 ;:::s g thereisapositiveinteger p k ij suchthat, 8 ; 2C k jf 2 : ; 2C i and ; 2C j gj = p k ij If ; 2C i thenwesay and are i-thassociates .Wewrite a i = p 0 ii andcall a i the valency ofthe i -thassociateclass.Notethat,bysymmetry, p k ij = p k ji .Itisuseful tointroduceanotationforthesetof i -thassociatesofanelement 2 .Wewrite C i = f 2 : ; 2C i g .Then,wecandenethevalencyofthe i -thassociate 16

PAGE 21

classinanotherway,since a i = jC i j foranychoiceof 2 .Wecanalsorewrite fromourdenition:If 2C k ,then jC i C j j = p k ij Example 3.2 Let j j = n ,let C 0 = Diag ,andlet C 1 = f ; 2 : 6 = g = nC 0 Thisisthetrivialassociationscheme.Itistheonlyassociationschemewithjustone associateclass.Here, a 0 =1 asalways, a 1 = n )]TJ/F25 11.9552 Tf 12.328 0 Td [(1 ,and p 1 11 = n )]TJ/F25 11.9552 Tf 12.328 0 Td [(2 .Theother numbersarenotveryinterestingsincehavinga0inthesubscriptof p k ij limitsthe intersectioninthedenitiontoanintersectionwith1element.Infact, p 0 10 =0 and p 1 10 =1 Lemma 3.3 P s i =0 a i = j j foreveryiandk, P j p k ij = a i Proof. Let 2 ,thenallassociatesof partitiontheset,i.e.,is thedisjointunionof C 0 ; C 1 ;:::; C s and jC i j = a i andtheresults follows. Forany ; 2C k ,wecanwritetheset C i asthedisjointunionof C i C j for j =0 ; 1 ;:::;s sinceispartitionedbythe C j 's.As statedabove,thesizeofthatintersectionis p k ij Example 3.4 Let bethesetofverticesofthePetersengraphshownbelow. Let C 1 bethesetofedgesinthegraph,andlet C 2 bethesetofnon-edgesi.e.,theset ofpairsofverticesnotconnectedbyandedge. Wehave a 0 =1 ,asalways.Everyvertexisconnectedtoexactlythreeothers,so a 1 =3 .Thisleaves a 2 =10 )]TJ/F25 11.9552 Tf 12.66 0 Td [(1 )]TJ/F25 11.9552 Tf 12.66 0 Td [(3=6 .Thuswecanstarttoformtables,one describing p 1 ij andonefor p 2 ij withrowsandcolumnssummingto1,3,and6inthat order.Westartwith p 1 ij .If ; isanedgei.e., ; 2C 1 ,then: 17

PAGE 22

Figure1. ThePetersenGraph[ 10 ] p 1 ij C 0 C 1 C 2 Sum C 0 0 1 0 1 C 1 1 0 2 3 C 2 0 2 4 6 Sum 1 3 6 10 Thistablewaseasytoconstruct:therowstartingwith C 0 andthecolumnstarting with C 0 areeasytosee,andsincetherearenotrianglesinthePetersengraph, p 1 11 =0 .Therestfollowsbysubtraction.Similarly,if ; isnotanedge,i.e., ; 2C 2 ,wecanconstructthefollowingtablefor p 2 ij : p 2 ij C 0 C 1 C 2 Sum C 0 0 0 1 1 C 1 0 1 2 3 C 2 1 2 3 6 Sum 1 3 6 10 Again,heretherstrowandcolumnareobvious,soweonlyneedtocalculate p 2 11 and thenwecanusesubtractiontollinthetable.Weobservethateachpairofvertices notconnectedbyanedgehasexactlyonevertexthatbothareconnectedto,andhence p 2 11 =1 andourtablefollows.Wehavejustformedanassociationschemewithtwo classesonthePetersengraph. Fromthisexamplewecanseethatgraphscanmotivateanotherwayofconsidering associationschemes.Recallthata complete graphisagraphwhereeverypairof 18

PAGE 23

verticesisjoinedbyanedge.Ifweweretodrawinthenon-edgesofthePetersen graphwithadierentcolororifyouthinkofthemalreadydrawninwhitethenwe canthinkoftheassociationschemeasa2-coloringofthecompletegraphwithten vertices, K 10 .Wepresentthegraphcoloringdenitionofanassociationscheme,but wewillgonofurther,soasnottoconfusethereaderwhenwedescribeassociation schemesondistanceregulargraphsinadierentwayfurtherinthechapter. Definition 3.5 An associationscheme with s classesonaset isacoloring oftheedgesofthecompletegraphwithvertexset with s colorssuchthat everycolorisusedatleastonce 8 i 2f 1 ;:::;s g ; 9 a i 2 N suchthateachvertexinthegraphiscontainedin exactly a i edgesofcolor i 8 i;j;k 2f 1 ;:::;s g thereisaninteger p k ij suchthat,whenever f ; g isan edgeofcolor k then jf 2 : f ; g hascoloriand f ; g hascolorj gj = p k ij Thisdenitiontellsusthat,if f ; g isa k -colorededge,wehaveaxednumber, p k ij ,oftrianglesinthegraphwithan i -colorededgefrom anda j -colorededgefrom totheremainingvertexinthetriangle.Thisisindependentofourchoiceof and 2.TheMatrixDenitionofAssociationSchemes Topresentthematrixdenitionofassociationscheme,wemustdevelopamore generalnotionofamatrix.Insteadofindexingtherowsandcolumnsofthematrix withnaturalnumbersasiscommonlypracticed,wecanmoregenerallyindexthe arraywithnitesets.Inthisway,ourcommonnotionofan m n matrixcanbe thoughtofasamatrixonthesets)-331(= f 1 ;:::;m g and= f 1 ;:::;n g .Sincethese setshaveanorder,theusualmatrixconventionisthatwedonotlabelrowsand 19

PAGE 24

columnsbutordermatters.Wewillconsidermatricesintheoppositeway{Thesets weusemaynothaveanaturalordering,solabelingisimportant.Thus,amatrixin F )]TJ/F37 7.9701 Tf 5.288 0 Td [( isamatrixwithrowsindexedbytheelementsof,columnsindexedbythe elementsof,andwhoseentriesareelementsof F Definition 3.6 An associationscheme with s associateclassesonaset is asetofmatrices A 0 ;A 1 ;:::;A s 2f 0 ; 1 g suchthat A 0 = I A i issymmetricfor 1 i s 8 i;j 2f 1 ;:::;s g theproduct A i A j isalinearcombinationof A 0 ;A 1 ;:::;A s Weholdoonmorediscussionofthematrixdenitionofassociationschemeuntil ourdiscussionofdistanceregulargraphsinthenextsection.There,wewillfocuson somepropertiesoftheadjancencymatricesonthedistances. 3.Distance-regulargraphs Recallthatagraphis connected ifeverypairofverticeshasapathofedges betweenthem,andthat,inaconnectedgraph,the distance betweentwoverticesis thelengthoftheshortestpathfromonetotheother.The diameter ofthegraphis themaximumdistancebetweenanypairofvertices. Inaconnectedgraph G withvertexset,wecandenesubsetsondistanceby G i = f ; 2 :thedistancebetween and is i g G i = f 2 :thedistancebetween and is i g Definition 3.7 Let G beaconnectedgraphwithdiameter s andvertexset G is distanceregular if G 0 ; G 1 ;:::; G s formanassociationschemeon 20

PAGE 25

Thus,inanydistanceregulargraph G ,thereareintegers a i suchthat jG i j = a i 8 2 .Wealsohavethat,if 2G i then G 1 G i )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 [G i [G i +1 Inwords,thismeansthatif isdistance i from ,thenallelementsdistance1from willbeeitherdistance i )]TJ/F25 11.9552 Tf 10.414 0 Td [(1, i ,or i +1from .Itmakessense,then,tolet b i = p i i )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 ; 1 and c i = p i i +1 ; 1 .Infact,ifthesenumbersareconstantthroughoutthevertexset,then G willbedistanceregular.Theproofofthismakesuseofthe adjacencymatrices of thedistanceassociateclasses G i Theorem 3.8 Let bethevertexsetofaconnectedgraph G withdiameter s .If thereexistintegers a i ;b i ;c i for 1 i s suchthat, 8 2 and 8 i 2f 1 ;:::;s g jG i j = a i if 2G i then jG i )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 G 1 j = b i and jG i +1 G 1 j = c i then G isdistanceregular. Definition 3.9 Foragraph G withvertexset ,wedenethe adjacency matrix A i 2f 0 ; 1 g oftheclass G i asthebinarymatrixwiththeentry ; = 8 < : 1 if and aredistanceiapart 0 else Theadjacencymatricesofadistanceregulargraphhavesomeniceproperties. Theyarelistedinthefollowinglemma,fromGodsil[ 6 ]: Lemma 3.10 Let A 0 ;:::;A s bethedistanceadjancencymatricesofadistance regulargraph G withdiameter s .Then,thefollowingpropertieshold: A 0 = I P s i =0 A i = J A i issymmetrici.e., A i = A T i for 0 i s A i A j isalinearcombinationof A 0 ;:::;A s forall i and j 21

PAGE 26

A i A j = A j A i forall i and j A i isapolynomialofdegree i in A 1 foralli 4.CharacterizationsofAssociationSchemesontheCube Thecubeisagoodexampletodemonstrateacoupleofthevariousdenitionsof associationscheme.Letbethesetofthe8verticesofthecube.Werstconsider thecubeasanassociationschemebylabelingtheverticeswithacorrespondingthreedigitbinarynotationthatdirectlyrelatestotheunitcube'sCartesiancoordinates. Thisformsanassociationschemecalledthe HammingScheme ,withthefollowing denitionfromBannaiandIto[ 3 ]: Definition 3.11 LetFbeasetwithcardinality q 2 and X = F n betheset ofvectorsoflength n withentriesfromF.For x;y 2 X with x = x 1 ;:::;x n and y = y 1 ;:::;y n ,denethe Hammingdistance tobe @ x;y =# f i : x i 6 = y i g Dene C i = f x;y 2 X X : @ x;y = i g .Thentheseclassesformanassociation schemecalledthe HammingScheme anddenotedby H n;q 101 111 011 001 100 110 010 000 Figure2. Thecubewithbinaryvertices Thus,thecubeisanexampleofaHammingSchemewith F = f 0 ; 1 g and n =3, or H ; 2.Anelement 2 thenwillhaveone0-thassociateitself, )]TJ/F31 7.9701 Tf 5.479 -4.379 Td [(3 1 =3rst associates, )]TJ/F31 7.9701 Tf 5.48 -4.379 Td [(3 2 =3secondassociates,andexactlyonethirdassociate. 22

PAGE 27

Figure3. ColoredAssociationSchemeontheCube,adaptedfrom Bailey[ 1 ] Wecanalsoformanassociationschemebycoloringthecube.Considercoloring theedgesofthecubeyellow,thediagonalsthroughthecubered,thefacediagonals blue,andtheeightverticesgreen.Eachvertexwillthenbecontainedinthreeyellow egdes,threeblueedges,andonerededge,andhence a g =1, a y =3, a b =3,and a r =1.Notethatthesesumto j j =8,asrequired.Foreachcolor c 2f y;b;r g we canformatableforthevaluesof p c ij : p y ij g y b r g 0 1 0 0 y 1 0 2 0 b 0 2 0 1 r 0 0 1 0 p b ij g y b r g 0 0 1 0 y 0 2 0 1 b 1 0 2 0 r 0 1 0 0 p r ij g y b r g 0 0 0 1 y 0 0 3 0 b 0 3 0 0 r 1 0 0 0 Wecanverifytheseresultseasilybyconstructingacoloredrepresentationofthis associationschemeSeeFigure3. Thelastwaytoconsiderforminganassociationschemeonthecubeisthrough distances.UsingFigure2,weseethatthebothourchoiceofcoloringandthebinary notationcorresponddirectlytodistances.Inparticular,if and areconnectedby ayellowcubeedge,theyaredistance1fomeachother.Thebluefacediagonalsare 23

PAGE 28

distance2,whiletheredcubediagonalsaredistance3.Thus,weobtainthesame associationschemeagainbyconsideringdistancesinthegraphofthecube. 24

PAGE 29

CHAPTER4 The n =2 Case Westartwiththesimplestnontrivialcase, N =4 n =2.Wewishtounderstand thegraph )]TJ/F31 7.9701 Tf 8.08 -1.793 Td [(4 ,nditsdiameter,and,ifpossible,ndanassociationschemeonits distancestoproveitisdistanceregular.ByProposition2.4,wendthenumberof S -permutationmatricesofthisordertobe j 4 j =2! 2 =2 4 =16 Example 4.1 Whilewealreadyknowthat 4 has16elements,itisusefulto verifythealternativenotationbycountingandcheckingthatourresultisthesame. Any S -permutationmatrixin 4 canbewrittenasfourorderedpairsdescribingthe positionsofthefour1's.Therstpair, i 1 ;j 1 hastobeintherstblock,sothere aretwochoicesfor i 1 andtwofor j 1 .Movingtothesecondblock, i 2 isxedbyour choicefor i 1 andwehavetwochoicesfor j 2 .Inthethirdblock,wehavetwochoices for i 3 while j 3 isxedby j 1 .Lastly, i 4 isxedby i 3 and j 4 isxedby j 2 .Thuswe veryourformulaforthiscase,obtaining 2 4 =16 distinct S -permutationmatrices. Sincethevertexsetissmallenough,wecanlistitselements.Welabelthemwith theforesightofusingthebinaryrepresentationoftheirplaceonthehypercube,for purposesthatwillbeevidentlater: 2 6 6 4 10 00 00 10 01 00 00 01 3 7 7 5 1100 2 6 6 4 10 00 00 10 00 01 01 00 3 7 7 5 1000 2 6 6 4 10 00 00 01 01 00 00 10 3 7 7 5 1101 2 6 6 4 10 00 00 01 00 10 01 00 3 7 7 5 1001 25

PAGE 30

2 6 6 4 01 00 00 10 10 00 00 01 3 7 7 5 0100 2 6 6 4 01 00 00 01 10 00 00 10 3 7 7 5 0101 2 6 6 4 01 00 00 10 00 01 10 00 3 7 7 5 0000 2 6 6 4 01 00 00 01 00 10 10 00 3 7 7 5 0001 2 6 6 4 00 10 10 00 01 00 00 01 3 7 7 5 1110 2 6 6 4 00 10 10 00 00 01 01 00 3 7 7 5 1010 2 6 6 4 00 01 10 00 01 00 00 10 3 7 7 5 1111 2 6 6 4 00 01 10 00 00 10 01 00 3 7 7 5 1011 2 6 6 4 00 10 01 00 10 00 00 01 3 7 7 5 0110 2 6 6 4 00 10 01 00 00 01 10 00 3 7 7 5 0010 2 6 6 4 00 01 01 00 10 00 00 10 3 7 7 5 0111 2 6 6 4 00 01 01 00 00 10 10 00 3 7 7 5 0011 Thesmallsizeofthiscaseallowedforabruteforce"methodinconstructing )]TJ/F31 7.9701 Tf 8.081 -1.794 Td [(4 .Giventwoblocksor,equivalently,giventhepositionoftwo1'sinthesame blockroworcolumn,thereisexactlyonewaytoformasubmatrixthatis I 2 or L 2 Hence,everyblockcanperformexactlyone S -interchangewitheveryblockinits blockrowandblockcolumn.In 4 ,wehavefourblocks,eachwithoneotherblock initsrowandoneinitscolumn.Countingallofthesedoublecountsthenumberof S -interchangeswecanperformonagivenelement A 2 4 sincethereisoneunique S -interchangethatcantakeplacebetweentwoblocks.Wethereforeenumeratethe numberof S -interchangesby = 2 4 2=4.Thiscoincideswithwhatwewould expectthevalencytobefromTheorem2.14. Aftersomeworkbyhand,wefoundthatthegraphproducedistheHypercube Graph, Q 4 .Wearenowconcernedwithdistancesinthisgraphandndingitsdiameter.Wewillthenshowittobedistanceregularbyforminganassociationscheme onitsdistances.Thisgraphhasatwo-dimensionaldepictionaspicturedingure 26

PAGE 31

1,butfordistancepurposes,itismoreusefultoviewitasverticesandedgesona hypercube. Figure1. Q 4 {TheHypercubeGraph[ 9 ] FromTheorem2.9,weknowourlowerboundforourdiameteris2whileourupper boundis4: LB = = 2 n 2 = = 2 4=2 UB =2 n n )]TJ/F25 11.9552 Tf 11.956 0 Td [(1=2 2=4 : Calculatingdistancesinthehypercube,however,isfairlysimple,especiallywith thebinarynotationonthevertices.Notethatthedistancebetweentwoverticesin thehypercubecorrespondsdirectlytohowmanyofthefournumbersinthebinary notationaredierent.Two4-digitnumberscandierinarangefrom0to4positions. Thus,twoverticescanhaveadistanceof0to4,andweobtainthediameterof )]TJ/F31 7.9701 Tf 8.08 -1.793 Td [(4 to be4.Wenowcountthenumberofelementsateachdistancefromanygivenvertex. Whilewehavealreadydonethisfordistance1usuingtheblockmatrixnotation,we recountallusingthebinaryhypercubelabeling.Consideravertex v = v 1 v 2 v 3 v 4 with v i 2f 0 ; 1 g for1 i 4.Distance0correspondstoall v i 'sbeingxed,soeach elementisdistance0fromitself,and a 0 =1.Wehavefourchoicestochangeone elementof v ,so a 1 =4.Fordistancetwo,weneedtopicktwoofthefourelements 27

PAGE 32

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1101 1100 1010 1110 1011 1111 Figure2. Hypercubewithbinaryvertices[ 7 ] tochange,andhence a 2 = )]TJ/F31 7.9701 Tf 5.48 -4.378 Td [(4 2 =6.Indistance3,oneelementstaysxed,giving a 3 =4.Lastly,thereisonlyoneelementdistance4awayfrom v a 4 =1. WehavejustdescribedtheHammingScheme H ; 2asdenedinDenition3.11. Thedeningassociationschemenumbers a i b i ,and c i aresummarizedinthe followingtable: i a i b i c i 0 1 0 4 1 4 1 3 2 6 2 2 3 4 3 1 4 1 4 0 28

PAGE 33

Table1. TheAssociationSchemeon )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(4 p 1 ij 0 1 2 3 4 Sum 0 0 1 0 0 0 1 1 1 0 3 0 0 4 2 0 3 0 3 0 6 3 0 0 3 0 1 4 4 0 0 0 1 0 1 Sum 1 4 6 4 1 16 p 2 ij 0 1 2 3 4 Sum 0 0 0 1 0 0 1 1 0 2 0 2 0 4 2 1 0 4 0 1 6 3 0 2 0 2 0 4 4 0 0 1 0 0 1 Sum 1 4 6 4 1 16 p 3 ij 0 1 2 3 4 Sum 0 0 0 0 1 0 1 1 0 0 3 0 1 4 2 0 3 0 3 0 6 3 1 0 3 0 0 4 4 0 1 0 0 0 1 Sum 1 4 6 4 1 16 p 4 ij 0 1 2 3 4 Sum 0 0 0 0 0 1 1 1 0 0 0 4 0 4 2 0 0 6 0 0 6 3 0 4 0 0 0 4 4 1 0 0 0 0 1 Sum 1 4 6 4 1 16 Wecandepicttheassociationschemeforthehypercubewithacoloringchart. Hereeachcolorrepresentsadierentdistance,withthefollowingassociation: Distance Color 0 yellow 1 red 2 purple 3 green 4 blue 29

PAGE 34

Figure3. ColoredAssociationSchemeonDistancesintheHypercube 30

PAGE 35

CHAPTER5 The n =3 Case 1.Propertiesof)]TJ/F31 7.9701 Tf 106.357 -1.793 Td [(9 Wenowtheconsiderthecaseofthenormal"sudokupuzzlewith N =9 n =3. ByProposition2.4,weknowthenumberof S -permutationmatricesofthissizetobe j 9 j = n 2 n =6 6 =46 ; 656 : Thus,thiscaseisalmost3000timeslargerthanthepreviousoneandthesame methodsemployedtounderstand )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(4 wouldbeimpossible. Example 5.1 Wecanexplicitlycountthe 6 6 S -permutationmatricestofurther understandthestructureof 9 .Sinceeveryrownumberappearsexactlyonce,we cancounttheplacementofthenine1'sbychoosingthecolumnpositionofeachrow. Thereareninechoicesforthecolumnofthe1intherstrow.Inthesecondrow, wehavetoavoidtheblockweplacedtherst1in,sowehavesixchoicesforthe column.Inthethirdrow,wehaveoneblockleft,andhencetherearethreechoicesfor wheretoplacethethird1.Sofar,then,wehave 9 6 3 waystopickthepositionsof the1'sintherstblockrow.Inthefourthrow,wecanpickanyofthethreeblocks toplacethe1butwedoneedtoavoidthecolumnswehavealreadychosen,sowe havesixchoices.Inthefthrow,wehavetwoblockstochoosefromwitheachblock havingonecolumnalreadyused,sowehavefourchoices.Inthesixthrow,wehave twochoices.Intheseventhrow,wecanpickoneofthethreeblocks,butwithonly onefreeremainingcolumnineachblock,wehavethreechoices,andthentwoforthe eighth1.Oncewehavepickedthersteight1's,thereisonlyoneremainingchoice 31

PAGE 36

fortheninthrow.Thus,wecancountthenumberof S -permutationmatricesin 9 tobe 9 6 3 6 4 2 3 2 1=6 6 FromTheorem2.14,weexpectthegraphtoberegularwithvalency18,butwe cancountthisaswell.Everyblockhastwootherblocksinbothitsblockrowand blockcolumn,soevery1can S -interchangewithfourother1'sinexactlyoneway. Thisdoublecounts,soweendupwith = 2 9 2 2=18 S -interchangespossiblefor agivenvertex v 2 )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 Considertwo S -permutationmatrices A;B 2 9 .Wewishtondaformula forthedistancebetween A and B ,i.e.,theleastnumberof S -interchangesthatcan transform A into B .Let A = f i k ;j k g 9 k =1 and B = f i 0 k ;j 0 k g 9 k =1 inorderedBCNas describedinChapter2. S -interchangesoccurinonlyoneblockroworblockcolumn anddonotaectthepositionsofthe1'sinanyotherblockrow/column,sowecan countthe S -interchangesneededtochange A into B ifwecounttheleastnumberof S -interchangesneededtoxthedierencesineachblockrowandblockcolumnof A and B seperatelyinthefollowingmethod: First,itishelpfultowriteoutthelistofthepositionsofthe1'sin A and B ontop ofoneanother,sincetheyareordered,toassistincorrectlyidentifyingdierences: A = f i 1 ;j 1 ; i 2 ;j 2 ; i 3 ;j 3 ; i 4 ;j 4 ; i 5 ;j 5 ; i 6 ;j 6 ; i 7 ;j 7 ; i 8 ;j 8 ; i 9 ;j 9 g B = f i 0 1 ;j 0 1 ; i 0 2 ;j 0 2 ; i 0 3 ;j 0 3 ; i 0 4 ;j 0 4 ; i 0 5 ;j 0 5 ; i 0 6 ;j 0 6 ; i 0 7 ;j 0 7 ; i 0 8 ;j 0 8 ; i 0 9 ;j 0 9 g Whenweperforman S -interchangeinablockrow,theresultwillbeatransposition ofthe i coordinatesinthepositionsofthe1'sinthetwoaectedblocks.Sincerow S -interchangescanonlyoccurwhenthetwoaected1'sareinthesameblockrow, the i coordinatesthatareallowedtobeswitchedcanbegroupedintothreedistinct 3-sets: f i 1 ;i 2 ;i 3 g ; f i 4 ;i 5 ;i 6 g ; and f i 7 ;i 8 ;i 9 g .Similarly,whenan S -interchangeoccurs betweentwoblocksinthesameblockcolumn,theendresultisatranspositionofthe j coordinatesofthe1'sinthetwoaectedblocks.Sinceeach1canonly S -interchange 32

PAGE 37

witha1inablockinitssameblockcolumn,theonly j coordinatesthatcanbe swappedwitheachothercanbegrouped,likebefore,intothreedierent3-sets: f j 1 ;j 4 ;j 7 g ; f j 2 ;j 5 ;j 8 g ; and f j 3 ;j 6 ;j 9 g .Insummary, everysingle S -interchange wecanperformon A willtransposetwoelementsinoneofthesix3-sets wehavelisted Thus,tocountthedistancebetween A and B ,wecanlookatthenumberof S interchangesthatxeachofthesix3-setsseparatelyandsumthemtogetourtotal distance.Considercomparingoneofthesix3-setslistedabovebyplacingthethree numbersforthetwomatricesintwo3-tuplesinorderofascendingblocknumber, say a 1 ;a 2 ;a 3 and b 1 ;b 2 ;b 3 .Wecompare a 1 with b 1 a 2 with b 2 ,and a 3 with b 3 i.e.,wecomparethe i or j positionsofthe1'sinaspecicblockroworcolumn, startingwiththerstblockintheroworcolumnrst.Iftherearenodierences i.e., a i = b i forall i ,1 i 3,thenobviouslyno S -interchangesareneeded.If therearedierencesbetweenthetuples,though,therearethreecasestoconsider, whichwedointhefollowinglemma: Lemma 5.2 Considercomparingthepositionsofthree1'sinthesameblockrowor columnintwo S -permutationmatrices A and B .Letthesepositionsberepresentedby theordered3-tuples a 1 ;a 2 ;a 3 and b 1 ;b 2 ;b 3 asdescribedabove.Whenwecompare component-wise,therearethreecases: Thesituationinwhichthereisonlyonedierencebetweenthe3-tuplesi.e., a i 6 = b i forexactlyone i isnotpossible. Iftherearetwodierencesi.e., a i = b i forexactlyone i ,thenone S interchangeisneeded. Iftherearethreedierencesi.e., a i 6 = b i for 1 i 3 ,thentwo S interchangesareneeded. Proof. Thisisanimpossiblesituationbecauseiftheothertwocoordinatesinthe3-tupleagree,therewillbeonlyoneremainingchoiceofrowfor 33

PAGE 38

thelastrowcoordinateineach3-tuplefor A and B tobevalid S -permutation matrices,andthelastcoordinatewillthushavetoagreeaswell.Itisgood thatthisisanimpossiblesituation{ S -interchangestranspose2coordinates, sowewouldnotbeabletoxjustonethatwasincorrect. AsdescribedinChapter2,an S -interchangeonthetwoswappednumbers inBCNissimplyatransposition. Wecanconsiderthechangesweneedtomakeonthethreenumberstobea 3-cycle.Any3-cyclecanbewrittenasaproductoftwotranspositions,soto correctallthreenumbers,weneedtwo S -interchanges.Thereisnotaunique waytodothis,butallwayswilltake2 S -interchangesatleast.Wecanstart withany S -interchange.Thiswillxoneelementandpositiontheotheras in. Fromtheabove,wedevelopaformulaforthedistancebetweentwo S -permutation matrices. Proposition 5.3 Let i bethenumberof S -interchangesnecessarytoturnthe i -th3-setof A intothe i -th3-setof B 1 i 6 .Then dist A;B = 6 X i =1 i Proof. FromLemma5.2,weknowhowtocountthenumberof S -interchanges tocorrectaspecic3-set.Sincetheelementsofeachofthesix3-setscanonly S -interchangewithanotherelementofthesameset,theresultfollows. Example 5.4 Considertwo S -permutationmatricesin 9 : A = f ; 3 ; ; 5 ; ; 7 ; ; 1 ; ; 6 ; ; 8 ; ; 2 ; ; 4 ; ; 9 g B = f ; 3 ; ; 6 ; ; 7 ; ; 2 ; ; 5 ; ; 8 ; ; 1 ; ; 4 ; ; 9 g 34

PAGE 39

Usingthemethoddescribedabove,wecountthe S -interchangesneededtocorrecteach ofthesix3-setsrepresentingtheblockrowsandcolumns: For f i 1 ;i 2 ;i 3 g ,wehave,inorder, ; 1 ; 3 7! ; 2 ; 1 whichcanbeaccomplishedbythecycle .Inthematrixnotationoftherstblockrowof A and B shownbelow,noticethatwehavetomovethe1intherstblock inrow2torow3,thesecond1downfromtherstrowtothesecondrow, andthethirdoneinthethirdrowtotherstrow.Fromtheabove,weneed two S -interchangestoxthis,butwhichtranspositionwestartwithdoesnot matter.Wecouldstartwiththe S -interchangethattransposestherowsof the1'sinthersttwoblocks,whichwouldcorrectposition i 2 toitscorrect placein B row2.Thenweneedtotransposetherowoftherstandthird block,andwehavecorrectedtherowpositionsoftherstblockrowintwo transpositions,asexpected. 2 4 000 010 000 001 000 000 000 000 100 3 5 2 4 000 000 100 000 010 000 001 000 000 3 5 Weconsidertherstblockcolumnnext,i.e.,the3-set f j 1 ;j 4 ;j 7 g .Here,the1 intherstblockinthecorrectcolumn,butthecolumnpositionsofthe1's inthefourthandseventhblocksneedtobeswtiched.Thisisthepermutation mappedby ; 1 ; 2 7! ; 2 ; 1 .One S -interchangecanxthis: 2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 001 100 000 000 000 010 000 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 001 010 000 000 000 100 000 3 7 7 7 7 7 7 7 7 7 7 7 5 Weconsiderthelasttwoblockrowsandlasttwoblockcolumnsinlessdetail. Thesecondblockrowisalreadycorrect: ; 5 ; 6 7! ; 5 ; 6 .Thesecondblock 35

PAGE 40

columni.e.,thecoordinates f j 2 ;j 5 ;j 8 g requiresthepermutation ; 6 ; 4 7! ; 5 ; 4 ,sothe S -interchangebetweenthe1'sinblocks2and7willxthis set.Thelastblockrowissimilartotherst: ; 9 ; 7 7! ; 7 ; 8 corresponds tothe3-cycle sotwotranspositionswillcorrectthis.Lastly,thethird blockcolumnisalreadycorrect. Weaddupthe S -interchangesdonetotransform A into B :2intherst blockrowandthirdblockrow,1intherstblockcolumnandsecondblock column,and0inthesecondblockrowandthirdblockcolumn.Weexpectthe distancebetween A and B ,then,tobe 2 2+2 1+2 0=6 Weconcludetheexamplebyshowingonepathoflength6from A to B {Theorder inwhichweperform S -interchangesindoesnotmatterandwehavethreewaysto correcteachblockrow/columnthatrequirestwo S -interchangeswecanstartwithany ofthethree S -interchanges,butourchoicexesthesecondoneweneedtoperform, sotherearemanypathstochoosefrom. A = 2 6 6 6 6 6 6 6 6 6 6 6 4 000 0 1 0 000 00 1 000 000 000 000 100 100 000 000 000 000 010 000 001 000 000 000 001 010 000 000 000 100 000 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 00 1 000 000 000 010 000 000 000 1 00 100 000 000 000 000 010 000 001 000 000 000 001 010 000 000 000 100 000 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 100 000 010 000 001 000 000 1 00 000 000 000 000 010 000 001 000 000 000 001 0 1 0 000 000 000 100 000 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 100 000 0 1 0 000 001 000 000 010 000 000 000 000 010 000 00 1 000 000 000 001 100 000 000 000 100 000 3 7 7 7 7 7 7 7 7 7 7 7 5 36

PAGE 41

2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 100 000 001 000 001 000 000 010 000 000 000 000 010 000 010 000 000 000 001 1 00 000 000 000 1 00 000 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 100 000 001 000 001 000 000 010 000 000 000 000 010 000 010 000 000 000 00 1 000 1 00 000 100 000 000 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 100 000 001 000 001 000 000 010 000 000 000 000 010 000 010 000 000 100 000 000 000 001 100 000 000 3 7 7 7 7 7 7 7 7 7 7 7 5 = B InBCN,thepathis: A = f 2 ; 3 ; 1 ; 5 ; ; 7 ; ; 1 ; ; 6 ; ; 8 ; ; 2 ; ; 4 ; ; 9 g f 1 ; 3 ; ; 5 ; 3 ; 7 ; ; 1 ; ; 6 ; ; 8 ; ; 2 ; ; 4 ; ; 9 g f ; 3 ; ; 5 ; ; 7 ; ; 1 ; ; 6 ; ; 8 ; ; 2 ; ; 4 ; ; 9 g f ; 3 ; ; 5 ; ; 7 ; ; 2 ; ; 6 ; ; 8 ; ; 1 ; ; 4 ; ; 9 g f ; 3 ; ; 6 ; ; 7 ; ; 2 ; ; 5 ; ; 8 ; 8 ; 1 ; 9 ; 4 ; ; 9 g f ; 3 ; ; 6 ; ; 7 ; ; 2 ; ; 5 ; ; 8 ; ; 1 ; 8 ; 4 ; 7 ; 9 g f ; 3 ; ; 6 ; ; 7 ; ; 2 ; ; 5 ; ; 8 ; ; 1 ; ; 4 ; ; 9 g = B Fromequation2,weexpectthediameterof )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 tobe P 6 i =1 2=12.FromTheorem 2.9,weknowthistobetheupperboundonthediameterof )]TJ/F31 7.9701 Tf 8.08 -1.794 Td [(9 .Weneedtoshowthat therecannotbeashorterpathbetweentwocompletelydistinctmatrices,andwewill knowthediameterof )]TJ/F31 7.9701 Tf 8.08 -1.794 Td [(9 tobe12. Theorem 5.5 Thediameterof )]TJ/F31 7.9701 Tf 8.08 -1.794 Td [(9 is12. Proof. Considertwoorderedverticesin )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 A = f i k ;j k g 9 k =1 and B = f i 0 k ;j 0 k g 9 k =1 with i 0 k 6 = i k and j 0 k 6 = j k 8 k .Recallthatwecanconsideran S -interchangeon A as 37

PAGE 42

atranspositionoftwoelementsinoneofthefollowing3-sets: f i 1 ;i 2 ;i 3 g ; f i 4 ;i 5 ;i 6 g ; f i 7 ;i 8 ;i 9 g ; f j 1 ;j 4 ;j 7 g ; f j 2 ;j 5 ;j 8 g ; f j 3 ;j 6 ;j 9 g Weknowthatwecantransform A into B withaseriesof12 S -interchanges,as describedinProposition5.3,withtwotranspositionsineach3-set.Supposeforcontradictionthatthereisawaytotransform A into B usinglessthan12 S -interchanges. Thenonesetwouldhavelessthantwotranspositionsperformedonit.Morespecically,atleastoneelementwouldremainxed.But B diersfrom A ineverysingle i and j coordinate,andthusaseriesoflessthan12 S -interchangescannottransform A into B Example 5.6 Weshowapathoflength12in )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 betweentwovertices A and B thatdierinevery i and j coordinateasintheproofoftheprevioustheorem.To illustratethattheorderinwhichweperform S -interchangesdoesnotmatter,wetake apathof S -interchangesinnoparticularorder.Let A = f ; 2 ; ; 6 ; ; 8 ; ; 3 ; ; 4 ; ; 7 ; ; 1 ; ; 5 ; ; 9 g and B = f ; 1 ; ; 4 ; ; 7 ; ; 2 ; ; 5 ; ; 9 ; ; 3 ; ; 6 ; ; 8 g : Werstpresentthepathinnumericnotationandtheninmatrixnotation.Inboth presentations,thenumbersinboldarethe1'sabouttobeinterchanged. A == f ; 2 ; ; 6 ; ; 8 ; ; 3 ; ; 4 ; ; 7 ; ; 1 ; ; 5 ; ; 9 g = f ; 2 ; ; 6 ; ; 8 ; ; 3 ; ; 5 ; ; 7 ; 8 ; 1 ; 9 ; 4 ; ; 9 g = f ; 2 ; 1 ; 6 ; 3 ; 8 ; ; 3 ; ; 5 ; ; 7 ; ; 1 ; ; 4 ; ; 9 g = f ; 2 ; ; 6 ; ; 8 ; 4 ; 3 ; ; 5 ; 5 ; 7 ; ; 1 ; ; 4 ; ; 9 g = f ; 2 ; ; 6 ; ; 8 ; 5 ; 3 ; 6 ; 5 ; ; 7 ; ; 1 ; ; 4 ; ; 9 g = f ; 2 ; ; 6 ; ; 8 ; ; 3 ; ; 5 ; ; 7 ; ; 1 ; ; 4 ; ; 9 g = f ; 2 ; ; 6 ; ; 7 ; ; 3 ; ; 5 ; ; 8 ; 9 ; 1 ; ; 4 ; 7 ; 9 g = f ; 2 ; ; 6 ; ; 7 ; ; 3 ; ; 5 ; ; 8 ; ; 1 ; ; 4 ; ; 9 g 38

PAGE 43

= f ; 3 ; ; 6 ; ; 7 ; ; 2 ; ; 5 ; ; 8 ; ; 1 ; ; 4 ; ; 9 g = f ; 3 ; ; 4 ; ; 7 ; ; 2 ; ; 5 ; ; 8 ; ; 1 ; ; 6 ; ; 9 g = f 2 ; 3 ; 3 ; 4 ; ; 7 ; ; 2 ; ; 5 ; ; 9 ; ; 1 ; ; 6 ; ; 8 g = f ; 3 ; ; 4 ; ; 7 ; ; 2 ; ; 5 ; ; 9 ; ; 1 ; ; 6 ; ; 8 g = f ; 1 ; ; 4 ; ; 7 ; ; 2 ; ; 5 ; ; 9 ; ; 3 ; ; 6 ; ; 8 g = B Inmatrixnotation: A = 2 6 6 6 6 6 6 6 6 6 6 6 4 000 001 000 010 000 000 000 000 010 001 000 000 000 000 100 000 1 00 000 000 000 001 100 000 000 000 0 1 0 000 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 001 000 010 000 000 000 000 010 001 000 000 000 000 100 000 010 000 000 000 001 1 00 000 000 000 1 00 000 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 00 1 000 010 000 000 000 000 0 1 0 001 000 000 000 000 100 000 010 000 000 000 001 000 100 000 100 000 000 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 010 010 000 000 000 001 000 00 1 000 000 000 000 1 00 000 010 000 000 000 001 000 100 000 100 000 000 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 010 010 000 000 000 001 000 000 000 100 00 1 000 000 000 0 1 0 000 000 000 001 000 100 000 100 000 000 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 0 1 0 010 000 000 000 001 000 000 000 1 00 000 010 000 001 000 000 000 000 001 000 100 000 100 000 000 3 7 7 7 7 7 7 7 7 7 7 7 5 39

PAGE 44

2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 100 010 000 000 000 001 000 000 000 010 000 010 000 001 000 000 000 000 00 1 000 100 000 1 00 000 000 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 100 0 1 0 000 000 000 001 000 000 000 010 000 010 000 00 1 000 000 100 000 000 000 100 000 000 000 001 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 100 001 000 000 000 00 1 000 000 000 010 000 010 000 010 000 000 100 000 000 000 1 00 000 000 000 001 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 100 001 000 000 000 100 000 000 000 0 1 0 000 010 000 010 000 000 100 000 000 000 001 000 000 000 00 1 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 100 00 1 000 000 000 1 00 000 000 000 001 000 010 000 010 000 000 100 000 000 000 001 000 000 000 010 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 100 000 100 000 00 1 000 000 000 000 001 000 010 000 010 000 000 1 00 000 000 000 001 000 000 000 010 3 7 7 7 7 7 7 7 7 7 7 7 5 2 6 6 6 6 6 6 6 6 6 6 6 4 000 000 100 000 100 000 100 000 000 000 000 001 000 010 000 010 000 000 001 000 000 000 001 000 000 000 010 3 7 7 7 7 7 7 7 7 7 7 7 5 = B Definition 5.7 Givenan S -permutationmatrix A = f i k ;j k g N k =1 a counterpart of A isamatrix B = f i 0 k ;j 0 k g N k =1 2 N suchthat i 0 k 6 = i k and j 0 k 6 = j k 8 k 40

PAGE 45

Lemma 5.8 Every S -permutationmatrixin 9 hasexactly64counterparts. Proof. Let A = f i k ;j k g 9 k =1 .Wewishtocountthenumberof S -permutation matrices B = f i 0 k ;j 0 k g 9 k =1 with i 0 k 6 = i k and j 0 k 6 = j k 8 k .Recallthatsincethe positionpairsareorderedbyblocksaspreviouslydescribed,anypositioncanonly changeintoadierentelementinits n -setwith n 1 = f 1 ; 2 ; 3 g n 2 = f 4 ; 5 ; 6 g ,and n 3 = f 7 ; 8 ; 9 g .Recallalsothat,withtheordering, f i 1 ;i 2 ;i 3 g = n 1 ; f i 4 ;i 5 ;i 6 g = n 2 and f i 7 ;i 8 ;i 9 g = n 3 ,while f j 1 ;j 4 ;j 7 g = n 1 ; f j 2 ;j 5 ;j 8 g = n 2 ,and f j 3 ;j 6 ;j 9 g = n 3 Wecanthereforecountthenumberof B 'swecanformquiteeasily:Eachtimewe pickanewelementofoneofthesets,wehave2choicesifweavoidthenumberin thesamepositionof A ,andthenonlyonechoicefortheremainingtwopositionsin theset.Thuswehave2 6 =64 S -permutationsthatwecanformfromanygiven S -permutationmatrixoforder9withevery1inadierentrowandcolumn. Corollary 5.9 jG 12 v j =64 8 v 2 )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 Example 5.10 Let A = f ; 1 ; ; 5 ; ; 9 ; ; 2 ; ; 6 ; ; 7 ; ; 3 ; ; 4 ; ; 8 g Weconstructamatrix B = f i k ;j k g 9 k =1 thatisacounterpartof A asfollows: Theorderinwhichwechoosetheelementsof B doesnotmatter.Toillustrate this,westartbypicking j 5 .Wehave2possiblechoices:4or5.Wepick5. Wecancontinuewiththecolumnpositionsfromthesamecolumnblock, j 2 and j 8 .Wehavetobeabitcareful{Ifweweretopick j 2 nextwithout considering j 8 ,wewouldseethatwecouldonlynotchoose5since5isin thatpositionin A andwealreadyhavepicked5forourchoiceof j 5 .Itmight seemasifwecouldchooseeither4or6,then,for j 2 ,butifpicked6,we wouldbeleftchoosing4for j 8 whichisthesamenumberinthatpositionof A .Wehavetopick j 2 =4 and j 8 =6 .Notethatoncewepickedoneoftwo choicesfor j 5 ,ourothertwochoiceswerexed. Theprocessisthesameforeverypositionsetlistedintheproofofthelemma. Orderdoesnotmatter{Wedonotevenneedtopickallelementsoftheset 41

PAGE 46

consecutivelyaswedidinand,butsinceonechoicexestheother two,itisgoodpractice. Theaboveprocessveriesthatwecannd64counterparts A .Onesuchmatrixwe couldndifwecontinuedasaboveis B = f ; 2 ; ; 4 ; ; 8 ; ; 3 ; ; 5 ; ; 9 ; ; 1 ; ; 6 ; ; 7 g : Itisobvioustoseenowthatthereisexactlyonematrix C thatisacounterpartof both A and B .Inthisexample, C = f ; 3 ; ; 6 ; ; 7 ; ; 1 ; ; 4 ; ; 8 ; ; 2 ; ; 5 ; ; 9 g : Theorem 5.11 Therearenotrianglesin )]TJ/F31 7.9701 Tf 8.08 -1.793 Td [(9 Proof. Supposeforcontradictionthatthereisatrianglein )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 ,i.e.,thatthere existsavertex v withtwoneighbors,say w and x ,withanedgebetweenthetwo.Let v = f v i k ;v j k g 9 k =1 betheBCNrepresentationofthe1'sin v .Asdescribedabove,an S -interchangeon v isatranspositionoftwoelementsinoneofthesix3-sets f v i 1 ;v i 2 ;v i 3 g ; f v i 4 ;v i 5 ;v i 6 g ; f v i 7 ;v i 8 ;v i 9 g ; f v j 1 ;v j 4 ;v j 7 g ; f v j 2 ;v j 5 ;v j 8 g ; f v j 3 ;v j 6 ;v j 9 g : Thus,since w and x arebothneighborsof v ,therearetwocases: The S -interchangesperformedon v toget w and x areindierent3-sets The S -interchangesperformedon v toget w and x areinthesame3-set If,then w and x dierinfourpositionsintwodierent3-sets,sinceeachdier inthetwotransposedpositionsfrom v .Theredoesnotexistan S -interchangethat willcorrectthisinonestep,so w and x cannotbeneighbors,andwemustbein case.Withoutlossofgenerality,assumethatthe S -interchangesthattransform v into w and x occurintherst3-set, f v i 1 ;v i 2 ;v i 3 g .An S -interchangeinthissetis justatranspositionoftwoelements,soforthissetthepossible S -interchangesare representedby v i 1 v i 2 v i 1 v i 3 ,and v i 2 v i 3 .Since w and x areconnected,oneof 42

PAGE 47

thesetranspositionswilltransformoneintotheother.Thus,transforming v into w into x involvesaseriesoftwotranspositionsona3-set,andtransforming x backinto v willalsobeatransposition.Buttheproductofanytwooftheabovetranspositions willbea3-cycleifthetranspositonsaredistinctortheidentityiftheyarethesame, notatranspositionasneeded.Thisisacontradictionandthereforetherecannotbe trianglesin )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 2.AnAssociationSchemeon)]TJ/F31 7.9701 Tf 186.333 -1.793 Td [(9 ? Asinthecasefor )]TJ/F31 7.9701 Tf 8.081 -1.794 Td [(4 ,wewishtoinvestigateifwecanformanassociationscheme onthedistancesin )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 toproveitisdistanceregular. )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 ismuchlargerandmore complicatedthanthehypercubegraph,andcountingthedistancesthe a i 'sisadifculttask,evenwiththedistanceformulaexplainedintheprevioussection.Finding the b i 'sand c i 'sasdenedinTheorem3.8isevenharder.Themagnitudeofthe taskrequiredtheaidofacomputerprogramtosortandcountthedistances.We usedourconceptoftranspositionsonmatricesinBCNtowriteaprograminPython tocountthenumberof S -permutationmatricesatalldistancesawayfromaninitial vertexasnoted,thesearethe a i 's,andtocaluculate b i and c i forarandomelement inthe i 'thclassoftheoriginalvertexforall i ,0 i 12.Theprogramtookan inputofany S -permutationmatrixoforderNandcountedthenumberofverticesat everydistanceawayfromthisvertexinthefollowingway: Westartwithaninitial S -permutationmatrix,say A ,andcomputeitsneighbors. Thisiseasytodoifweinput A asanorderedlistofthe1'sin A inthesamewaywe havebeenandutilizeafunctionthatgenerateswhichtranspositionstoperformon A Wecancollectthe18resultsina set ,amoduleinPythonforanunorderedcollection ofuniqueobjects.Sincesetscannothavemultiplecopiesofthesameelement,using setstocountallowsustonotworryaboutdoublecounting S -permutationmatrices. Weiterateusingawhileloop,ateachstepaddingthesetofobjectsobtainedfrom 43

PAGE 48

performingall S -interchangesontheprevioussetandkeepingonlythosethathave notbeenseenbefore.Thewhileloopterminateswhennonewelementsremain. Moreprecisely,theideaoftheprogramtocountthedistancescanbeexplained inanequation.Inthisdiscussion,weidentifyan S -permutationmatrixwithits correspondingvertexin )]TJ/F31 7.9701 Tf 8.08 -1.794 Td [(9 andusebothnotations.WeconsidersetsasPython doesi.e.,asetofuniqueelements{thisway,wedon'tneedtoworryabouthow manytimesanobjectappears,sowerenameourmathematicalsetstohighlightthe distinction.Let C i v bethesetof S -permutationmatricesdistance i fromavertex v with C 0 v = f v g thisislikeourdenitionof G i inChapter3,and S x = C 1 x tobethesetof18 S -permutationmatricesthatareone S -interchangeawayfroma vertex x .Thenthesetof S -permutationmatricesdistance i fromaninitialvertex v is C i v = [ x 2 C i )]TJ/F32 5.9776 Tf 5.756 0 Td [(1 v S x )]TJ/F34 7.9701 Tf 12.456 14.944 Td [(i )]TJ/F31 7.9701 Tf 6.587 0 Td [(1 [ j =0 C j v Afterthewhileloopterminates,wehavealistofasetoftupleswhose i thelement ispreciselythose S -permutationmatricesthatareadistance i awayfromtheinitial matrix.Wecollectedthenumberofelementsandrantheprogramformanydierent initial S -permutationmatricesfor n =3aboutahundredtimes.Thenumberswere consistentforallinitialmatrices,andarelistedinthetablebelow. a 0 a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10 a 11 a 12 Sum 1 18 147 720 2355 5418 8989 10836 9420 5760 2352 576 64 46656 Notethatourprogramveriedthat )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 is18-regularofdiameter12with jG 12 v j = 64andthat j 9 j =46 ; 656. Nowthatwehavealistoftheobjectsatvariousdistancesfromourinitialvertex, itiseasytowriteaprogramthatndsthe b i 'sand c i 's.Inaforloopthatiterates throughtheindexedlist,wecallarandom S -permutationmatrixinthe i 'thsetof thelist,andcomputeitsneighborsusingourinterchangefunction.Wethentakethe 44

PAGE 49

intersectionofthiswiththe i )]TJ/F25 11.9552 Tf 12.189 0 Td [(1and i +1setsofthelistseparatelytond b i and c i ,withtheaddedexceptioncasesof b 0 = c 12 =0. Runningtheprogramtondthe b i 'sand c i 'sproducedinterestingresults.The numberswerenot,infact,consistentforanyinitial S -permutationmatrix,asthey neededtobefor )]TJ/F31 7.9701 Tf 8.081 -1.794 Td [(9 tobeadistanceregulargraph.Infact,thenumbersvaried withmultiplerunsofthesameinitial S -permutationmatrix,meaningthatdierent randomchoicesofmatricesinthe i 'thsethadadierentratioofneighborsinthe i )]TJ/F25 11.9552 Tf 12.815 0 Td [(1settoneighborsinthe i +1set.Thereweresomepropertiesthatheldfor every i ,regardlessofchoiceofinitialvertex.First, b i + c i =18 8 i 0 i 12, thatistosay,alltheneighborsofavertexatdistance i arecontainedineitherthe i +1or i )]TJ/F25 11.9552 Tf 11.946 0 Td [(1set{noneighborsofavertexdistance i fromaninitialvertexarealso distance i fromthevertex.Itwasalsoevidentfromtheresultsthatthe b i 'sformeda monotonicallyincreasingsequencefrom0to18whilethe c i 'sformedamonotonically decresingsequencefrom18to0.Thersttwoandlasttwoelementsofeachsequence weretheonlyelementstoremainconstant{ b 1 =1and c 1 =17,while b 11 =16and c 11 =2.The b i 'sand c i 'sfor2 i 10arenotconstant,however,foreachmatrixat adistance i .Thisisforasimplereasonthatisbestillustratedthroughanexample. Example 5.12 Consideraninitial S -permutationmatrix A = f ; 3 ; ; 6 ; ; 8 ; ; 1 ; ; 5 ; ; 7 ; ; 2 ; ; 4 ; ; 9 g : Weidentify A withitsvertex v 2 )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 andweshowhowtoobtaindierentresults for b 2 ,dependingonourchoiceof S -permutationmatrixdistance2from v .First consideramatrix B 2G 2 A wecanconsider B asavertex w 2 C 2 v wherethe two S -interchangesdoneon A toobtain B occurindierentblockrows/columns.One suchexampleofthistypeofmatrixis B = f ; 3 ; ; 7 ; ; 8 ; 5 ; 1 ; 6 ; 5 ; ; 6 ; ; 2 ; ; 4 ; ; 9 g : 45

PAGE 50

Then,ifweperformeitherofthetwo S -interchangesthatwedidtoarriveat B ,we willgetanelementthatisdistance1from A .Anyother S -interchangeweperform willleaveuswithan S -permutationmatrixthatisdistance3from A .Thus,weexpect b 2 =2 and c 2 =16 Whatifwepickan S -permutationmatrixthatisdistance2from A becauseoftwo S -interchangesonthesameblockroworcolumn?Forinstance,consider C = f 3 ; 3 ; 1 ; 6 ; 2 ; 8 ; ; 1 ; ; 5 ; ; 7 ; ; 2 ; ; 4 ; ; 9 g : Considerthethree S -interchangeswecanperformontherstblockrowof C ,representedbythetranpositions ,and .Thesewillresultinthe S -permutation matrices,withtheboldednumbersrepresentingthetranspositionsperformedon C : C 1 = f ; 3 ; 2 ; 6 ; 1 ; 8 ; ; 1 ; ; 5 ; ; 7 ; ; 2 ; ; 4 ; ; 9 g ; C 2 = f 1 ; 3 ; 3 ; 6 ; ; 8 ; ; 1 ; ; 5 ; ; 7 ; ; 2 ; ; 4 ; ; 9 g ; and C 3 = f 2 ; 3 ; ; 6 ; 3 ; 8 ; ; 1 ; ; 5 ; ; 7 ; ; 2 ; ; 4 ; ; 9 g : Noticethatallthreeofthesearedistinct S -permutationmatricesthataredistance1 from A ,sohere b 2 =3 Werealize,then,thatnotall S -permutationsatdistance i fromaninitialvertex actthesame:Ifthereisonlyone S -interchangeperformedonablockroworcolumn, wecanonlygetbackto A inonemovebyperformingthesametranspositionagain, butiftwodierent S -interchangesaredoneonthesameblockroworcolumn,any ofthethree S -interchangesontheblockroworcolumnwillproduceamatrixcloser to A .Thus,wecannotformanassociationschemeonthedistancesof )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 ,andwe concludethat )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 isnotdistanceregular. 46

PAGE 51

CHAPTER6 ConclusionandFurtherWork Dahl's[ 4 ]paperwasahelpfulstartingpointforinvestigatingthedistancesandthe diametersoftheSudokuGraphs.Wefoundrathereasily,givenitssmallvertexset, that )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(4 wasthehypercubegraphandhencedistanceregular.Followingtheexamples oftheassociationschemesonthecubeinChapter2,weformedtheHammingScheme H ; 2onthe S -permutationmatricesin 4 Ourhypothesisthat )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 wasdistanceregularaswefound )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(4 tobewasshown tobeincorrect,however,withthePythonprogramwecreated.Thisisdueto thefundamentaldierencesthatarisewhenperformingmultiple S -interchangeson distinctblockrowsorcolumnsversusonthesameblockroworcolumn.These dierencesarebestsummarizedandunderstoodbyconsideringpermutationsand transpositions.Considerageneral S -permutationmatrrix A 2 9 inBCN,with A = f i k ;j k g 9 k =1 .First,considerperformingtwo S -interchangesonblocksindifferentblockrows/columns.Onesuchexampleofthiscanberepresentedbythe permutation i 4 i 6 j 1 j 7 .Thisisapermutationinvolvingtwodisjointtranspositions,soitisasreducedasitcanbe.Itwillproducean S -permutationmatrixthat isdistance2from A byProposition5.3.Weknowwhatthiselementis: B = f i 1 ;j 7 ; i 2 ;j 2 ; i 3 ;j 3 ; i 6 ;j 4 ; i 5 ;j 5 ; i 4 ;j 6 ; i 7 ;j 1 ; i 8 ;j 8 ; i 9 ;j 9 g Ifwewantedtogettoanelementdistance1from A byonlyperformingone S interchange,ouronlyoptionswouldbetoundo"oneofthetwotranspositionsby performingoneofthetwo S -interchangesagain.Anyother S -interchangewecould performon B willproduceanelementdistance3awayfrom A 47

PAGE 52

Ontheotherhand,performingtwodierent S -interchangesonthesameblock roworcolumnof A worksdierently.Consider,forexample,performingthe S interchangesrepresentedbytheproductoftranspositions i 7 i 9 i 8 i 9 .Tokeep consistentwithcyclemultiplication,these S -interchangesareperformedfromright toleft.Unlikewhatweobservedbefore,theendresultofthesetwoswapscanbe reduced;inthiscase,itreducestothe3-cycle i 7 i 9 i 8 .Weobtainan S -permutation matrix C distance2from A ,with C = f i 1 ;j 1 ; i 2 ;j 2 ; i 3 ;j 3 ; i 4 ;j 4 ; i 5 ;j 5 ; i 6 ;j 6 ; i 9 ;j 7 ; i 7 ;j 8 ; i 8 ;j 9 g AsdemonstratedinExample5.12,allofthethree S -interchangesonthethirdblock rowwillproduceadistinctelementdistance1from A ,butanyotherofthe15 S interchangeswecandowillproduceanelementdistance3from A Thus,everyvertexatdistance2from A doesnotactthesameaseveryother vertexatthatdistance,aswehadbelieved.Thisextendstodistanceslargerthan 2aswell{Infact,everydistancesetmorethanone S -interchangeinfromeither endi.e.,everysetofelementsdistance i from A for2 i 11willhavesimilar inconsistenciesarisingfromthesamereason.Thismeansthat )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 isnotdistance regularaswehadhoped. Theremight,however,stillbeanassociationschemethatwecanformon )]TJ/F31 7.9701 Tf 8.081 -1.793 Td [(9 perhapsusinggraphcoloring,asdescribedinDenition3.5.Thisisonepossiblearea offutureresearch. Anotherareaoffutureworkistogeneralizetothe n case.ThePythonprogram waswrittenforageneral n ,butthesizeofanycase n 4wouldrequiretheuse ofamorepowerfulcomputerthantheoneused.Wedo,however,haveaconjecture regardingthediameteroftheSudokuGraphforthegeneral n case: Conjecture 6.1 Thediameterof )]TJ/F34 7.9701 Tf 8.081 -1.794 Td [(N willbe 2 n n )]TJ/F25 11.9552 Tf 12.079 0 Td [(1 ,theupperboundgiven inTheorem2.9fromDahl.Thenumbers f a i g 2 n n )]TJ/F31 7.9701 Tf 6.586 0 Td [(1 i =0 ofverticesatagivendistance i fromaninitialvertex A willbethesameregardlessofchoiceof A 48

PAGE 53

Theintuitionbehindthisconjecturereliesonthefactthatany n cyclecanbe writtenasaseriesof n )]TJ/F25 11.9552 Tf 12.911 0 Td [(1transpositions.Thus,ifeveryblockrowandcolumn ofamatrix B isrepresentedbypermutingeach n -setoftheblockrowandcolumn positionsof A ina n cycle,weexpecttobeablegetfrom A to B withaseriesof n )]TJ/F25 11.9552 Tf 10.909 0 Td [(1 S -interchangesoneachblockrowandcolumnof A .Thereare n blockrowsand n blockcolumns,soweexpectthediameterof )]TJ/F34 7.9701 Tf 8.081 -1.793 Td [(N tobe2 n n )]TJ/F25 11.9552 Tf 11.955 0 Td [(1. AsdiscussedinChapter2, S -permutationmatricesarethebuildingblocks"of Sudokupuzzles{AcompletedSudokupuzzle, P ,oforder N willhaveadecomposition P = P N i =1 i A i ,with A i 2 N .Moreover,the A i 'saredisjoint,meaningno two1'sareinthesameposition i k ;j k ,thisisnotasstrictascounterpartfrom Denition5.7.Alastareaoffurtherstudycanbefoundinrelatingresultsabout S -permutationmatricesandSudokugraphsbacktothemainquestionsinSudoku mathematics,overviewedinChapter1.Ananalysisofdistancesbetweenthe S permutationmatricesinmanysolvedpuzzlesmighthaveinterestingresultsaswell. Itwouldberelativelysimpletocreateaprogramtocollectsuchdata,especiallywith thedistanceformula/algorithmprovidedinChapter5. Wehopetohaveimpartedthereaderwithanunderstandingthat,especiallyfora puzzlethatmanyinsisthaslittletodowithmath,Sudokuhasquitethemathematical nature.ThereisstillmuchthatcanbelearnedregardingthemathinSudoku,and theproblemsexaminedinthisthesisandproposedinthisconclusionarejustafew examplesofthis. 49

PAGE 54

APPENDIXA Code fromitertoolsimportchain,combinations importcopy importrandom defcomboschoice_list: """Generatestranspositionstoperform. Args: choice_list:Listoflistsofelementstocreate2-tuplesfrom. Returns: 2-tuples,insortedorderwithnorepeatedelementsforeach xinchoice_list. """ returnlistchain*[combinationsx,2forxinchoice_list] defswap_listn: """Createsalistoftranspositionstoperform. Groupstheindicesofrowandcolumnpositionsintothecorrect numberspertainingtoeachblockrowandcolumn,thenformsall possible2-tuplesusingcombosfunction. 50

PAGE 55

Args: n:Anaturalnumber. Returns: Twolistsof2-tuples,thefirstpertainingtorowtranpositions,thesecondtocolumn. """ all_choices=rangen*n i_choices=[all_choices[i:i+n]foriinrange,n*n,n] j_choices=[all_choices[i::n]foriinrangen] returncombosi_choices,combosj_choices deftransposeinitial,swap,pos: """PerformsanS-interchangeoninitial. Args: initial:AnS-permutationmatrixasalistoftheiandj positionsofits1's swap:The2-tupleofindicestoswap. pos:0or1,pertainstoiftheswapinonaroworcolumn Returns: ThenewS-permmatrixresultingfromthespecifiedtranposition oninitial """ initial[swap[0]][pos],initial[swap[1]][pos]=initial[swap[1]][pos], initial[swap[0]][pos] 51

PAGE 56

defpreprocess_s_permsneighbors: """Correctstheformofsettoperformtanspositions. Wehaveneighborsinasetoftuplesoftuples,butweneedthe innertuplesinlists. """ returntupletuplelistxforxinneighborforneighborinneighbors definterchanges_list,swaps_list: """PerformsS-interchangesonalistofS-permmatrices. Args: s_list:AlistofS-permuatationmatrices swaps_list:listoftranspositiionsonindices Returns: Asetofalltheneighborsofallthematricesins_list. """ neighbors=[] fors_permins_list: forindex,swapsinenumerateswaps_list: forswapinswaps: perm=copy.deepcopys_perm transposeperm,swap,index result=tupletuplexforxinperm neighbors.appendresult returnsetneighbors 52

PAGE 57

defdistance_countern,swaps,initial: """Formsalistofsetsofitemsateverydistancefrominitial. Args: n:Anaturalnumber. swaps:Alistofindicestotranspose. intial:AstartingS-permutationmatrix. Returns: AnindexedlistofsetsofS-permmatricesateverydistance frominitial. """ counts=[1]#Numberofs-permutationsatthisdistance c_list=[set[tupletuplexforxininitial]] neighbors=interchange[initial],swaps whilelenneighbors>0: counts.appendlenneighbors #printneighbors c_list.appendneighbors tmp_neighbors=preprocess_s_permsneighbors neighbors=interchangetmp_neighbors,swaps neighbors=neighbors.difference*c_list #Printtheresults printcounts printsumcounts returnc_list 53

PAGE 58

defneighbors_at_distance_ic_list,swaps: """Findstheb_iandc_inumbers. Picksarandomelementdistanceifrominitialandintersectsits neighborswithelementsi-1frominitialforb_iandi+1from initialforc_i. Args: c_list:Theresultofthedistance_counterfunction,anindexed listofitemsateverydistancefrominitial. swaps:Thelistoftranspositionstoperform. Returns: Thenumbersb_iandc_iforalli. """ fori,c_currentinenumeratec_list: c_current_list=listc_current x=random.choicec_current_list #Thexthatischosenmatters.Itcanbehelpfultoprintx. tmp_x=preprocess_s_perms[x] neigh_x=interchangetmp_x,swaps #Exceptionendcase. ifi==0: b_i=0 c_i=lenneigh_x.intersectionc_list[i+1] printb_i,c_i 54

PAGE 59

#Otherexceptionendcase. elifi==lenc_list-1: b_i=lenneigh_x.intersectionc_list[i-1] c_i=0 printb_i,c_i #Normaldefinitionsforthemiddlecases. else: b_i=lenneigh_x.intersectionc_list[i-1] c_i=lenneigh_x.intersectionc_list[i+1] printb_i,c_i if__name__=='__main__': #n=2 #initial=[1,1],[0,2],[2,0],[3,3] n=3 initial= [1,2],[2,5],[0,7], [5,0],[4,4],[3,6], [8,1],[6,3],[7,8] swaps=swap_listn c_list=distance_countern,swaps,initial neighbors_at_distance_ic_list,swaps 55

PAGE 60

Bibliography [1]Bailey,R.A. AssociationSchemes:DesignedExperiments,Algebra,andCombinatorics; CambridgeUniversityPress:Cambridge,2004;pp1-26. [2]Bailey,R.A.;Cameron,P.;Connelly,R.Sudoku,GerechteDesigns,Resolutions,AneSpace, Spreads,Reguli,andHammingCodes. Am.MathMon. 2008. 115 ,383-404. [3]Bannai,E.;Ito,T. AlgebraicCombinatoricsIAssociationSchemes; TheBenjamin/Cummings PublishingCompany,Inc.:MenloPark,California,1984;p207. [4]Dahl,G.PermutationMatricesRelatedtoSudoku. LinearAlgebraAppl. 2009. 430 ,2457-2460. [5]Felgenhauer,B.;Jarvis,F.EnumeratingPossibleSudokuGrids.InternalReport.Universityof Sheeld,2005. [6]Godsil,C.D. AlgebraicCombinatorics; Chapman&Hall,Inc.:NewYork,1993;p198. [7]GrayCodein4-cube. http://www.texample.net/tikz/examples/gray-code-in-4-cube/ [8]Herzberg,A.;Murty,R.SudokuSquaresandChromaticPolynomials. NoticesoftheAMS 2007. 54 ,708-717. [9]Nguyen,M. AlgorithmicGraphTheory. http://code.google.com/p/graph-theory-algorithms-book/ [10]ThePetersenGraph. GraphTheoryinLaTeX. http://graphtheoryinlatex.blogspot.com/2006/08/petersen-graph.html [11]Royle,G. http://mapleta.maths.uwa.edu.au/gordon/sudokumin.php [12]SpikedMathComics. http://spikedmath.com/033.html 56


ERROR LOADING HTML FROM SOURCE (http://ncf.sobek.ufl.edu//design/skins/UFDC/html/footer_item.html)