Latinsk kvadrat

En latinsk kvadrat eller romersk kvadrat är en matris där elementen är ordnade på så sätt att varje rad och varje kolumn innehåller element av olika typ. Namnet latinsk kvadrat kommer från Leonhard Euler, som använde latinska bokstäver för att fylla i matrisen.

Definition 
En latinsk kvadrat är en n × n-matris där antalet distinkta element är n. Varje rad och kolumn ska innehålla exakt ett element av varje typ.

Det existerar en latinsk kvadrat för alla n, ty om man låter den översta raden vara '0 1 2 3 ... (n-1)', nästa rad vara '(n-1) 0 1 ... (n-2)' och så vidare, så har man konstruerat en latinsk kvadrat för godtyckligt n. 
Följande exempel är en latinsk kvadrat av ordning 4:

Alternativt kan en latinsk kvadrat definieras som en funtion  med egenskapen att varje specialisering  definierad genom  för något  är en bijektion och varje specialisering  definierad genom  för något  är en bijektion. Av detta följer omedelbart att de tre mängderna  (radindex),  (kolumnindex) och  (symboler) har samma kardinalitet, så de kan lika gärna tas till att vara samma mängd, vanligen mängden  av positiva heltal mindre än eller lika med ; dock är det i konkreta fall inte ovanligt att . För  är denna definition ekvivalent med: en latinsk kvadrat är multiplikationstabellen för en kvasigrupp (se även algebraisk struktur).

Ovanstående definitioner behandlar symboler på ett annat sätt än rader och kolumner, men begreppet latinsk kvadrat är helt symmetriskt med avseende på dessa tre axlar. En definition som tydliggör detta är den följande: En latinsk kvadrat är en treställig relation  med egenskaperna att
 det för varje  och  finns ett entydigt  som löser ,
 det för varje  och  finns ett entydigt  som löser , samt
 det för varje  och  finns ett entydigt  som löser .

Ytterligare en definition är att en latinsk kvadrat är en äkta kantfärgning av en komplett bipartit graf ; bastolkningen där är att ena partitionens hörn svarar mot rad, den andra partitionens hörn svarar mot kolumn, kanter svarar mot element i den latinska kvadraten och färger svarar mot symboler.

Historik 
Namnet latinsk kvadrat härrör från Eulers så kallade officerarproblem (1782):
 Är det möjligt att placera ut 36 officerare, från sex olika regementen med sex officerare av olika grad från varje regemente, så att de fyller en 6×6 kvadrat där inga två från samma regemente eller av samma grad står på samma rad eller kolumn?
I modern terminologi handlar detta problem om att konstruera två ortogonala latinska kvadrater (se nedan), men Euler föreslog att lösningar skulle presenteras som en matris där det i varje element stod en grekisk och en latinsk bokstav – en så kallad greko-latinsk kvadrat – där det ena alfabetet skulle ange grad och det andra regemente; ortogonaliteten blir då att varje kombination av grekisk och latinsk bokstav skall återfinnas i exakt ett element i matrisen. Förenklingen till att bara sätta ut en symbol i varje element kallas följaktligen en latinsk kvadrat.

Euler anade att det inte fanns någon lösning på problemet, vilket bevisades av Gaston Tarry 1901. Euler kunde konstruera lösningar för motsvarande problem av storlek n×n för varje n som inte ger rest 2 vid division med 4, och det förmodades länge att detta var alla storlekar för vilka lösningar alls fanns, men E. T. Parker, R. C. Bose och S. S. Shrikhande kunde 1959 bevisa att lösningar finns för alla n > 6 (liksom för n = 3, 4 och 5).

Euler var för övrigt inte den förste som diskuterade ortogonala latinska kvadrater. Jacques Ozanam hade 1725 presenterat problemet att placera ut alla ess, kungar, damer och knektar från en kortlek i en 4×4-kvadrat så att varje valör och varje färg förekom exakt en gång i varje rad och varje kolumn. Enstaka latinska kvadrater uppträder så ofta i elementär matematik att det är vanskligt att ange någon första förekomst; till exempel utgör entalssiffrorna i en vanlig additionstabell en latinsk kvadrat.

