Latin négyzet

A latin négyzet egy n × n-es táblázat, amelynek soraiban és oszlopaiban n különböző elem (szimbólum) szerepel oly módon, hogy ezek mindegyike minden sorban és minden oszlopban pontosan egyszer fordul elő. Példák másod-, harmad- és negyedrendű latin négyzetre:

${\begin{bmatrix}\alpha &\beta \\\beta &\alpha \\\end{bmatrix}}\quad \quad {\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}}$

Itt pedig az arab számjegyek egy 10×10-es latin négyzetben:

Az elnevezés Leonhard Eulertől származik, aki latin betűket használt szimbólumokként.

A latin négyzet redukált, normalizált vagy standard alakú, ha első oszlopa és első sora megfelel a természetesen rendezett sorrendnek. A fenti háromszor hármas táblázat ilyen.

A véges csoportok, sőt a kvázicsoportok Cayley-táblái is latin négyzetet adnak.

Definíciója

Az n × n-es vagy n-edrendű latin négyzet egy olyan n-edrendű $A$ négyzetes mátrix, amelynek $a_{i,j}$ elemei az $s_{1},s_{2},...,s_{n}$ szimbólumok közül kerülnek ki és minden sora/oszlopa az $s_{1},s_{2},...,s_{n}$ elemek egy permutációja.

Példák

Példák kis latin négyzetekre:

{\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}}

Ezek rendre a következő csoportok Cayley-tábláit reprezentálják:

az egyelemű csoport
$\mathbb {Z} _{2}$ , kételemű ciklikus csoport
$\mathbb {Z} _{3}$ , háromelemű ciklikus csoport
$\mathbb {Z} _{2}\times \mathbb {Z} _{2}$ , Klein-csoport
$\mathbb {Z} _{4}$ , négyelemű ciklikus csoport
$\mathbb {Z} _{5}$ , ötelemű ciklikus csoport
egy ötelemű kvázicsoport

Redukált és izotóp latin négyzetek

Egy latin négyzetből akár a sorok, akár az oszlopok cseréjével, permutálásával ugyancsak latin négyzetet kapunk. A szimbólumok cseréje, permutálása szintén megtartja a definíció feltételeit. Az így kapott latin négyzeteket izotópoknak nevezzük, s ez az izotópia ekvivalencia osztályokba sorolja az összes azonos rendű elrendezést. Egy osztály reprezentálására azt a latin négyzetet választhatjuk, aminek első sorában és első oszlopában az $s_{1},s_{2},...,s_{n}$ elemek eredeti sorrendben vannak: Redukált vagy normalizált latin négyzet.

Ez az elrendezés bármelyik latin négyzetből kiindulva az oszlopok és a sorok cseréjével elérhető. Megfordítva, egy redukált latin négyzetből sor-oszlop permutációkkal előállítható az összes izotóp négyzet és csak ezek. A redukált n × n-es latin négyzetek $L(n)$ számából az összes n × n-es latin négyzet $N(n)$ száma meghatározható:

$N(n)=n!(n-1)!L(n)$ .

Néhány n-re ezek az értékek:

n	1	2	3	4	5	6	7
L(n)	1	1	1	4	56	9408	16942080
N(n)	1	2	12	576	161280	812851200	61479419904000

Nem ismerünk azonban olyan egzakt képletet, amivel a redukált négyzetek $L(n)$ száma meghatározható. A legjobb alsó és felső becslés (Lint és Wilson):

${\frac {\left(n!\right)^{2n}}{n^{n^{2}}}}\leq L(n)\leq \prod _{k=1}^{n}\left(k!\right)^{n/k}$ ,

de ezek nagy n-re nagymértékben eltávolodnak, „szétnyílik az olló”. Csak 1981-ben sikerült Szmetanjuknak bizonyítania, hogy a latin négyzetek száma n növekedésével együtt szigorúan növekszik.

Eredete, alkalmazása

