Lateinisches Quadrat

Grundbegriff und Darstellungen

Ein lateinisches Quadrat der Ordnung n ist ein quadratisches Schema mit n Zeilen und n Spalten. Jedes Feld enthält eines von n verschiedenen Symbolen. Jedes Symbol kommt in jeder Zeile und in jeder Spalte genau einmal vor. Als Symbole dienen häufig die Zahlen 1 bis n, Buchstaben oder Farben. In der modernen Kombinatorik wird ein lateinisches Quadrat meist als spezielle n×n-Matrix mit den Zahlen 1 bis n aufgefasst.

Für eine Matrix M=(M_{j,k}) kann die Eigenschaft mit folgenden Bedingungen geprüft werden: Für jede Zeile k gilt 1≤k≤n und Σ_{j=1}^n 2^{M_{j,k}-1}=2^n−1. Für jede Spalte j gilt 1≤j≤n und Σ_{k=1}^n 2^{M_{j,k}-1}=2^n−1.

Eine weitere Darstellung ist die Tripeldarstellung oder orthogonal array representation (OAR). Sie besteht aus n² verschiedenen Tripeln (r,s,z)∈{1,2,…,n}³. Dabei bezeichnen r die Zeile, s die Spalte und z das dort eingetragene Symbol. Genau dann liegt ein lateinisches Quadrat vor, wenn keine zwei Tripel in zwei Einträgen übereinstimmen.

Geometrisch kann man z als Höhe eines Quaders über dem Feld (r,s) deuten. Die jeweils obersten Würfel ergeben n² Einheitswürfel in einem größeren Würfel mit Kantenlänge n. Ein solches Muster gehört genau dann zu einem lateinischen Quadrat, wenn es bei Betrachtung in jeder der drei achsparallelen Richtungen lückenlos erscheint. Die OAR-Eigenschaft bleibt auch erhalten, wenn Zeilen-, Spalten- und Zeichennummern untereinander vertauscht werden.

Ein Beispiel der Ordnung 4 ist C=[[3,4,2,1],[4,3,1,2],[1,2,4,3],[2,1,3,4]]. Durch Vertauschen der Zeilen- und Zeichennummern entsteht D=[[4,3,1,2],[3,4,2,1],[1,2,4,3],[2,1,3,4]].

Konstruktion, Normalisierung und algebraische Bedeutung

Für jede Ordnung n lässt sich ein lateinisches Quadrat leicht konstruieren: Man trägt n verschiedene Symbole in eine erste Zeile ein. Jede weitere Zeile entsteht, indem die vorherige Zeile zyklisch um eins nach rechts verschoben wird; das äußerste rechte Symbol kommt links wieder hinzu. Eine Verschiebung nach links ist ebenfalls möglich. Beginnt man mit 1,2,…,n, erhält man ein reduziertes oder normalisiertes Quadrat: In der ersten Zeile und der ersten Spalte stehen die Symbole in natürlicher Reihenfolge. Jedes lateinische Quadrat kann durch Vertauschungen von Zeilen und Spalten normalisiert werden.

Die Anzahl aller lateinischen Quadrate der Ordnung n wird mit L(n) bezeichnet. Eine einfache Berechnungsformel ist nicht bekannt. Es gilt die klassische Abschätzung (n!)^{2n}/n^{n²} ≤ L(n) ≤ ∏_{k=1}^n (k!)^{n/k}. Die Werte L(n) bilden die OEIS-Folge A002860. Die Anzahl l(n) der reduzierten lateinischen Quadrate bildet A000315; zwischen beiden Zahlen besteht die Beziehung L(n)=n!·(n−1)!·l(n). Strukturell unterschiedliche Quadrate bis zur Ordnung 7 werden in A264603 erfasst.

Das zyklisch konstruierte Quadrat kann als Verknüpfungstafel der Restklassengruppe (ℤ/nℤ,+) interpretiert werden, wenn die Einträge um 1 verringert werden. Allgemeiner ist jedes lateinische Quadrat die Verknüpfungstafel einer endlichen Quasigruppe, also einer algebraischen Struktur, in der jede Zeile und jede Spalte einer Verknüpfungstafel jedes Element genau einmal enthält. Umgekehrt bestimmt jede endliche Quasigruppe eine Äquivalenzklasse lateinischer Quadrate.

