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.

DefinitionRedigera

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

  1. det för varje   och   finns ett entydigt   som löser  ,
  2. det för varje   och   finns ett entydigt   som löser  , samt
  3. 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.

HistorikRedigera

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 satsRedigera

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 1Redigera

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 2Redigera

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 satsRedigera

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 rn - 1 olika rader numrerade  ,...,  med   element i rad i 1 ≤ ir. 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 ≤ ir, 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 kvadraterRedigera

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 planRedigera

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 kvadraterRedigera

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ämpningarRedigera

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.

ReferenserRedigera