Små latinska rutor och kvasigrupper

Latinska kvadrater och kvasigrupper är likvärdiga matematiska objekt, även om den förra har en kombinatorisk karaktär medan den senare är mer algebraisk . Listan nedan kommer att överväga exemplen på några mycket små beställningar , vilket är sidolängden på kvadraten eller antalet element i motsvarande kvasigrupp.

Ekvivalensen

Med tanke på en kvasigrupp Q med n element är dess Cayley-tabell (nästan allmänt kallad dess multiplikationstabell ) en ( n + 1) × ( n + 1) tabell som inkluderar gränser; en översta raden med kolumnrubriker och en vänstra kolumn med radrubriker. Om du tar bort kanterna lämnas en n × n array som är en latinsk kvadrat. Denna process kan vändas, börja med en latinsk kvadrat, införa en kantlinje och kolumn för att få multiplikationstabellen för en kvasigrupp. Även om det är fullständigt godtycke i hur denna gränsning görs, är kvasigrupperna som erhålls genom olika val ibland likvärdiga i den mening som anges nedan.

Isotopi och isomorfism

Två latinska rutor, L ₁ och L ₂ av storlek n är isotopiska om det finns tre bijektioner från raderna, kolumnerna och symbolerna för L ₁ till raderna, kolumnerna och symbolerna för L ₂ , som mappar L ₁ till L ₂ . Isotopi är en ekvivalensrelation och ekvivalensklasserna kallas isotopiklasser .

En starkare form av likvärdighet finns. Två latinska rutor, L ₁ och L ₂ på sidan n med gemensam symboluppsättning S som också är indexuppsättningen för raderna och kolumnerna i varje kvadrat, är isomorfa om det finns en bijektion g:S → S så att g ( L ₁ ( i , j ) _, = L2 ( g ( i ), g ( j ) ) ) för alla i j i S. Ett alternativt sätt att definiera isomorfa latinska kvadrater är att säga att ett par isotopiska latinska kvadrater är isomorfa om de tre bijektionerna som används för att visa att de är isotopiska faktiskt är lika. Isomorfism är också en ekvivalensrelation och dess ekvivalensklasser kallas isomorfismklasser .

En alternativ representation av en latinsk kvadrat ges av en ortogonal array . För en latinsk kvadrat av ordningen n är detta en n ² × 3 matris med kolumner märkta r , c och s och vars rader motsvarar en enda position i den latinska kvadraten, nämligen positionens rad, positionens kolumn och symbolen i positionen. Alltså för ordningen tre latinska kvadraten,

1	2	3
2	3	1
3	1	2

den ortogonala arrayen ges av:

r	c	s
1	1	1
1	2	2
1	3	3
2	1	2
2	2	3
2	3	1
3	1	3
3	2	1
3	3	2

Villkoret för att en matris av lämplig storlek ska representera en latinsk kvadrat är att för två i , j valfria kolumner är de n ² ordnade paren som bestäms av raderna i dessa kolumner alla par ( ) med 1 ≤ i , j ≤ n , en gång vardera .

Denna egenskap går inte förlorad genom att permutera de tre kolumnerna (men inte etiketterna), så ytterligare en ortogonal array (och därmed ytterligare en latinsk kvadrat) erhålls. Till exempel, genom att permutera de två första kolumnerna, vilket motsvarar att transponera kvadraten (reflekterande om dess huvuddiagonal) ger en annan latinsk kvadrat, som kanske är isotopisk till originalet. I det här fallet, om kvasigruppen som motsvarar denna latinska kvadrat uppfyller den kommutativa lagen , är den nya latinska kvadraten densamma som den ursprungliga. Sammanlagt finns det sex möjligheter inklusive "gör ingenting", vilket ger högst sex latinska rutor som kallas konjugaten ( även parastrofer ) av den ursprungliga kvadraten.

Två latinska rutor sägs vara paratopiska , även huvudklassens isotopiska , om en av dem är isotopisk till ett konjugat av den andra. Detta är också ett ekvivalensförhållande, med ekvivalensklasserna som kallas huvudklasser , arter eller paratopiklasser . Varje huvudklass innehåller upp till sex isotopiklasser.

En huvudklass är en osammanhängande förening av isotopiklasser och en isotopiklass är en osammanhängande förening av isomorfismklasser.

Isotopiska kvasigrupper

Låt ( Q ,∘) och ( R ,∗) vara två kvasigrupper. En ordnad trippel ( f , g , h ) av bijektioner från Q till R kallas en isotopism av ( Q ,∘) till ( R ,∗) om f ( x ) ∗ g ( y ) = h ( x ∘ y ) för alla x, y i G . Sådana kvasigrupper sägs vara isotopiska .

Om i ovanstående definition f = g = h så sägs kvasigrupperna vara isomorfa .