A „latin négyzet” elnevezés Leonhard Eulertől származik, aki az elrendezés vizsgálatánál latin betűket használt a táblázat elemeiként. Euler több más vizsgált problémához hasonlóan matematikai fejtörőként is megfogalmazta az elrendezés egyik megoldhatatlan problémáját: „A 36 tiszt problémáját”.

A latin négyzet mint elrendezés, fontos szerepet játszik olyan kísérletek tervezésénél, amelyekben bizonyos hatások (öntözés, műtrágya, kezelési módszer, gyógyszer, takarmány stb.) együttes alkalmazásai képezik a vizsgálat tárgyát. A latin négyzet-elrendezés biztosítja az összes lehetséges kombináció kiválasztását és a kísérlet mellékhatásainak kiszűrését. Matematikán belül a kombinatorika, a véges geometria és a csoportelmélet területén, a hírközlésben a hibajavító kódok készítésénél használják.

A 19. századtól a kombinatorika több más feladatához (15-ös kombinet, átkelések, Euler-gráfok stb.) hasonlóan népszerű volt. Napjainkban a japáni eredetű szudoku és a KenKen is erre a feladatra épül. Az Interneten számos online puzzle is a latin vagy a latin-görög négyzetek előállítását tűzi ki célul. Egy részben kitöltött négyzet befejezése NP-teljes feladat.

A latin négyzet megjelenik a Kanadai Statisztikai Társaság (Statistical Society of Canada) címerében^[1] és a Nemzetközi Biometrikus Társaság (International Biometric Society) logójában is.^[2]

Latin-görög négyzet, ortogonalitás

Két azonos rendű $A$ és $B$ latin négyzetet egyesíthetünk oly módon, hogy az azonos helyen álló elemeikből képzett rendezett párokat helyezzük el a $C$ mátrix megfelelő helyére: $c_{i,j}=(a_{i,j};b_{i,j})$ .

Ha a $C$ mátrix olyan, hogy az $s_{1},s_{2},...,s_{n}$ szimbólumokból képezhető $n^{2}$ számú rendezett pár mindegyike pontosan egyszer fordul elő a táblázatban, akkor az $A$ és $B$ latin négyzeteket ortogonálisnak, a $C$ kompozíciójukat pedig latin-görög négyzetnek vagy Euler-négyzetnek nevezzük. Az előbbi elnevezést maga Euler használta, mivel a vizsgált ortogonális pár egyikében az elemeket latin betűkkel, a másikban görög betűkkel jelölte.

Története

Első ismert előfordulásai az első ezredforduló körüli évekből származó hindi és arab érmékről, amulettekről, szőttesekről, mozaik-padlókról ismertek. Vegyesen fordulnak elő a bűvös négyzetek, bűvös körök és más hasonló, varázserejűnek tartott elrendezésekkel együtt, amelyeknek a gyökerei az ókori szám-misztikára vezethetők vissza. Első irodalmi említése Ahmed ibn’Ali ibn Juszuf al-Buni (meghalt i. sz. 1225-ben) könyvében (Shams al-Ma’arif al-Kubra) található. Az elrendezéssel kapcsolatos hiedelmekre jellemzőek a közölt példákban szereplő elemek : a hét napjai, a bolygók neve, az alkímia néhány eleme stb.

Az Európába áramló keleti tudomány magával hozta a mágikus elrendezések „elméletét”. A 13. században Ramón Lull spanyol filozófus és mágus műveiben jelennek meg az átvett és az általa konstruált latin, latin-görög és bűvös négyzetek, háromszögek, körök s egyéb varázserejű elrendezések.