Smetaniuks sats 
Om färre än n element är ifyllda i en partiell latinsk kvadrat av ordning n är det alltid möjligt att konstruera en fullständig latinsk kvadrat av ordning n.
Trevor Evans var den första som funderade över frågeställningen 1960 och den fick namnet Evans förmodan. Ett bevis stod Bohdan Smetaniuk för, då han bevisade satsen 1981.
Till beviset av Smetaniuks sats behövs två lemman.

Lemma 1 
Varje r × n latinsk rektangel där r  n, kan utökas till en (r + 1) × n latinsk rektangel och därför också till en latinsk kvadrat.

Lemma 2 
Låt P vara en ofullständig latinsk kvadrat av ordning n med upp till n - 1 element och upp till  distinkta element.
Då kan P kompletteras till en fullständig latinsk kvadrat.

Bevis av Smetaniuks sats 
Beviset sker med induktion över n.
Fallet n ≤ 2 är trivialt. Vi studerar därför en latinsk kvadrat av storlek n ≥ 3 med upp till n - 1 element. 
Dessa element finns i r ≤ n - 1 olika rader numrerade ,..., med  element i rad i 1 ≤ i ≤ r.
Från Lemma 2 kan vi anta att det finns fler än  olika element vilket innebär att en siffra bara finns representerat en gång.
Efter permutering och omnumrering kan vi få att siffran n är representerad en gång, i rad .
Därefter vill vi permutera raderna så att alla rader ligger under diagonalen, utom siffran n som ska ligga på diagonalen.
Detta gör vi genom att först permutera rad  till position . Sedan permuterar vi kolumner så att alla element i rad  flyttas till den vänstra sidan.
Då står siffran n som sista element i raden, på diagonalen.
Rad  flyttas till position 1 +  +  och , 1 ≤ i ≤ r, flyttas till position 1 +  + ... +  och element i raden så långt till vänster som möjligt.
För att kunna använda induktion tar vi bort siffran n från diagonalen och bortser även från den första raden och den sista kolumnen.
Eftersom vi nu har en partiell latinsk kvadrat av ordning n - 1 med upp till n - 2 element kan vi använda induktionsantagandet som säger att vi komplettera vår partiella latinska kvadrat till en komplett latinsk kvadrat.
Då återstår att fylla ut den första raden och den sista kolumnen vilket kan göras med följande algoritm.
Målet är att sätta siffran n på diagonalen och fylla ut övriga platser. Detta gör vi rad för rad (uppifrån) 
sätta siffran n på plats (k, n), 2 ≤ k  n. Byt plats på element (k, n) och element (k, k).
Om elementet på plats (k, k) inte finns i kolumn n är bytet klart. 
Om det redan fanns representerat på plats (j, n) 2 ≤ j  k så byter vi plats på elementen (j, n) och (j, k). 
Om två element fortfarande är lika i kolumn n upprepas proceduren ett ändligt antal gånger tills elementen i kolumn n är distinkta.
Nu återstår bara den första raden och eftersom lemma 1 säger att en latinsk (r × n) rektangel kan utökas till en latinsk ((r + 1)× n) rektangel kan vi komplettera vår latinska rektangel till en latinsk kvadrat.
Härmed är satsen bevisad enligt induktionsprincipen.

Ortogonala latinska kvadrater 
Två latinska kvadrater  och  av samma storlek säges vara ortogonala om paret  av element i de två kvadraterna entydigt identifierar paret  av rad- och kolumnindex där de återfinns.
Det existerar inte något par av ortogonala 6 × 6 latinska kvadrater, vilket visades av G. Tarry år 1900. 
Eulers förmodan, som motbevisades på 1900-talet, behandlar existensen av ortogonala latinska kvadrater.