Durch gleichartige Zeilen- und Spaltenpermutation π sowie eine Umnummerierung ρ der Symbole entstehen Matrizen N mit N_{π(j),π(k)}=ρ(M_{j,k}). Sie gehören zur selben Quasigruppe. Eine Quasigruppe ist genau dann kommutativ, wenn ihre Matrix symmetrisch ist, also M_{k,j}=M_{j,k}. Eine Loop ist eine Quasigruppe mit einem zugleich links- und rechtsneutralen Element e. Ordnet man e als erstes Element an, entsteht eine reduzierte Verknüpfungstafel.

Orthogonalität, MOLS und magische Quadrate

Zwei lateinische Quadrate Q und R derselben Ordnung n heißen orthogonal, wenn die n² Paare, die durch das Nebeneinanderschreiben ihrer Einträge entstehen, alle verschieden sind. Solche Quadrate werden auch Griechisch-Lateinische-Quadrate oder Euler-Quadrate genannt. Aus Q=[[3,2,1],[2,1,3],[1,3,2]] und R=[[2,3,1],[1,2,3],[3,1,2]] entsteht beispielsweise S=[[32,23,11],[21,12,33],[13,31,22]].

Eine Menge paarweise orthogonaler lateinischer Quadrate der Ordnung n kann höchstens n−1 Quadrate enthalten. Eine Liste mit n−1 solchen Quadraten heißt vollständig. Die größtmögliche Anzahl R(n) wird auch als Anzahl der MOLS (mutually orthogonal Latin squares) bezeichnet. Für n=2,3,4,5,6,7,8,9,11,13 sind die bekannten Werte 1,2,3,4,1,6,7,8,10,12. Für n=10 gilt R(10)≥2, möglicherweise R(10)=2, und für n=12 gilt R(12)≥5. Für n=0 und n=1 wird R(n)=∞ als Konvention angegeben.

Wichtige Ergebnisse sind: Ist n>4 und R(n)≥n−3, dann gilt R(n)=n−1. Für n>6 ist R(n)≥2, für n>52 ist R(n)≥4. Ist p eine Primzahl und r∈ℕ, dann gilt R(p^r)=p^r−1. Für hinreichend große n gilt R(n)≥n^{1/17}−2; daher wächst R(n) unbeschränkt. Für n,m≥3 gilt außerdem R(n·m)≥min(R(n),R(m)). Bis heute ist nicht bekannt, ob es eine natürliche Zahl n gibt, die keine Primzahlpotenz ist und für die R(n)=n−1 gilt.

Aus einem Griechisch-Lateinischen-Quadrat kann durch die bijektive Codierung (j,k)↦(j−1)·n+k ein Zahlenquadrat entstehen, dessen Zeilen- und Spaltensummen gleich sind. Beim Beispiel S entsteht [[8,6,1],[4,2,9],[3,7,5]] mit der magischen Summe s=15. Sind zusätzlich beide Diagonalsummen gleich dieser Summe, liegt ein magisches Quadrat vor.

Geometrie, Konstruktionen und Anwendungen

Eine vollständige Liste von n−1 paarweise orthogonalen lateinischen Quadraten der Ordnung n entspricht einer endlichen affinen Ebene der Ordnung n. Die Punkte sind die Paare (j,k) mit 1≤j,k≤n. Zwei Parallelenscharen bestehen aus den Zeilen und Spalten; jedes weitere lateinische Quadrat liefert eine Parallelenschar, deren Geraden aus den Feldern mit gleichem Symbol bestehen. Umgekehrt bestimmen die nicht zu den Achsen parallelen Scharen einer affinen Ebene paarweise orthogonale lateinische Quadrate. Daher gibt es für n≥2 genau dann eine projektive Ebene der Ordnung n, wenn es n−1 paarweise orthogonale lateinische Quadrate der Ordnung n gibt. Eine unvollständige Liste von m MOLS führt zu einem (m+2,n)-Netz.