Till skillnad från situationen med latinska kvadrater, när två isotopiska kvasigrupper representeras av Cayley-tabeller (kantade latinska kvadrater), fungerar permutationerna f och g endast på kantrubrikerna och flyttar inte kolumner och rader, medan h verkar på tabellens kropp .

Att permutera raderna och kolumnerna i en Cayley-tabell (inklusive rubrikerna) ändrar inte kvasigruppen den definierar, men den latinska kvadraten som är associerad med denna tabell kommer att permuteras till en isotop latinsk kvadrat. Normalisering av en Cayley-tabell (att sätta kantrubrikerna i någon fast förutbestämd ordning genom att permutera rader och kolumner inklusive rubrikerna) bevarar alltså isotopiklassen för den associerade latinska kvadraten. Dessutom, om två normaliserade Cayley-tabeller representerar isomorfa kvasigrupper så är deras associerade latinska kvadrater också isomorfa. Följaktligen är antalet distinkta kvasigrupper av en given ordning antalet isomorfismklasser av latinska kvadrater av den ordningen.

Notation

Uppsättningen symboler som används i en latinsk kvadrat (eller kvasigrupp) är godtycklig och enskilda symboler har ingen betydelse, även om de kan ha en betydelse i andra sammanhang. Så eftersom det är vanligast att se symbolmängderna {1,2, ... , n } eller {0,1, ... , n − 1 } använda, måste man komma ihåg att dessa symboler inte har någon numerisk betydelse. För att betona denna punkt använder små latinska rutor ibland bokstäver i alfabetet som en symboluppsättning.

Räknar latinska rutor

Eftersom en latinsk kvadrat är ett kombinatoriskt objekt är symboluppsättningen som används för att skriva kvadraten oväsentlig. Således, som latinska rutor, bör dessa betraktas som samma:

${\begin{matrix}a&b\\b&a\end{matrix}}$ och ${\begin{matrix}1&2\\2&1\end{matrix}}.$

På samma sätt, och av samma anledning,

${\begin{matrix}b&a\\a&b\end{matrix}}$ och ${\begin{matrix}1&2\\2&1\end{matrix}}$

bör ses som detsamma. Således,

${\begin{matrix}a&b\\b&a\end{matrix}}$ och ${\begin{matrix}b&a\\a&b\end{matrix}}$

kan inte ses som olika latinska rutor.

Detta intuitiva argument kan göras mer exakt. De latinska torgen

${\begin{matrix}a&b\\b&a\end{matrix}}$ och ${\begin{matrix}b&a\\a&b\end{matrix}},$

är isotopiska på flera sätt. Låt ( a,b ) vara den involutoriala permutationen på mängden S = { a , b }, vilket skickar a till b och b till a . Sedan kommer isotopin {( a , b ), id , id } att byta ut de två raderna i den första kvadraten för att ge den andra kvadraten ( id är identitetspermutationen). Men, { id , ( a , b ), id } som växlar de två kolumnerna är också en isotopi, liksom { id , id , ( a , b ) } som växlar de två symbolerna. Men {( a , b ), ( a , b ), ( a , b ) } är också en isotopi mellan de två kvadraterna, så detta kvadratpar är isomorfa.

Minskade rutor

Att hitta en given latinsk kvadrats isomorfismklass kan vara ett svårt beräkningsproblem för kvadrater av stor ordning. För att minska problemet något kan en latinsk ruta alltid sättas i en standardform som kallas en reducerad kvadrat . En förminskad kvadrat har sina översta radelement skrivna i någon naturlig ordning för symboluppsättningen (till exempel heltal i ökande ordning eller bokstäver i alfabetisk ordning). De vänstra kolumnposterna placeras i samma ordning. Eftersom detta kan göras genom rad- och kolumnpermutationer, är varje latinsk kvadrat isotopisk till en reducerad kvadrat. Således måste varje isotopiklass innehålla en reducerad latinsk kvadrat, men en latinsk kvadrat kan ha mer än en reducerad kvadrat som är isotopisk för sig. Faktum är att det kan finnas mer än en reducerad kvadrat i en given isomorfismklass.

Till exempel de reducerade latinska kvadraterna av ordning fyra,

$&2\\4&3&2&1\end{matrix}}$${\begin{matrix}1&2&3&4\\2&1&4&3\\3&4&2&1\\4&3&1&2\end{matrix}}$ och

är båda i klassen isomorfism som också innehåller den reducerade kvadraten

${\begin{matrix}1&2&3&4\\2&3&4&1\\3&4&1&2\\4&1&2&3\end{matrix}}.$

Detta kan visas av isomorfismerna {(3,4), (3,4), (3,4)} respektive {(2,3), (2,3), (2,3)}.

Eftersom isotopiklasser är osammanhängande ger antalet reducerade latinska kvadrater en övre gräns för antalet isotopklasser. Dessutom är det totala antalet latinska kvadrater n !( n − 1)! gånger antalet reducerade rutor.