Konstruktion från projektiva plan 
Från vilket som helst ändligt projektivt plan av ordning  kan man konstruera mängder om  sinsemellan ortogonala latinska kvadrater av storlek . Detta kan i användas för att konstruera ortogonala latinska kvadrater med vilken som helst sida  som är en primtalspotens, i synnerhet . Däremot kan konstruktionen inte användas för , trots att ortogonala latinska kvadrater finns även av denna storlek, eftersom det inte finns något projektivt plan av ordning 10.

Konstruktionen är som följer. Låt ett projektivt plan  av ändlig ordning  vara givet. Välj en punkt  i planet; det finns exakt  linjer genom , och var och en av dessa har  punkter. Numrera på varje sådan linje de punkter som inte är  med talen ; olika sätt att göra detta på kommer att producera olika latinska kvadrater, men de kan överföras på varandra genom en lämplig permutation av rader, kolumner och symboler. Antalet linjer som inte går genom  är ; dessa kommer att svara mot de latinska kvadraternas element. Välj en linje  genom  till att bestämma radindex och en annan linje  till att bestämma kolumnindex; de övriga linjerna  genom  bestämmer elementen i var sin latinsk kvadrat. För att ta reda på elementet  i den :te latinska kvadraten så låter man  vara den punkt på linjen  som märkts med talet , man låter  vara den punkt på linjen  som märkts med talet , låter   vara linjen genom  och , samt låter  vara skärningspunkten mellan linjerna  och . Det nummer som tilldelats  är det sökta elementet i den latinska kvadraten. Konstruktionen genererar latinska kvadrater därför att det i ett projektivt plan finns exakt en linje som går genom varje par av punkter; en symbol kan till exempel inte förekomma två gånger i samma rad därför att rad och symbol motsvaras av två punkter  och , genom vilka det endast går en linje , och denna har endast en skärningspunkt med linjen , nämligen den som svarar mot kolumnen där symbolen faktiskt återfinns. På samma sätt är två kvadrater som genererats från olika linjer  och  ortogonala mot varandra därför att den kombinationen av symboler entydigt definierar en linje , så att symbolkombinationens entydiga rad och kolumn kan fås från skärningspunkterna med  respektive .

För koordinatiserbara projektiva plan, i synnerhet planen  över en ändligt kropp, kan det vara enklare att beskriva resultatet av denna konstruktion rent algebraiskt. Om  är den ändliga kroppen med  element, och de latinska kvadraterna beskrivs som funktioner , så är
   för alla  
en distinkt latinsk kvadrat för varje , och dessa  latinska kvadrater är parvis ortogonala mot varandra.

I det konkreta fallet , om man betecknar elementen i  med , så är de tre erhållna ortogonala latinska kvadraterna

Konstruktion av magiska kvadrater 
Från två ortogonala latinska kvadrater kan man få fram en magisk kvadrat, dvs summan av siffrorna i varje rad och kolumn är lika; däremot så garanterar konstruktionen inte att summan av siffrorna på en diagonal är densamma. Om de två ortogonala latinska kvadraterna  och  som ovan har elementmängd  så kan elementen i motsvarande magiska kvadrat  beräknas med formeln ; ortogonaliteten garanterar att alla element i  blir olika. Summan av en rad eller kolumn i  är summan av motsvarande rad eller kolumn i  plus  gånger motsvarande summa för  minus , och en rad- eller kolumnsumma i en latinsk kvadrat  eller  är helt enkelt summan av alla element i elementmängden.

Tillämpningar 
Latinska kvadrater används på en mängd olika områden så som till att programmera parallella processer, till felrättande koder och i idrottssammanhang till spelschema för serier.

Sudoku är ett spel som kan liknas vid att konstruera en latinsk kvadrat utgående från att några element redan är kända och med den ytterligare restriktionen att de så kallade regionerna ska uppfylla samma krav som raderna och kolumnerna. 
I Sudoku är det av vikt att den latinska kvadraten, med denna ytterligare restriktion, är kritisk, det vill säga att det existerar exakt en lösning utifrån de givna elementen.

Referenser 

A. Bogomolny, Latin Squares from Interactive Mathematics Miscellany and Puzzles, 11-05-2008

Matriser