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:

${\displaystyle {\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ű ${\displaystyle A}$ négyzetes mátrix, amelynek ${\displaystyle a_{i,j}}$ elemei az ${\displaystyle s_{1},s_{2},...,s_{n}}$ szimbólumok közül kerülnek ki és minden sora/oszlopa az ${\displaystyle s_{1},s_{2},...,s_{n}}$ elemek egy permutációja.

Példák

Példák kis latin négyzetekre:

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

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

${\displaystyle {\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
• ${\displaystyle \mathbb {Z} _{2}}$, kételemű ciklikus csoport
• ${\displaystyle \mathbb {Z} _{3}}$, háromelemű ciklikus csoport
• ${\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{2}}$, Klein-csoport
• ${\displaystyle \mathbb {Z} _{4}}$, négyelemű ciklikus csoport
• ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle L(n)}$ számából az összes n × n-es latin négyzet ${\displaystyle N(n)}$ száma meghatározható:

${\displaystyle N(n)=n!(n-1)!L(n)}$.

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

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

${\displaystyle {\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ű ${\displaystyle A}$ és ${\displaystyle 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 ${\displaystyle C}$ mátrix megfelelő helyére: ${\displaystyle c_{i,j}=(a_{i,j};b_{i,j})}$.

Ha a ${\displaystyle C}$ mátrix olyan, hogy az ${\displaystyle s_{1},s_{2},...,s_{n}}$ szimbólumokból képezhető ${\displaystyle n^{2}}$ számú rendezett pár mindegyike pontosan egyszer fordul elő a táblázatban, akkor az ${\displaystyle A}$ és ${\displaystyle B}$ latin négyzeteket ortogonálisnak, a ${\displaystyle 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:

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 ${\displaystyle 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 ${\displaystyle n\equiv 2{\pmod {4}}}$, vagyis ha ${\displaystyle 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

• 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 pasziá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^{[halott link]}

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