Latin négyzet

4×4-es kirakós

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 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,n)$ négyzetes mátrix, amelynek $a_{i,j}$ elemei az $S(s_1,s_2,..,s_n)$ szimbólumok é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 egy elemű csoport
• $\mathbb{Z}_2$, két elemű ciklikus csoport
• $\mathbb{Z}_3$, három elemű ciklikus csoport
• $\mathbb{Z}_2 \times \mathbb{Z}_2$, Klein-csoport
• $\mathbb{Z}_4$, négy elemű ciklikus csoport
• $\mathbb{Z}_5$, öt elemű ciklikus csoport
• egy öt elemű 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 sorrenben 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 latin négyzetek $L(n,n)$ számából az összes $A(n,n)$ latin négyzet $N(n,n)$ száma meghatározható:

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

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

n	1	2	3	4	5	6	7
L(n,n)	1	1	1	4	56	9408	16942080
N(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,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 $S(s_1,s_2,..,s_n)$ 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ája”.

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 on-line 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 és a Nemzetközi Biometrikus Társaság (International Biometric Society) logójában is.

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

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

Ha a $C(n,n)$ mátrix olyan, hogy az $S(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(n,n)$ és $B(n,n)$ négyzeteket ortogonálisnak, a $C(n,n)$ 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. Az Euler-négyzetet gyakran (helytelenül!) latin négyzetként említik.

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-ban) 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 alkimia 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-Ille de France, G2-Besançon, G3-Champagne, G4-Picardie) végzett. A kísérleti állatoknál négyféle takarmányozást (T1-burgonya, T2-takarmány ré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észtvevő 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égyszögben elrendezni, hogy minden sorban és minden oszlopban a tiszti rendfokozatok és az ezredek pontosan egyszer forduljanak elő.

A feladat általánosságban egyszerűen fogalmazható: 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. Az Euler szerint n=6 esetén a feladatnak nincs megoldása. Általánosabban az Euler-féle sejtés azt mondja, hogy ha $n \equiv 2 (mod 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 reprezentáns 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 Euler-féle sejtést több konkrét n-re sikerült bizonyítani, de az általános eset még mindig homályban maradt.

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

• Táblázat a lehetséges n-edrendű latin négyzetek számáról
• Táblázat az n-edrendű redukált latin négyzetek számáról
• A Diamond 16 Puzzle (4×4-es passziánsz)
• Encyclopaedia of Mathematics
• A sudoku játék
• Euler a latin és a latin-görög négyzetekről
• Interaktív Java Tool Euler-négyzet készítéséhez
• Anything but square: from magic squares to Sudoku
• MathWorld enciklopédia

Források

• 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