Latinsk kvadrat

Från Rilpedia

Texten från svenska Wikipedia

En latinsk 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.

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:

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 s₁,...,s_r med f_i 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 s₁. 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₁ till position f₁. Sedan permuterar vi kolumner så att alla element i rad s₁ flyttas till den vänstra sidan. Då står siffran n som sista element i raden, på diagonalen. Rad s₂ flyttas till position 1 + f₁ + f₂ och s_i, 1 ≤ i ≤ r, flyttas till position 1 + f₁ + ... + 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 (uppfifrå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.

Eulers officerarproblem

Leonhard Euler undrade om det var 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 fyllde en 6 × 6 kvadrat där ingen från samma regemente eller av samma grad stod på samma rad eller kolumn. Euler anade att det inte fanns någon lösning på problemet vilket bevisades av Gaston Tarry 1901.

Ortogonala latinska kvadrater

Två latinska kvadrater A = (a_ij) och B = (b_ij) av samma storlek säges vara ortogonala om (a_ij,b_ji) är distinkta . 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.
Från två ortogonala latinska kvadrater kan man få fram en magisk kvadrat, dvs summan av siffrorna i varje rad och kolumn är lika.

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

Aigner, Martin; Günter M. Ziegler: Proofs from the book, Springer-Verlag, 2004. ISBN 3540404600. 
Lovász, László; Jószef Pelikán, Katalin Vesztergombi: Discrete Mathematics, Springer-Verlag, 2003. ISBN 0387955852. 
A. Bogomolny, Latin Squares from Interactive Mathematics Miscellany and Puzzles http://www.cut-the-knot.org/arithmetic/latin_intro.shtml, 11-05-2008
http://en.wikipedia.org/wiki/Latin_square, 11-05-08