Aus einem endlichen Ternärkörper (K,T,0,1) erhält man für jedes a∈K{0} die Quasigruppenverknüpfung x⋆_a y=T(a,y,x). Die zu verschiedenen a gehörenden Verknüpfungstafeln sind paarweise orthogonal. So entstehen stets n−1 MOLS der Ordnung n. Für K=ℤ/5ℤ gilt x⋆a y=x+a·y für a=1,2,3,4; daraus entstehen vier paarweise orthogonale lateinische Quadrate. Allgemein liefern endliche Körper 𝔽{p^r} jeweils p^r−1 MOLS der Ordnung p^r.

Das Vervollständigen eines teilweise ausgefüllten lateinischen Quadrats ist ein NP-vollständiges Problem. Ein Quadrat der Ordnung 9 mit der Zusatzbedingung, dass in jedem der neun 3×3-Teilquadrate alle Symbole genau einmal vorkommen, führt zum Sudoku.

Bei vier Politikern und vier Informatikern kann ein Quadrat der Ordnung 4 festlegen, welcher Politiker an welchem von vier Tagen welchen Informatiker besucht. Zeilen stehen für Politiker, Spalten für Informatiker und Symbole für Tage. Es gibt 576 mögliche Konstellationen.

In der statistischen Versuchsplanung wird ein lateinisches Quadrat als Blockanlage verwendet. In einem 4×4-Feld können beispielsweise vier Düngerkonzentrationen A, B, C und D so angeordnet werden, dass jede Konzentration in jeder Zeile und jeder Spalte einmal vorkommt. Dadurch lassen sich neben dem interessierenden Faktor zwei Blockfaktoren berücksichtigen, etwa Hangneigung und Bodentiefe.

Äquivalenzklassen und historische Entwicklung

Aus einem lateinischen Quadrat entstehen durch Transponieren, Permutieren von Zeilen oder Spalten, bijektives Umbenennen der Symbole sowie Spiegelungen weitere lateinische Quadrate. Diese Operationen führen zu verschiedenen Äquivalenzbegriffen.

Zwei Quadrate heißen parastroph, wenn ihre OAR-Tripel durch eine Permutation π∈S₃ der drei Einträge ineinander überführt werden. Eine parastrophe Klasse enthält 1, 2, 3 oder 6 verschiedene Quadrate. Zwei Quadrate heißen isotop, wenn sie durch Zeilen- und Spaltenpermutationen sowie bijektive Umbenennungen der Einträge auseinander hervorgehen. Die Kombination aus Parastrophie und Isotopie definiert die Hauptklassen. Jede Hauptklasse enthält 1, 2, 3 oder 6 Isotopieklassen.

Frühe lateinische Quadrate sind um 1000 n. Chr. im arabischen und indischen Kulturkreis nachweisbar. In der westlichen Mathematik untersuchte Leonhard Euler sie besonders intensiv. 1779 stellte er, veröffentlicht 1782, das Problem der 36 Offiziere: Zwei lateinische Quadrate der Ordnung 6 sollten orthogonal sein. Eine solche Lösung gibt es nicht; Euler fand jedoch eine Lösung der Ordnung 7. Choi Seok-jeong gab Anfang des 18. Jahrhunderts ein Beispiel orthogonaler Quadrate der Ordnung 9.

Euler vermutete, dass es für Ordnungen 4k+2 keine orthogonalen lateinischen Quadrate gebe. Gaston Tarry zeigte 1900 die Nicht-Existenz für n=6. Ernest Tilden Parker fand 1959 ein Gegenbeispiel für n=10; 1960 bewiesen Parker, Raj Chandra Bose und S. S. Shrikhande die Existenz orthogonaler lateinischer Quadrate für alle n≥10. Die maximale Zahl n−1 paarweise orthogonaler Quadrate wurde 1896 von E. H. Moore bewiesen. Die erste Verwendung eines lateinischen Quadrats in der Versuchsplanung erfolgte 1788 durch François Crettè de Palluel.