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:

${\begin{bmatrix}1&2&3&4\\4&1&2&3\\3&4&1&2\\2&3&4&1\\\end{bmatrix}}$

Alternativt kan en latinsk kvadrat definieras som en funtion $f\colon X\times Y\longrightarrow Z$ med egenskapen att varje specialisering $g_{x}$ definierad genom $g_{x}(y)=f(x,y)$ för något $x\in X$ är en bijektion och varje specialisering $h_{y}$ definierad genom $h_{y}(x)=f(x,y)$ för något $y\in Y$ är en bijektion. Av detta följer omedelbart att de tre mängderna $X$ (radindex), $Y$ (kolumnindex) och $Z$ (symboler) har samma kardinalitet, så de kan lika gärna tas till att vara samma mängd, vanligen mängden $\{1,2,\dots ,n\}$ av positiva heltal mindre än eller lika med $n$; dock är det i konkreta fall inte ovanligt att $X=Y\neq Z$. För $X=Y=Z$ ä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 $R\subseteq X\times Y\times Z$ med egenskaperna att

1. det för varje $x\in X$ och $y\in Y$ finns ett entydigt $z\in Z$ som löser $(x,y,z)\in R$,
2. det för varje $x\in X$ och $z\in Z$ finns ett entydigt $y\in Y$ som löser $(x,y,z)\in R$, samt
3. det för varje $y\in Y$ och $z\in Z$ finns ett entydigt $x\in X$ som löser $(x,y,z)\in R$.

Ytterligare en definition är att en latinsk kvadrat är en äkta kantfärgning av en komplett bipartit graf $K_{n,n}$; 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 ${\tfrac {n}{2}}$ 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 $s_{1}$,...,$s_{r}$ med $f_{i}$ element i rad i 1 ≤ i ≤ r. Från Lemma 2 kan vi anta att det finns fler än ${\tfrac {n}{2}}$ 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 $s_{1}$. 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 $s_{1}$ till position $f_{1}$. Sedan permuterar vi kolumner så att alla element i rad $s_{1}$ flyttas till den vänstra sidan. Då står siffran n som sista element i raden, på diagonalen. Rad $s_{2}$ flyttas till position 1 + $f_{1}$ + $f_{2}$ och $s_{i}$, 1 ≤ i ≤ r, flyttas till position 1 + $f_{1}$ + ... + $f_{i}$ 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 $A=(a_{ij})$ och $B=(b_{ij})$ av samma storlek säges vara ortogonala om paret $(a_{ij},b_{ij})$ av element i de två kvadraterna entydigt identifierar paret $(i,j)$ 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 $q$ kan man konstruera mängder om $q-1$ sinsemellan ortogonala latinska kvadrater av storlek $q\times q$. Detta kan i användas för att konstruera ortogonala latinska kvadrater med vilken som helst sida $q>2$ som är en primtalspotens, i synnerhet $q=3,4,5,7,8,9,11$. Däremot kan konstruktionen inte användas för $q=10$, 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 $\Pi$ av ändlig ordning $q$ vara givet. Välj en punkt $O$ i planet; det finns exakt $q+1$ linjer genom $O$, och var och en av dessa har $q+1$ punkter. Numrera på varje sådan linje de punkter som inte är $O$ med talen $1,2,\dots ,q$; 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 $O$ är $q^{2}$; dessa kommer att svara mot de latinska kvadraternas element. Välj en linje $r$ genom $O$ till att bestämma radindex och en annan linje $c$ till att bestämma kolumnindex; de övriga linjerna $s_{1},\dots ,s_{q-1}$ genom $O$ bestämmer elementen i var sin latinsk kvadrat. För att ta reda på elementet $(i,j)$ i den $k$:te latinska kvadraten så låter man $P$ vara den punkt på linjen $r$ som märkts med talet $i$, man låter $Q$ vara den punkt på linjen $c$ som märkts med talet $j$, låter $l$ vara linjen genom $P$ och $Q$, samt låter $R$ vara skärningspunkten mellan linjerna $l$ och $s_{k}$. Det nummer som tilldelats $R$ ä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 $P$ och $R$, genom vilka det endast går en linje $l$, och denna har endast en skärningspunkt med linjen $c$, 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 $s_{k}$ och $s_{m}$ ortogonala mot varandra därför att den kombinationen av symboler entydigt definierar en linje $l$, så att symbolkombinationens entydiga rad och kolumn kan fås från skärningspunkterna med $r$ respektive $c$.

För koordinatiserbara projektiva plan, i synnerhet planen $\mathrm {PG} (2,q)$ över en ändligt kropp, kan det vara enklare att beskriva resultatet av denna konstruktion rent algebraiskt. Om $\mathbb {F} _{q}$ är den ändliga kroppen med $q$ element, och de latinska kvadraterna beskrivs som funktioner $f\colon \mathbb {F} _{q}\times \mathbb {F} _{q}\longrightarrow \mathbb {F} _{q}$, så är

$f_{\gamma }(x,y)=x+\gamma y$ för alla $x,y\in \mathbb {F} _{q}$

en distinkt latinsk kvadrat för varje $\gamma \in \mathbb {F} _{q}\setminus \{0\}$, och dessa $q-1$ latinska kvadrater är parvis ortogonala mot varandra.

I det konkreta fallet $q=4$, om man betecknar elementen i $\mathbb {F} _{q}$ med $0,1,a,b$, så är de tre erhållna ortogonala latinska kvadraterna

${\begin{array}{c|cccc}f_{1}&0&1&a&b\\\hline 0&0&1&a&b\\1&1&0&b&a\\a&a&b&0&1\\b&b&a&1&0\end{array}}\qquad {\begin{array}{c|cccc}f_{a}&0&1&a&b\\\hline 0&0&a&b&1\\1&1&b&a&0\\a&a&0&1&b\\b&b&1&0&a\end{array}}\qquad {\begin{array}{c|cccc}f_{b}&0&1&a&b\\\hline 0&0&b&1&a\\1&1&a&0&b\\a&a&1&b&0\\b&b&0&a&1\end{array}}$

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 $A=(a_{ij})$ och $B=(b_{ij})$ som ovan har elementmängd $\{1,2,\dots ,n\}$ så kan elementen i motsvarande magiska kvadrat $C$ beräknas med formeln $c_{ij}=a_{ij}+n(b_{ij}-1)$; ortogonaliteten garanterar att alla element i $C$ blir olika. Summan av en rad eller kolumn i $C$ är summan av motsvarande rad eller kolumn i $A$ plus $n$ gånger motsvarande summa för $B$ minus $n^{2}$, och en rad- eller kolumnsumma i en latinsk kvadrat $A$ eller $B$ ä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

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Latin square, 8 maj 2011.

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Graeco-Latin square, 29 juli 2015.

• Aigner, Martin; Günter M. Ziegler (2004). Proofs from the book. Springer-Verlag. ISBN 3540404600 
• Lovász, László; Jószef Pelikán, Katalin Vesztergombi (2003). Discrete Mathematics. Springer-Verlag. ISBN 0387955852 
• A. Bogomolny, Latin Squares from Interactive Mathematics Miscellany and Puzzles, 11-05-2008