Latinski kvadrat

Latínski kvadrát je n × n tabela (kvadratna shema oziroma matrika), napolnjena z n različnimi znaki, tako da se vsak znak pojavi le enkrat v vsaki vrstici in le enkrat v vsakem stolpcu. Na primer latinska kvadrata reda 3 in 4:

${\begin{bmatrix}1&2&3\\2&3&1\\3&1&2\\\end{bmatrix}}\quad \quad {\begin{bmatrix}a&b&d&c\\b&c&a&d\\c&d&b&a\\d&a&c&b\end{bmatrix}}$

Latinski kvadrati se pojavljajo kot množitvene tabele (Cayleyjeve tabele) kvazigrupe. Teorija latinskih kvadratov in teorija kvazigrup sta medsebojno povezani. Uporabljajo se pri (statističnem) načrtovanju (organizaciji) preskusov. Latinski kvadrati so poseben primer latinskih pravokotnikov.

Ime je med prvimi uporabljal Leonhard Euler, ki je za znake uporabljal latinične črke.

Latinski kvadrat je skrčen (reduciran, oziroma normaliziran ali v standardni obliki), če sta prva vrstica in prvi stolpec naravno urejena. Prvi latinski kvadrat zgoraj je skrčen, ker sta prva vrstica in stolpec urejena po vrsti 1, 2, 3. Vsak latinski kvadrat lahko s permutacijami prevedemo na skrčeno obliko.

Zapis v obliki pravokotne vrste

Če vsak element n × n latinskega kvadrata zapišemo kot trojico (r,c,s), kjer je r vrstica, c stolpec in s znak, dobimo množico n² trojk, ki se imenuje zapis kvadrata v obliki pravokotne vrste. Takšen zapis zgornjega prvega latinskega kvadrata je

{ (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) },

kjer, na primer, trojka (2,3,1) pomeni, da se v 2. vsrtici in 3. stolpcu nahaja znak 1. Definicijo latinskega kvadrata lahko v takšnem zapisu potem zapišemo:

• Obstaja n² trojk oblike (r,c,s), kjer je 1 ≤ r, c, s ≤ n.
• Različni so vsi pari (r,c), (r,s) kakor tudi (c,s).

Ortogonalnost latinskih kvadratov sta prva raziskovala Donald Knuth in Radž Čandra Bose.

Ekvivalenčni razredi latinskih kvadratov

Veliko operacij na latinskem kvadratu da nov latinski kvadrat. Ena izmed njih je, če ga obrnemo.

Če permutiramo vrstice, stolpce ali imena znakov nekega latinskega kvadrata, dobimo nov latinski kvadrat, ki je izotopičen prvemu. Izotopizem je ekvivalenčna relacija in je množica latinskih kvadratov razdeljena na podmnožice, ki se imenujejo izotopični razredi. Dva latinska kvadrata v istem razredu sta izotopična, v različnih razredih pa nista.

Drugo vrsto operacije lahko najlaže pojasnimo z zapisom v obliki pravokotne vrste. Če na novo sistematično in skladno razvrstimo tri elemente v vsaki trojki, dobimo novo pravokotno vrsto in z njo nov latinski kvadrat. Lahko na primer zamenjamo vsako trojko (r,c,s) s (c,r,s), ki odgovarja preslikavi prek glavne diagonale. Lahko tudi zamenjamo vsako trojko (r,c,s) s (c,s,r) kar je že bolj zapletena operacija. Vsega skupaj imamo 6 možnosti, med katere spada tudi prazna operacija in, ki da 6 latinskih kvadratov. Ti so konjugirani (tudi parastrofi) izvirnemu latinskemu kvadratu.

Končno lahko združimo ti dve ekvivalenčni operaciji: dva latinska kvadrata sta paratopična, oziroma izotopična glede na glavni razred, če je eden od njiju izotopičen konjugiranemu drugemu. To je spet ekvivalenčna relacija z ekvivalenčnimi razredi, ki se imenujejo glavni razredi, oziroma paratopični razredi. Vsak glavni razred vsebuje do 6 izotopičnih razredov.

Število latinskih kvadratov

Ne obstaja lahko izračunljiva enačba za število n × n latinskih kvadratov z znaki 1,2,...,n. Tudi najboljše ocene za velike n so zelo grobe. Tu so podane vse znane natančne vrednosti. Število narašča zelo hitro.

Za vsak n je število vseh latinskih kvadratov (OEIS A002860) enako n! (n-1)! krat število skrčenih latinskih kvadratov (OEIS A000315).

Število latinskih kvadratov različnih velikosti

n	skrčeni latinski kvadrati reda n	vsi latinski kvadrati reda n
1	1	1
2	1	2
3	1	12
4	4	576
5	56	161280
6	9408	812851200
7	16942080	61479419904000
8	535281401856	108776032459082956800
9	377597570964258816	5524751496156892842531225600
10	7580721483160132811489280	9982437658213039871725064756920320000
11	5363937773277371298119673540771840	776966836171770144107444346734230682311065600000

Za vsak n vsak izotopičen razred (OEIS A040082) vsebuje do (n!)³ latinskih kvadratov (natančno število se spreminja), vsak glavni razred (OEIS A003090) vsebuje 1, 2, 3 ali 6 izotopskih razredov.

Ekvivalenčni razredi latinskih kvadratov

n	glavni razredi	izotopski razredi
1	1	1
2	1	1
3	1	1
4	2	2
5	2	2
6	12	22
7	147	564
8	283657	1676267
9	19270853541	115618721533
10	34817397894749939	208904371354363006

Primeri

Primeri latinskih kvadratov vsakega glavnega razreda do reda 5.

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

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

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

Latinski kvadrati in matematične uganke

Priljubljena logična uganka sudoku je poseben primer latinskih kvadratov. Vsaka rešitev uganke sudoku je latinski kvadrat. V uganki Sudoku je še dodatna omejitev: manjši 3 × 3 kvadrati morajo spet vsebovati števke 1–9 (v običajni različici).

Vsak magični kvadrat je tudi latinski kvadrat, obratno pa ne velja.

Glej tudi

• grško-latinski kvadrat
• problem 36 častnikov

Zunanje povezave

• Latinski kvadrati v Javi (angleško)
• Neskončni latinski kvadrati (Java) (angleško)
• Weisstein, Eric Wolfgang, Latinski kvadrat na spletišču MathWorld (angleško)