Normalisera en Cayley-tabell för en kvasigrupp på samma sätt som en reducerad latinsk kvadrat. Då har kvasigruppen associerad med en reducerad latinsk kvadrat ett (tvåsidigt) identitetselement (nämligen det första elementet bland radrubrikerna). En kvasigrupp med en dubbelsidig identitet kallas en loop . Vissa, men inte alla, loopar är grupper. För att vara en grupp måste också den associativa lagen hålla.

Isotopi invarianter

Antalet olika understrukturer i en latinsk kvadrat kan vara användbara för att skilja dem från varandra. Vissa av dessa räkningar är desamma för varje isotop av en latinsk kvadrat och kallas isotopi-invarianter. En sådan invariant är antalet 2 × 2 delkvadrater, kallade intercalates . En annan är det totala antalet transversaler , en uppsättning av n positioner i en latinsk kvadrat av ordningen n , en i varje rad och en i varje kolumn, som inte innehåller något element två gånger. Latinska rutor med olika värden för dessa räkningar måste ligga i olika isotopiklasser. Antalet interkalat är också en huvudklassinvariant.

Beställning 1

För ordning ett finns det bara en latinsk ruta med symbol 1 och en kvasigrupp med underliggande mängd {1}; det är en grupp, den triviala gruppen .

Beställning 2

Det finns bara en reducerad latinsk kvadrat av ordning två (och endast två totalt), nämligen

${\begin{matrix}1&2\\2&1\end{matrix}}.$

Eftersom det bara finns en reducerad kvadrat av denna ordning, finns det bara en isotopiklass. I själva verket är denna isotopiklass också en isomorfismklass ( visas ovan) .

Eftersom det bara finns en isomorfismklass av latinska kvadrater, finns det bara en kvasigrupp av ordning två (upp till isomorfism) och det är gruppen som vanligtvis betecknas med ℤ /2 ℤ , den cykliska gruppen av ordning två.

Beställning 3

Det finns också bara en reducerad latinsk ruta av ordning tre (av 12),

${\begin{matrix}1&2&3\\2&3&1\\3&1&2\end{matrix}}.$

Det finns alltså bara en isotopiklass. Denna isotopiklass är emellertid sammanslutningen av fem isomorfismklasser.

Tre av de fem isomorfismklasserna innehåller tre latinska kvadrater vardera, en innehåller två och en innehåller bara en. Den reducerade kvadraten är i en isomorfismklass med tre element och så den motsvarande kvasigruppen är en slinga, i själva verket är det en grupp, ℤ /3 ℤ , den cykliska gruppen av ordning tre. En latinsk kvadrat som representerar var och en av dessa isomorfismklasser ges av (talet under varje är antalet kvadrater i motsvarande isomorfismklass):

${\begin{matrix}1&2&3\\2&3&1\\3&1&2\\&(3)&\end{matrix}}\qquad \qquad {\begin{matrix}2&3&1\\1&2&3\\3&1&2\\&( 3)&\end{matrix}}\qquad \qquad {\begin{matrix}2&1&3\\3&2&1\\1&3&2\\&(3)\end{matrix}}\qquad \qquad {\begin{matrix}3&2&1\ \2&1&3\\1&3&2\\&(2)&\end{matris}}\qquad \qquad {\begin{matrix}1&3&2\\3&2&1\\2&1&3\\&(1)&\end{matris}}.$

Beställning 4

Det finns fyra reducerade latinska rutor av ordning fyra (av 576 rutor). Dessa är:

${\begin{matrix}1&2&3&4\\2&1&4&3\\3&4&1&2\\4&3&2&1\end{matrix}}\qquad {\begin{matrix}1&2&3&4\\2&1&4&3\\3&4&2&1\\24&3&}\{ qquad {\begin{matrix}1&2&3&4\\2&3&4&1\\3&4&1&2\\4&1&2&3\end{matrix}}\qquad {\begin{matrix}1&2&3&4\\2&4&1&3\\3&1&4&2\\14&}{matrix}$

De tre sista av dessa är isomorfa ( se ovan) . Det finns två huvudklasser, två isotopiklasser och 35 isomorfismklasser. Bland de 35 kvasigrupperna är bara två loopar, och de är faktiskt grupper. Motsvarande den första kvadraten ovan är Klein fyra-gruppen , medan motsvarande någon av de andra tre kvadraterna är den cykliska gruppen ℤ /4ℤ . Den första kvadraten har åtta transversaler och 12 intercalates, medan var och en av de andra har inga transversaler och fyra intercalates.

Isomorfismklassen i Klein fyra-gruppen har fyra medlemmar, medan isomorfismen i den cykliska gruppen har 12 medlemmar. Av de 576 latinska kvadraterna är 288 lösningar av 4×4-versionen av Sudoku , ibland kallad Shi Doku [1] .

Beställning 5

Av de 161 280 latinska rutor av ordning fem finns det 56 reducerade rutor. Det finns två huvudklasser och bara två isotopiklasser, men 1 411 isomorfismklasser. Det finns sex isomorfismklasser som innehåller reducerade kvadrater, det vill säga det finns sex slingor, varav bara en är en grupp, den cykliska gruppen av ordning fem.

Nedan finns två reducerade latinska kvadrater av ordning fem, en från varje isotopiklass.

${\begin{matrix}0&1&2&3&4\\1&2&3&4&0\\2&3&4&0&1\\3&4&0&1&2\\4&0&1&2&3\end{matrix}}\qquad \qquad {\begin{matrix}0&1&2&3&4\\1&0&3&4&2\\2&3&4&0&1\\3&4&1&2&0\\4&2&0&1&3\end{matrix}}$

Den första kvadraten har 15 transversaler, inga intercalates och är den obegränsade Cayley-tabellen för den cykliska gruppen ℤ /5 ℤ . Den andra kvadraten har tre transversaler och fyra intercalates. Den representerar en slinga som inte är en grupp, eftersom till exempel 2 + (3 + 4) = 2 + 0 = 2, medan (2 + 3) + 4 = 0 + 4 = 4, så den associativa lagen inte håll.

Beställningar 6 till 10

Antalet latinska rutor, när ordningen ökar, uppvisar det fenomen som kallas kombinatorisk explosion ; för även små ökningar i storlek motsvarar enorma ökningar av sorter. De grundläggande räkningarna ges i de följande två tabellerna, och inte mycket utöver vad som presenteras här är känt med exakthet.

Antal isotopklasser av latinska kvadrater och kvasigrupper (isomorfismklasser)

n	huvudklasser	isotopiklasser	isomorfism klasser
6	12	22	1,130,531
7	147	564	12,198,455,835
8	283,657	1,676,267	2,697,818,331,680,661
9	19,270,853,541	115,618,721,533	15 224 734 061 438 247 321 497
10	34,817,397,894,749,939	208,904,371,354,363,006	2,750,892,211,809,150,446,995,735,533,513

Antalet reducerade latinska rutor och slingor av olika storlekar

n	reducerade latinska kvadrater av storlek n	öglor av storlek n
6	9,408	109
7	16 942 080	23,746
8	535,281,401,856	106,228,849
9	377,597,570,964,258,816	9,365,022,303,540
10	7 580 721 483 160 132 811 489 280	20,890,436,195,945,769,617

Historia

Denna redogörelse följer McKay, Meynert & Myrvold (2007 , s. 100).

Räkningen av latinska rutor har en lång historia, men de publicerade redovisningarna innehåller många fel. Euler 1782 och Cayley 1890 kände båda till antalet reducerade latinska rutor upp till storleksordningen fem. 1915 MacMahon problemet på ett annat sätt, men fick till en början fel värde för order fem. M.Frolov 1890 och Tarry 1901 fann antalet reducerade kvadrater av ordningen sex. M. Frolov gav en felaktig räkning av reducerade kvadrater av ordningen sju. RA Fisher och F. Yates , omedvetna om tidigare arbete av E. Schönhardt, gav antalet isotopiklasser av beställningar upp till sex. År 1939 hittade HW Norton 562 isotopklasser av ordning sju, men erkände att hans metod var ofullständig. A. Sade, 1951, men privat publicerad tidigare 1948, och PN Saxena hittade fler klasser och, 1966, noterade DA Preece att detta korrigerade Nortons resultat till 564 isotopiklasser. Men 1968 meddelade JW Brown ett felaktigt värde på 563, vilket ofta har upprepats. Han gav också fel antal isotopklasser av ordning åtta. Det korrekta antalet reducerade kvadrater av ordningen åtta hade redan hittats av MB Wells 1967, och antalet isotopiklasser 1990 av G. Kolesova, CWH Lam och L. Thiel. Antalet reducerade rutor för order nio erhölls av SE Bammel och J. Rothstein, för order 10 av BD McKay och E. Rogoyski, och för order 11 av BD McKay och IM Wanless.

Se även

• Lista över små grupper

Anteckningar

•   Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 978-1-58488-506-1
•    Dénes, J.; Keedwell, AD (1974), Latin squares and their applications , New York-London: Academic Press, sid. 547, ISBN 0-12-209350-X , MR 0351850
•     McKay, Brendan D. ; Meynert, Alison; Myrvold, Wendy (2007), "Små latinska kvadrater, kvasigrupper och slingor" (PDF) , Journal of Combinatorial Designs , 15 ( 2): 98–119, CiteSeerX 10.1.1.151.3043 , doi : 10.10202/ jCID .jc 82321 , Zbl 1112.05018