Első igazi tudományos előfordulása, pontosabban alkalmazása egy francia agronómushoz köthető. Francois Cretté de Palluel 1788-ban nyújtotta be értekezését Memoires d’Agriculture d’Economie et Domestique címmel a Societé Royale d’Agriculture á Paris–nak. Ebben beszámol egy takarmányozási kísérletről, amit az ország négy különböző vidékén (G1-Île-de-France, G2-Besançon, G3-Champagne, G4-Pikárdia) végzett. A kísérleti állatoknál négyféle takarmányozást (T1-burgonya, T2-takarmányrépa, T3-cukorrépa, T4-vegyes szemestakarmány) alkalmazott. Az állatok 2, 3, 4 és 5 hónapi súlynövekedéséből állapította meg az optimális takarmányt. A helyek és időtartamok eloszlásának megfelelő kombinációjával biztosította ezek szisztematikus hatásának közömbösítését. A munkájában magát a táblázatot nem rajzolta meg, csupán a kísérlet dokumentációjából rekonstruálható az alábbi elrendezés, ahol a mezőkben a hónapokban mért időtartamok szerepelnek:

Hónap	T1	T2	T3	T4
G1	2	5	4	3
G2	3	2	4	4
G3	4	3	2	5
G4	5	4	3	2

Euler is nagyjából ebben az időben foglalkozott a problémával, ami általa került a matematikusok látókörébe. A híressé vált „36 tiszt” problémát 1779-ben fogalmazta meg a Szentpétervári Tudományos Akadémia számára és 1782-ben tette közzé Recherches sur une nouvelle espèce de quarrés magiques címmel.

A 36 tiszt problémája

A feladat a következő: Egy díszszemlén a részt vevő 6 ezredből 6–6 különböző rendfokozatú tiszt vezénylésével kirendelt alegységeket úgy kell egy $6\times 6$ -os négyzetben elrendezni, hogy minden sorban és minden oszlopban a tiszti rendfokozatok és az ezredek pontosan egyszer forduljanak elő.

A feladat általánosságban is egyszerűen megfogalmazható: Elkészítendő egy n × n-es latin-görög négyzet vagy keressünk ortogonális párokat n-edrendű latin négyzetek között. Euler szerint n=6 esetén a feladatnak nincs megoldása. Általánosabban azt sejtette, hogy ha $n\equiv 2{\pmod {4}}$ , vagyis ha $n=4k+2$ alakú, akkor nincs megoldás. A legkisebb ilyen szám n=2, amire a sejtés a kevés lehetőség miatt direkt módon igazolható. A „36 tiszt problémájá”-ban szereplő n=6-ra csak 1900-ban talált bizonyítást Gaston Tarry. (Le problème des 36 officiers, C. R. Assoc. Franc. Av. Sci. 29, 1900, 170-203.). Azóta az általános esetről szóló Euler-féle sejtést Parker, Bose és Shrikhande megcáfolták, és kiderült, hogy n= 2 és 6 kivételével mindig létezik latin-görög négyzet.

A feladat n=4-re a következő pasziánszból ismert: A francia kártya négy színéhez (ezredek) tartozó négy különböző értékű (rendfokozatok) lapját kell egy 4 × 4–es alakzatban elrendezni úgy, hogy soronként és oszloponként se a színek, se a figurák ne ismétlődjenek. (A lehetséges elrendezések száma 16!= 20 922 789 888 000, és ebből csak 576 helyes.) Hasonlóan szórakoztató kirakóst kapunk öt különböző színre festett és öt különböző szimbólummal (pl. betűkkel) feliratozott zsetonokból.

További információk

Források

↑ Archivált másolat. [2009. december 17-i dátummal az eredetiből archiválva]. (Hozzáférés: 2010. február 12.)
↑ [1]

Kárteszi Ferenc: Bevezetés a véges geometriákba, Akadémiai Kiadó, Budapest 1972 (Disquisitiones Mathematicae Hungaricae 3)
Reinhardt, F. – Soeder, H.: SH atlasz-Matematika, Springer-Verlag, 1993
Ribnyikov, K. A.: A matematika története, Tankönyvkiadó, 1968
Sain Márton: Matematikatörténeti ABC, Nemzeti Tankönyvkiadó - Typotex, 1993
Andersen, Lars Døvling: The history of latin squares, Aalborg University, Dánia 2007

[1] Archivált másolat. [2009. december 17-i dátummal az eredetiből archiválva]. (Hozzáférés: 2010. február 12.)

[2] [1]

[1]

[2]