Lateinisches Quadrat

Ein lateinisches Quadrat ist ein quadratisches Schema mit $n$ Zeilen und $n$ Spalten, wobei jedes Feld mit einem von $n$ verschiedenen Symbolen belegt ist, so dass jedes Symbol in jeder Zeile und in jeder Spalte jeweils genau einmal auftritt. Die natürliche Zahl $n$ wird „Ordnung“ des lateinischen Quadrats genannt.

Ein lateinisches Quadrat der Ordnung 7 (Fenster im Gedenken an Ronald Aylmer Fisher am Gonville and Caius College, Cambridge)

Als Symbole werden häufig die Zahlen von $1$ bis $n$, oder $n$ verschiedene Buchstaben oder auch $n$ verschiedene Farben verwendet. Der Mathematiker Leonhard Euler befasste sich intensiv mit solchen Quadraten; als Symbolmenge benutzte er das lateinische Alphabet. Der Name lateinisches Quadrat geht darauf zurück.

In der modernen Kombinatorik und der diskreten Mathematik werden als Symbolmenge überwiegend die Zahlen von $1$ bis $n$, seltener die Zahlen von $0$ bis $n-1$ verwendet, und das Schema wird als spezielle $n\times n$-Matrix betrachtet.

Jedes lateinische Quadrat kann als Verknüpfungstafel (Cayley-Tafel) einer endlichen Quasigruppe aufgefasst werden, umgekehrt bestimmt jede endliche Quasigruppe eine Äquivalenzklasse von lateinischen Quadraten.

Zwei verschiedene lateinische Quadrate derselben Ordnung $n$ können orthogonal zueinander sein. In der synthetischen Geometrie werden bestimmten Mengen von paarweise orthogonalen lateinischen Quadraten der Ordnung $n$ endliche affine Ebenen zugeordnet. Daraus ergibt sich dort eine notwendige und hinreichende kombinatorische Bedingung für die Existenz von Ebenen der Ordnung $n$: Eine solche Ebene existiert genau dann, wenn es eine vollständige Liste paarweise orthogonaler Quadrate der Ordnung $n$ gibt.

Außerhalb der Mathematik im engeren Sinn werden lateinische Quadrate unter anderem in der agrarwissenschaftlichen Versuchsplanung als Blockanlagen und der statistischen Versuchsplanung angewendet.

Darstellung, Eigenschaften und Begriffe

Darstellung als Matrix

Ein lateinisches Quadrat der Ordnung $n$ ist eine quadratische $n\times n$ Matrix, deren sämtliche Einträge natürliche Zahlen von $1$ bis $n$ sind, und zwar so, dass in jeder Zeile und in jeder Spalte der Matrix jede dieser Zahlen genau einmal auftritt. Diese Eigenschaft lässt sich bei einer Matrix (zum Beispiel mit einem Computeralgebrasystem wie Maple) folgendermaßen testen: Für die Einträge $M_{j,k}$ der Matrix $M$ müssen folgende Gleichungen erfüllt sein:

• Für jede Zeile $k,\,1\leq k\leq n$ muss $\sum _{j=1}^{n}2^{M_{j,k}-1}=2^{n}-1$ und
• für jede Spalte $j,\,1\leq j\leq n$ muss $\sum _{k=1}^{n}2^{M_{j,k}-1}=2^{n}-1$ gelten.

Tripeldarstellung: OAR

Ein lateinisches Quadrat der Ordnung $n$ lässt sich auch als Menge $Q$ von $n^{2}$ verschiedenen Tripeln $(r,s,z)\in \{1,2,\ldots n\}^{3}$ darstellen. Dabei steht $r$ für die Nummer einer Zeile im lateinischen Quadrat, $s$ für die Nummer einer Spalte und $z$ für die dort im Quadrat stehende Zahl. Die Regel für lateinische Quadrate ist genau dann erfüllt, wenn keine zwei der Tripel in zwei Einträgen übereinstimmen. Diese Darstellung wird als orthogonal array representation (OAR) des lateinischen Quadrats bezeichnet.

Die OAR legt eine geometrische Interpretation für ein lateinisches Quadrat nahe: Man kann die Zahl in einer Zelle des lateinischen Quadrates als Höhe eines Quaders auffassen, der auf dieser Zelle als Grundfläche errichtet werden soll. Damit wird aus dem lateinischen Quadrat ein räumliches Säulendiagramm – vergleiche die Abbildung zu dem Beispiel unten.

In dem Bild ist auch eine verwandte Interpretation des lateinischen Quadrates der Ordnung $n$ zu erkennen: Füllt man von den Säulen des Säulendiagramms nur jeweils den Würfel an der Spitze, dann erhält man ein dreidimensionales Bild aus $n^{2}$ achsparallelen Einheitswürfeln in einem größeren achsparallelen Würfel mit der Kantenlänge $n$. Der Teilwürfel mit den Gitterkoordinaten $(r,s,z)$ ist genau dann „gefüllt“, wenn $(r,s,z)$ zu der OAR des lateinischen Quadrates gehört. Eine Anordnung von $n^{2}$ Teilwürfeln in einem solchen Würfel der Kantenlänge $n$ gehört genau dann zu einem lateinischen Quadrat der Ordnung $n$, wenn der große Würfel in den drei achsparallelen Richtungen betrachtet durch die Teilwürfel undurchsichtig ist, also bei der Projektion in einer Achsrichtung lückenlos gefüllt erscheint.

Die Tripel der OAR-Darstellung können als Raumkoordinaten oder als Höhen von Säulen auf dem lateinischen Quadrat aufgefasst werden. Bei diesem Bild sind der Übersicht wegen nur die erste und die letzte Spalte (s=1 und s=4) des lateinischen Quadrates der Ordnung 4 (rote Zahlen auf der Grundfläche) als Säulen dargestellt. Der Würfel an der Spitze dieser Säulen ist jeweils farblich hervorgehoben.

Diese Interpretation macht anschaulich, dass die OAR eines lateinischen Quadrates nicht nur bei Vertauschen der Zeilen- mit den Spaltennummern (einer Transposition in der Matrixdarstellung) zur OAR eines lateinischen Quadrates wird, sondern sogar, wenn alle Zeichennummern mit den Zeilennummern oder den Spaltennummern vertauscht werden.

Beispiel

Das Beispiel in der Abbildung rechts zeigt das erste lateinische Quadrat C unten, das zweite, D, entsteht daraus, indem man die $r$- mit der $z$-Achse vertauscht. Wenn man im ersten Quadrat C die $s$- mit der $z$-Achse vertauscht, entsteht ebenfalls das Quadrat D, denn dessen Matrix ist symmetrisch.

$C=\left[{\begin{array}{cccc}3&4&2&1\\4&3&1&2\\1&2&4&3\\2&1&3&4\end{array}}\right];\;D=\left[{\begin{array}{cccc}4&3&1&2\\3&4&2&1\\1&2&4&3\\2&1&3&4\end{array}}\right]$

Die Tripeldarstellungen lauten

${\begin{array}{rllll}Q_{C}=\{&(1,1,3),&(1,2,4),&(1,3,2),&(1,4,1),\\&(2,1,4),&(2,2,3),&(2,3,1),&(2,4,2),\\&(3,1,1),&(3,2,2),&(3,3,4),&(3,4,3),\\&(4,1,2),&(4,2,1),&(4,3,3),&(4,4,4)\quad \}\end{array}}$

bzw.

${\begin{array}{rllll}Q_{D}=\{&(1,3,1),&(1,4,2),&(1,2,3),&(1,1,4),\\&(2,4,1),&(2,3,2),&(2,1,3),&(2,2,4),\\&(3,1,1),&(3,2,2),&(3,4,3),&(3,3,4),\\&(4,2,1),&(4,1,2),&(4,3,3),&(4,4,4)\quad \}\end{array}}$

Anzahl der lateinischen Quadrate

Die Anzahlen $L(n)$ lateinischer Quadrate der Ordnung $n=1,2,3,\ldots$, bilden Folge A002860 in OEIS. Es ist keine einfach zu berechnende Formel für die Folge $L(n)$ bekannt. Die besten bekannten unteren und oberen Schranken für große Ordnungen $n$ sind noch weit auseinander. Eine klassische Abschätzung lautet:

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

Die Anzahlen der strukturell unterschiedlichen lateinischen Quadrate (d. h. die Quadrate sind nicht durch Drehung, Spiegelung, oder Permutation der Symbole identisch zu machen) bis zur Ordnung 7 bilden Folge A264603 in OEIS.

Reduzierte lateinische Quadrate

Ein lateinisches Quadrat heißt „reduziert“ oder auch „normalisiert“, wenn in der 1. Zeile und in der 1. Spalte die $n$ verschiedenen Symbole in ihrer „natürlichen Reihenfolge“ stehen. In der Tripeldarstellung mit Zahlen als Symbolen bedeutet das: $\{(1,1,1);(1,2,2);\ldots (1,n,n)\}\subset Q$ für die erste Zeile und $\{(1,1,1);(2,1,2);\ldots (n,1,n)\}\subset Q$ für die erste Spalte. Die Normalisierung eines beliebigen lateinischen Quadrates kann immer durch Vertauschungen von Zeilen und Spalten erreicht werden. Das Quadrat der Ordnung 3 in den Beispielen unten wird durch Vertauschen der 2. mit der dritten Zeile normalisiert, das Quadrat der Ordnung 4 ist bereits reduziert.

Die Anzahlen $l(n)$ reduzierter lateinischer Quadrate der Ordnung $n=1,2,3,\ldots$ bilden Folge A000315 in OEIS. Für die Anzahl aller lateinischen Quadrate $L(n)$ gilt $L(n)=n!\cdot (n-1)!\cdot l(n).$

Beispiele

Lateinische Quadrate der Ordnung 3 bzw. 4 in der Matrixdarstellung:

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

Die Tripeldarstellung des linken Quadrates lautet: $\{(1,1,1);(1,2,2);(1,3,3);(2,1,3);(2,2,1);(2,3,2);(3,1,2);(3,2,3);(3,3,1)\}$. Würde man dort in der ersten Zeile die Zahlen 1 und 2 vertauschen, so würden das Tripel $(1,1,2)$ (1. Zeile, 1. Spalte enthält 2) und das Tripel $(3,1,2)$ (3. Zeile, 1. Spalte enthält 2) an zwei Stellen (Spalte und Zeichen) übereinstimmen und das Quadrat wäre kein lateinisches Quadrat mehr.

Es lässt sich leicht ein lateinisches Quadrat für eine beliebige gegebene Ordnung $n$ angeben: Dazu verteilt man $n$ verschiedene Symbole beliebig auf die erste Zeile des Quadrats. Die folgenden Zeilen füllt man nun sukzessive aus, indem man die jeweils vorangehende Zeile um eins nach rechts verschoben übernimmt. Das äußerste rechte Symbol der vorangehenden Zeile würde dabei aus dem Quadrat hinausfallen; stattdessen trägt man es in der neuen Zeile ganz links ein.

Das Beispiel der Ordnung 3 ist auf diese Art konstruiert, beim Beispiel der Ordnung 4 wurde statt der Verschiebung nach rechts in jeder Zeile nach links zyklisch vertauscht. Startet man bei dieser Konstruktion wie im gezeigten Beispiel mit einer sortierten ersten Zeile mit den Zahlen $1,2,\ldots n$, dann erhält man stets ein reduziertes lateinisches Quadrat, das sich als Verknüpfungstabelle der Restklassengruppe $\left(\mathbb {Z} /n\mathbb {Z} ,+\right)$ interpretieren lässt. Dazu müssen die eingetragenen Zahlen alle um 1 verringert werden.

Orthogonale lateinische Quadrate und MOLS

Zwei lateinische Quadrate $Q$ und $R$ heißen orthogonal (sie werden auch als Griechisch-Lateinische-Quadrate oder Euler-Quadrate bezeichnet), wenn keine zwei von den $n^{2}$ Paaren übereinstimmen, die entstehen, wenn man die Einträge von $Q$ und $R$ jeweils nebeneinander in ein neues quadratisches Schema $S$ schreibt. In Matrixdarstellung:

$Q:={\begin{bmatrix}3&2&1\\2&1&3\\1&3&2\end{bmatrix}}\quad R:={\begin{bmatrix}2&3&1\\1&2&3\\3&1&2\end{bmatrix}}\longrightarrow S={\begin{bmatrix}32&23&11\\21&12&33\\13&31&22\end{bmatrix}}$

Die hier zur Matrix $S$ kombinierten lateinischen Quadrate $Q$ und $R$ sind orthogonal. In diesem Fall nennt man das durch $S$ repräsentierte Quadrat ein griechisch-lateinisches Quadrat. Die Anzahlen der Paare von orthogonalen lateinischen Quadraten der Ordnung $n=1,2,3,\ldots$ bilden Folge A072377 in OEIS.

Für die Anwendung in der Geometrie ist folgender Satz wichtig:

Sei ${\mathfrak {L}}$ eine Menge von lateinischen Quadraten, der Ordnung $n\geq 2$, mit der Eigenschaft, dass zwei verschiedene lateinische Quadrate $L_{1},L_{2}\in {\mathfrak {L}}$ stets zueinander orthogonal sind. Dann enthält ${\mathfrak {L}}$ höchstens $n-1$ Elemente.

(vermutete) maximale Anzahlen von MOLS

Ordnung n	R(n)
0	$\infty$
1	$\infty$
2	1
3	2
4	3
5	4
6	1
7	6
8	7
9	8
10	${}\geq 2\;({}=2?)$
11	10
12	${}\geq 5$
13	12

Eine Liste von $n-1$ paarweise orthogonalen lateinischen Quadraten der Ordnung $n$ wird als vollständig bezeichnet. Die Folge $R(n)$ der größtmöglichen Anzahlen von paarweise orthogonalen lateinischen Quadraten (MOLS = mutually orthogonal Latin squares) der Ordnung $n$ ist Folge A001438 in OEIS, was über die Werte bis $n=13$ bekannt ist, zeigt die Tabelle rechts, die Werte für 0 und 1 sind Konvention. Es gilt:

• Ist $n>4$ und $R(n)\geq n-3$, dann ist $R(n)=n-1$, denn eine Liste von $n-3\geq 2$ paarweise orthogonalen lateinischen Quadraten lässt sich stets vervollständigen.
• Für $n>6$ ist $R(n)\geq 2$, für $n>52$ ist $R(n)\geq 4.$
• Ist $p$ eine Primzahl und $r\in \mathbb {N}$, dann ist $R(p^{r})=p^{r}-1$.
• 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.
• Für hinreichend große $n$ ist $R(n)\geq n^{1/17}-2$, also ist $\lim _{n\to \infty }R(n)=\infty$.
• Es gilt für $n,m\geq 3$ immer $R(n\cdot m)\geq \min(R(n),R(m))$, denn aus einer Liste von $t$ MOLS der Ordnung $n$ und einer Liste von t MOLS der Ordnung $m$ lässt sich stets eine Liste von $t$ MOLS der Ordnung $n\cdot m$ herstellen. Das Verfahren wird hier an einem trivialen Beispiel demonstriert:

$A={\begin{bmatrix}{\color {Red}1}&{\color {Blue}2}\\{\color {Green}2}&{\color {Cyan}1}\end{bmatrix}}{\mathrel {\widehat {=}}}{\begin{bmatrix}{\color {Red}0}&{\color {Blue}1}\\{\color {Green}1}&{\color {Cyan}0}\end{bmatrix}},\quad B={\begin{bmatrix}1&2&3\\2&3&1\\3&1&2\\\end{bmatrix}}$

$\longrightarrow {\begin{bmatrix}{\color {Red}0}\cdot 3+1&{\color {Red}0}\cdot 3+2&{\color {Red}0}\cdot 3+3&{\color {Blue}1}\cdot 3+1&{\color {Blue}1}\cdot 3+2&{\color {Blue}1}\cdot 3+3\\{\color {Red}0}\cdot 3+2&{\color {Red}0}\cdot 3+3&{\color {Red}0}\cdot 3+1&{\color {Blue}1}\cdot 3+2&{\color {Blue}1}\cdot 3+3&{\color {Blue}1}\cdot 3+1\\{\color {Red}0}\cdot 3+3&{\color {Red}0}\cdot 3+1&{\color {Red}0}\cdot 3+2&{\color {Blue}1}\cdot 3+3&{\color {Blue}1}\cdot 3+1&{\color {Blue}1}\cdot 3+2\\{\color {Green}1}\cdot 3+1&{\color {Green}1}\cdot 3+2&{\color {Green}1}\cdot 3+3&{\color {Cyan}0}\cdot 3+1&{\color {Cyan}0}\cdot 3+2&{\color {Cyan}0}\cdot 3+3\\{\color {Green}1}\cdot 3+2&{\color {Green}1}\cdot 3+3&{\color {Green}1}\cdot 3+1&{\color {Cyan}0}\cdot 3+2&{\color {Cyan}0}\cdot 3+3&{\color {Cyan}0}\cdot 3+1\\{\color {Green}1}\cdot 3+3&{\color {Green}1}\cdot 3+1&{\color {Green}1}\cdot 3+2&{\color {Cyan}0}\cdot 3+3&{\color {Cyan}0}\cdot 3+1&{\color {Cyan}0}\cdot 3+2\end{bmatrix}}={\begin{bmatrix}{\color {Red}1}&{\color {Red}2}&{\color {Red}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}\\{\color {Red}2}&{\color {Red}3}&{\color {Red}1}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}4}\\{\color {Red}3}&{\color {Red}1}&{\color {Red}2}&{\color {Blue}6}&{\color {Blue}4}&{\color {Blue}5}\\{\color {Green}4}&{\color {Green}5}&{\color {Green}6}&{\color {Cyan}1}&{\color {Cyan}2}&{\color {Cyan}3}\\{\color {Green}5}&{\color {Green}6}&{\color {Green}4}&{\color {Cyan}2}&{\color {Cyan}3}&{\color {Cyan}1}\\{\color {Green}6}&{\color {Green}4}&{\color {Green}5}&{\color {Cyan}3}&{\color {Cyan}1}&{\color {Cyan}2}\\\end{bmatrix}}$

Magische Quadrate

Nach seiner Konstruktion sind bei einem griechisch-lateinischen Quadrat der Ordnung n, wenn man die Zahlenpaare in geeigneter Weise bijektiv zu aufeinanderfolgenden natürlichen Zahlen umkodiert – z. B. $(j,k)\mapsto (j-1)\cdot n+k$ – alle Zeilensummen und Spaltensummen gleich, zum Beispiel kann man dem Quadrat S so das Quadrat ${\hat {S}}$

$S={\begin{bmatrix}32&23&11\\21&12&33\\13&31&22\end{bmatrix}}\quad \longrightarrow \quad {\hat {S}}={\begin{bmatrix}8&6&1\\4&2&9\\3&7&5\end{bmatrix}}$

zuordnen, bei dem jede Zeile und jede Spalte die magische Summe $s=15$ hat.

Ist in einem solchen Quadrat zusätzlich noch die Summe der beiden Diagonalen gleich der Zeilen- und Spaltensumme, dann spricht man von einem magischen Quadrat.

Anwendungen

Algebra: Lateinische Quadrate und Verknüpfungstafeln

Verknüpfungstafel der zyklischen Gruppe C₅ als lateinisches Quadrat in Farbe. Das neutrale Element ist schwarz. Farbige Verknüpfungstafeln werden in der Online-Enzyklopädie zur Mathematik MathWorld verwendet, wie auch solche in Graustufen

Die erste Abbildung links zeigt die vollständige Verknüpfungstafel der Gruppe $C_{5}=\left(\mathbb {Z} /5\mathbb {Z} ,+\right)$:

$+$ 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3

$\longrightarrow \left[{\begin{array}{ccccc}0&1&2&3&4\\1&2&3&4&0\\2&3&4&0&1\\3&4&0&1&2\\4&0&1&2&3\end{array}}\right]\longrightarrow \left[{\begin{array}{ccccc}1&2&3&4&5\\2&3&4&5&1\\3&4&5&1&2\\4&5&1&2&3\\5&1&2&3&4\end{array}}\right]$

In der mittleren Matrix wurden die Zeilen- und Spaltenüberschriften, also die mit „+“ verknüpften Gruppenelemente, fortgelassen, damit stellt diese Matrix ein lateinisches Quadrat mit der Symbolmenge $\{0,1,2,3,4\}$, die für Restklassen üblich ist, dar. Addiert man zu jedem Eintrag 1, so entsteht ein lateinisches Quadrat mit der Standardsymbolmenge $\{1,2,3,4,5\}$. Hier ist dieses lateinische Quadrat normalisiert, weil die Gruppenelemente der Gruppe $C_{5}$ für die Verknüpfungstabelle in ihrer „natürlichen Anordnung“ als Vielfache des erzeugenden Elementes 1 angeordnet waren und diese Gruppe zyklisch ist.

Dabei muss beachtet werden, dass für die Elemente einer Gruppe oder Quasigruppe im Allgemeinen keine bestimmte Anordnung ausgezeichnet werden kann: Ist $S_{n}$ die symmetrische Gruppe auf $n$ Elementen, dann wird durch eine Permutation $\pi \in S_{n}$, die nacheinander auf die Zeilen und die Spalten der Verknüpfungstabelle (samt ihren Zeilen- bzw. Spaltenüberschriften) angewendet wird, aus der ursprünglichen Tabelle (links) eine andere gültige Verknüpfungstabelle der gleichen Gruppe, dabei ändert sich auch das der Gruppe zugeordnete lateinische Quadrat (rechts).

Formal und allgemeiner gilt: Ist $M=(M_{j,k})$ ein lateinisches Quadrat der Ordnung $n$ in der Matrixdarstellung, dann existiert eine Quasigruppe mit $n$ Elementen, die – bei geeigneter Anordnung und Nummerierung ihrer Elemente – die Matrix $(M_{j,k})$ als Inhalt ihrer Verknüpfungstabelle hat. Genau die lateinischen Quadrate $N=(N_{j,k})$ die durch eine gleichartige Zeilen- und Spaltenpermutation $\pi \in S_{n}$ und eine „Umnummerierung“ $\rho \in S_{n}$ aus $M=(M_{j,k})$ hervorgehen, für die also $N_{\pi (j),\pi (k)}=\rho \left(M_{j,k}\right)\,(1\leq j,k\leq n)$ gilt, können als Verknüpfungstabellen dieser Quasigruppe aufgefasst werden.

• Wählt man die Anordnung der Elemente einer endlichen Loop $L$, also einer Quasigruppe mit einem zugleich links- und rechtsneutralen Element $e$, so, dass $e$ als erstes Element in der Verknüpfungstafel auftritt und ordnet den Elementen in ihrer ansonsten beliebigen Anordnung der Zeile nach die Zahlen $1,2,\ldots \#L$ zu, dann ist der Inhalt ihrer Verknüpfungstafel, mit den zugeordneten natürlichen Zahlen geschrieben, ein reduziertes lateinisches Quadrat der Ordnung $\#L$. (Die Zahl $\#L$ steht für die Anzahl der Elemente von $L$).
• Eine Quasigruppe, die das lateinische Quadrat $M=(M_{j,k})$ der Ordnung $n$ als Inhalt ihrer Verknüpfungstafel hat, ist genau dann kommutativ, wenn die Matrix $(M_{j,k})$ symmetrisch ist, wenn also $M_{k,j}=M_{j,k}\,(1\leq j,k\leq n)$ gilt. Bei einer kommutativen Quasigruppe kann stets eine Nummerierung der Elemente gewählt werden, durch die der Inhalt der Multiplikationstabelle ein reduziertes lateinisches Quadrat ist. Dabei ist zu beachten, dass hier nur dann die erste Zeile des Quadrates in Übereinstimmung mit den Spaltenüberschriften der Verknüpfungstafel gebracht werden kann – und damit zugleich die erste Spalte mit den Zeilenüberschriften – wenn die Quasigruppe eine Loop ist.

Geometrie: Orthogonale lateinische Quadrate und endliche Ebenen

Aus einer vollständigen Liste ${\mathfrak {L}}=\{L_{1},L_{2},\ldots L_{n-1}\}$ von paarweise orthogonalen lateinischen Quadraten der Ordnung $n$ lässt sich eine endliche affine Ebene der Ordnung $n$ konstruieren und umgekehrt. Dabei geht man so vor:

• Die Punktmenge besteht aus den Paaren natürlicher Zahlen von 1 bis $n$:

${\mathcal {P}}=\{(j,k):1\leq j,k\leq n\}.$

• Jedes lateinische Quadrat $L_{i}\in {\mathfrak {L}},\;(1\leq i\leq n-1)$ bestimmt eine Parallelenschar $R_{i}$ der Ebene:
• Die Parallelenschar $R_{i}=\{g_{i,m}:1\leq m\leq n-1\}$ besteht aus den Geraden

$g_{i,m}=\{(j,k):\,1\leq j,k\leq n\,\land \,(L_{i})_{j,k}=m\}.$

• Dazu kommen zwei „Achsrichtungen“, $R_{0}=\{g_{0,m}:1\leq m\leq n\}$ und $R_{n}=\{g_{n,m}:1\leq m\leq n\}$ mit den Geraden

$g_{0,m}=\{(j,m):1\leq j\leq n\}\quad \mathrm {bzw.} \quad g_{n,m}=\{(m,k):1\leq k\leq n\}.$

• Die Geradenmenge ist die Vereinigungsmenge der so definierten Parallelenscharen: ${\mathcal {G}}=\bigcup _{i=0}^{n}R_{i}$.

Umgekehrt kann man in einer endlichen affinen Ebene der Ordnung n ein affines Koordinatensystem $(O,E_{1},E_{2})$ wählen und den Punkten auf der ersten Achse, also den Ternärkörperelementen über eine – bis auf das Urbild n des Ursprungs O beliebige – Bijektion $\beta :\{1,2,\ldots n\}\rightarrow K=OE_{1}$ Zahlen als „kombinatorische Koordinaten“ zuordnen, so dass

$K=OE_{1}=\{\beta (1),\beta (2),\beta (3),\ldots \beta (n)=O\}$ gilt.

Damit hat man für jeden Punkt der Ebene über die auf die Punktbasis $(O,E_{1},E_{2})$ bezogene Koordinatendarstellung $(x,y)\in K^{2}=(OE_{1})^{2}$ ein eindeutiges Zahlenpaar $(\beta ^{-1}(x),\beta ^{-1}(y))=(j,k)\in \{1,2,\ldots n\}^{2}$. Jede der $n-1$ Parallelenscharen außer den zwei Scharen parallel zu den Achsen bestimmt damit wie oben beschrieben ein lateinisches Quadrat und die so bestimmten Quadrate sind paarweise orthogonal. Ausgedrückt durch die – ebenfalls durch die Liste der orthogonalen lateinischen Quadrate bestimmte – Ternärverknüpfung T haben die Geraden dann die Geradengleichungen:

• $g_{0,m}:\;y=\beta (m)\;(1\leq m\leq n)$,
• $g_{n,m}:\;T(O,y,x)=x=\beta (m)\;(1\leq m\leq n)$ und
• $g_{i,m}:\;T(\beta (i),y,x)=\beta (m)\Leftrightarrow (L_{i})_{j,k}=m\land \beta (j)=x\land \beta (k)=y\;(1\leq m\leq n,1\leq i\leq n-1).$

Weil jede endliche affine Ebene der Ordnung $n$ eine projektive Ebene der gleichen Ordnung als projektiven Abschluss besitzt und jede endliche projektive Ebene so geschlitzt werden kann, dass eine endliche affine Ebene der gleichen Ordnung entsteht, gilt:

Zu jedem $n\geq 2$ gibt es genau dann eine projektive Ebene der Ordnung $n$, wenn es $n-1$ paarweise orthogonale lateinische Quadrate der Ordnung $n$ gibt.

Wenn man die hier beschriebene Konstruktion mit einer unvollständigen Liste von $m$ MOLS durchführt, erhält man eine Inzidenzstruktur mit $n$ Punkten auf jeder Geraden und $m+2<n+1$ Parallelenscharen, also ein sogenanntes $(m+2,n)$-Netz.

Konstruktion von orthogonalen lateinischen Quadraten aus Ternärkörpern

Ist $(K,T,0,1)$ ein endlicher Ternärkörper, dann wird $K$ für jedes $a\in K\setminus \{0\}$ durch die Verknüpfung $x\star _{a}y=T(a,y,x)$ zu einer Quasigruppe $(K,\star _{a})$. Bei gleicher Anordnung der Elemente von $K$ für die Multiplikationstabellen sind die lateinischen Quadrate zu zwei solchen Verknüpfungen $\star _{a},\star _{b}$ bei unterschiedlichen Faktoren $a\neq b;\,a,b\in K\setminus \{0\}$ stets orthogonal zueinander. So erhält man durch einen Ternärkörper der Ordnung $n$ stets eine vollständige Liste von $n-1$ paarweise orthogonalen lateinischen Quadraten.

Beispiele

Der Restklassenkörper $K=\mathbb {Z} /5\mathbb {Z}$ ist ein Ternärkörper. Die Inhalte der Multiplikationstabellen für die oben beschriebenen Quasigruppenverknüpfungen $\star _{a},a\in \{1,2,3,4\}$ – da $K$ ein Körper ist, gilt hier $x\star _{a}y=T(a,y,x)=x+a\cdot y$ – lauten:

$\left[{\begin{array}{ccccc}0&1&2&3&4\\1&2&3&4&0\\2&3&4&0&1\\3&4&0&1&2\\4&0&1&2&3\end{array}}\right],\left[{\begin{array}{ccccc}0&2&4&1&3\\1&3&0&2&4\\2&4&1&3&0\\3&0&2&4&1\\4&1&3&0&2\end{array}}\right],\left[{\begin{array}{ccccc}0&3&1&4&2\\1&4&2&0&3\\2&0&3&1&4\\3&1&4&2&0\\4&2&0&3&1\end{array}}\right],\left[{\begin{array}{ccccc}0&4&3&2&1\\1&0&4&3&2\\2&1&0&4&3\\3&2&1&0&4\\4&3&2&1&0\end{array}}\right].$

Für die Standardnotation muss darin noch 0 durch 5 ersetzt werden, dann hat man damit eine Menge von 4 paarweise orthogonalen lateinischen Quadraten erzeugt. Analog lassen sich für jede Primzahlpotenz $p^{r}$ über die entsprechenden Quasigruppenverknüpfungen $\star _{a},a\in \mathbb {F} _{p^{r}}\setminus \{0\}$ im endlichen Körper $\mathbb {F} _{p^{r}}$ immer $p^{r}-1$ paarweise orthogonale lateinische Quadrate bestimmen.

Jedes dieser lateinischen Quadrate beschreibt dann die Inzidenzrelation in einer der $p^{r}+1$ Parallelenscharen der affinen Ebene über $\mathbb {F} _{p^{r}}$ wie im vorigen Abschnitt dargestellt.

Mathematische Rätsel

• Die Frage, ob sich ein teilweise gefülltes Quadrat zu einem lateinischen Quadrat vervollständigen lässt, ist in der Sprache der Komplexitätstheorie ein NP-vollständiges Problem.
• Ein lateinisches Quadrat der Ordnung 9 mit der Zusatzbedingung, dass in der Aufteilung in neun $3\times 3$-Quadrate in jedem dieser Quadrate alle Symbole jeweils genau einmal auftreten, führt zu dem Zahlenrätsel Sudoku.

Besuche von Politikern und Informatikern

4 Politiker wollen 4 Informatiker besuchen. Jeder Politiker besucht an jedem von 4 Tagen genau einen Informatiker. Jeder Informatiker hat an jedem der 4 Tage genau einen Politiker zu Besuch. Nach den 4 Tagen hat jeder Politiker jeden Informatiker genau einmal besucht.

Dieser Ablauf kann mit einem lateinischen Quadrat der Ordnung 4 dargestellt werden. Die Zeilen stellen die Politiker, die Spalten stellen die Informatiker und die Farben stellen die Tage dar. Die Anzahl der Möglichkeiten für die Konstellationen der Besuche an den 4 Tagen ist gleich der Anzahl der lateinischen Quadrate der Ordnung 4 (Folge A002860 in OEIS). Es gibt also 576 mögliche Konstellationen.

		Informatiker
		I1	I2	I3	I4
Politiker	P1	Tag 3	Tag 4	Tag 2	Tag 1
	P2	Tag 4	Tag 3	Tag 1	Tag 2
	P3	Tag 1	Tag 2	Tag 4	Tag 3
	P4	Tag 2	Tag 1	Tag 3	Tag 4

Statistische Versuchsplanung

Ein Agrarwissenschaftler möchte herausfinden, welche Düngerkonzentration die Erntemenge seiner Nutzpflanzen maximiert. Dazu unterteilt er sein Feld in vier mal vier einzelne Bereiche. In jedem der 16 Bereiche wird eine der vier Düngerkonzentrationen $A$, $B$, $C$ oder $D$ mit $D-C=C-B=B-A>0$ verwendet. Allerdings sind die Anbaubedingungen auf den 16 Bereichen inhomogen. In $x$-Richtung nimmt das Gefälle immer weiter zu, während in $y$-Richtung der Boden immer tiefgründiger wird. Die beiden Blockfaktoren Hangneigung und Gründigkeit können neben der Düngerkonzentration ebenfalls Einfluss auf den Ernteertrag nehmen, worauf im Versuchsplan Rücksicht genommen werden muss. Bei zwei Blockfaktoren und einem interessierenden Faktor eignet sich ein lateinisches Quadrat als Versuchsplan. Jeder der drei Faktoren weist vier Faktorstufen auf, womit in R der folgende Versuchsplan mit der Funktion design.lsd aus dem Paket agricolae erzeugt wird:

Bereich	Zeile (Hangneigung)	Spalte (Gründigkeit)	Düngerkonzentration
1	1	1	A
2	1	2	C
3	1	3	D
4	1	4	B
5	2	1	C
6	2	2	A
7	2	3	B
8	2	4	D
9	3	1	B
10	3	2	D
11	3	3	A
12	3	4	C
13	4	1	D
14	4	2	B
15	4	3	C
16	4	4	A

	1	2	3	4
1	A	C	D	B
2	C	A	B	D
3	B	D	A	C
4	D	B	C	A

Äquivalenzklassen lateinischer Quadrate

Durch viele unterschiedliche Transformationen, die man auf ein lateinisches Quadrat anwenden kann, erhält man ein neues lateinisches Quadrat:

1. Man kann das Quadrat (in der Matrixschreibweise) an der Hauptdiagonalen spiegeln, die Matrixdarstellung also transponieren,
2. man kann die Zeilen und/oder Spalten des lateinischen Quadrates permutieren,
3. man kann die eingetragenen Zahlsymbole bijektiv umbenennen,
4. man kann das Quadrat „von unten nach oben“ lesen oder von „rechts nach links“...

Die in 4. genannten Transformationen sind Spezialfälle der Zeilen- bzw. Spaltenpermutationen.

Für die Anwendung wichtig und für das Zählen der möglichen lateinischen Quadrate einer festen Ordnung nützlich sind die nachfolgend beschriebenen Mengen von Transformationen, durch die jeweils eine Äquivalenklasseneinteilung auf der Menge aller lateinischen Quadrate der Ordnung $n$ (mit Symbolen aus $\{1,2,\ldots ,n\}$) eingeführt wird.

Parastrophie

Zwei lateinische Quadrate $Q_{1},Q_{2}$ heißen „parastroph“ zueinander, wenn sie in der OAR als Tripel durch eine Permutation $\pi \in S_{3}$ auseinander hervorgehen, wenn also $(r,s,z)\in Q_{1}\Leftrightarrow \pi (r,s,z)\in Q_{2}$ gilt. Zum Beispiel vertauscht $\pi =(1,2)\in S_{3}$ die Zeilennummer mit der Spaltennummer und entspricht damit in der Matrixdarstellung der Transposition. Jede Klasse von zueinander parastrophen lateinischen Quadraten enthält 1, 2, 3 oder 6 verschiedene lateinische Quadrate, dies ist eine Folgerung aus der Bahnformel. Siehe dazu auch Quasigruppe#Parastrophien.

Isotopie

Zwei lateinische Quadrate heißen „isotop“ zueinander, wenn sie auseinander durch eine Kombination von Zeilen-, Spaltenpermutationen und bijektive Umbenennungen der Einträge hervorgehen. Die Anzahlen $a_{n}$ der Isotopieklassen von lateinischen Quadraten der Ordnung $n$ bilden Folge A040082 in OEIS. Siehe dazu auch Quasigruppe#Morphismen.

Hauptklassen

Kombiniert man die Äquivalenzrelationen Parastrophie und Isotopie, so gelangt man zu einer neuen Äquivalenzklasseneinteilung, der Einteilung in die so genannten Hauptklassen. Zwei lateinische Quadrate gehören der gleichen Hauptklasse an, wenn sie durch eine Kombination von Parastrophie- und Isotopieoperationen ineinander umgewandelt werden können. In jeder Hauptklasse sind 1, 2, 3 oder 6 Isotopieklassen enthalten. Die Anzahlen $h_{n}$ der Hauptklassen von lateinischen Quadraten der Ordnung $n$ bilden Folge A003090 in OEIS.

Geschichte

Ernest Tilden Parkers griechisch-lateinisches Quadrat der Ordnung 10, welches die Nicht-Existenz-Vermutung von Euler widerlegt.

Die ersten lateinischen Quadrate sind auf Amuletten und Ringen mit religiösem oder magischem Inhalt um das Jahr 1000 im arabischen und indischen Kulturkreis nachweisbar. Magische Quadrate sind schon länger bekannt und waren verbreiteter auf Amuletten. Das Buch Shams al-Ma'arif al-Kubra des arabischen Sufi Ahmad ibn 'Ali ibn Yusuf al-Buni (gestorben 1225) enthält viele lateinische und magische Quadrate. Sie haben dort astrologische Bedeutung und die Auswahl deutet darauf, dass er mathematische Konstruktionsmethoden für diese kannte (bzw. Konstruktionsmethoden für magische Quadrate ausgehend von lateinischen Quadraten, was auch schon in Indien bekannt war). Lateinische Quadrate finden sich auch im 13. Jahrhundert bei Ramon Llull und in einem indischen Buch von 1356 von Narayana Pandit (Ganita-kaumudi).

In der westlichen mathematischen Literatur tauchten lateinische Quadrate bei einem alten quadratischen Kartenanordnungsproblem auf, das sich bei Claude Gaspard Bachet de Méziriac findet und von Jacques Ozanam in seine Sammlung aufgenommen wurde (1723, Récréations mathématiques et physiques. Die analytische (mathematische) Behandlung geschah erstmals bei Leonhard Euler, der 1779 in den Abhandlungen der Petersburger Akademie (veröffentlicht 1782,Recherches sur une nouvelle espèce de quarrés magiques) unter anderem das Problem der 36 Offiziere stellte: 36 Offiziere jeweils verschiedenen Rangs und verschiedenen Regiments sollten in einem 6x6 Quadrat angeordnet werden gemäß den Regeln für das lateinische Quadrat. Das Problem fragte im Wesentlichen nach zwei lateinischen Quadraten der Ordnung 6, die orthogonal sind. Euler fand keine Lösung (wie später gezeigt wurde gibt es auch keine), er fand aber eine Lösung für den Fall der Ordnung 7. Die Arbeit gab den lateinischen Quadraten ihren Namen (der Name stammte aus seiner Indizierung über lateinische und griechische Buchstaben beim Offiziersproblem, ließ er einen Index fallen ergab sich das Problem lateinischer Quadrate) und war der Beginn der Behandlung orthogonaler lateinischer Quadrate, wobei der Name nicht von Euler stammt. Euler konstruierte auch magische Quadrate aus lateinischen Quadraten, was allerdings schon in Indien bekannt war und in Europa von anderen Autoren vor Euler aufgegriffen worden war, so von La Loubère (1691), La Hire (1705), Joseph Sauveur (1710), der viele verschiedene lateinische Quadrate veröffentlichte (darunter drei gegenseitig orthogonale lateinische Quadrate der Ordnung 7). Magische Quadrate waren damals seit langem bekannt und von größerem Interesse als lateinische Quadrate und Euler hatte sich auch schon lange vorher mit ihnen befasst (1726 in seinen Notizbüchern und in einer längeren Abhandlung der Petersburger Akademie 1776, De quadratis magicis).

Ein erstes Beispiel orthogonaler lateinischer Quadrate gab noch vor Euler der Koreaner Choi Seok-jeong Anfang des 18. Jahrhunderts. Er fand ein orthogonales lateinisches Quadrat der Ordnung 9, scheiterte aber wie Euler bei der Ordnung 10.

Euler vermutete, dass es keine orthogonalen lateinischen Quadrate der Ordnung (4k+2) gibt, also auch keines der Ordnung 6 oder 10. Gaston Tarry fand 1900, dass es keine der Ordnung 6 gibt (möglicherweise – nach einem Brief von Heinrich Schumacher an Carl Friedrich Gauß von 1842, der eine Lösung von Thomas Clausen erwähnt- wurde das schon früher gefunden), allerdings fand Ernest Tilden Parker 1959 ein Gegenbeispiel für n=10 und Parker, Raj Chandra Bose und S. S. Shrikhande bewiesen 1960, dass es orthogonale lateinische Quadrate für alle $n\geq 10$ gibt. Über die Anzahl zueinander orthogonaler lateinischer Quadrate (MOLS) für eine bestimmte Ordnung n bewies E. H. Moore 1896 (von H. F. MacNeish und anderen wiederentdeckt) dass deren Maximalzahl (n-1) ist. Solche vollständigen Systeme von MOLS sind äquivalent zu projektiven und affinen Ebenen der Ordnung n. Eine Erweiterung der Eulerschen Vermutung über die Existenz von orthogonalen lateinischen Quadrate über die Mindestanzahl von MOLS wurde ebenso wie die Eulersche Vermutung widerlegt.

Die Verwendung eines lateinischen Quadrats in einer Versuchsplanung geschah zuerst 1788 durch Francois Crettè de Palluel (er benutzte eines der Ordnung 4 zur Untersuchung der Winterfütterung von Schafen).

Literatur

Fachartikel zu Einzelfragen

• Charles Colbourn: The complexity of completing partial latin squares. In: Discrete Applied Mathematics. Band 8, 1984, S. 25–30, doi:10.1016/0166-218X(84)90075-1. 

Versuchsplanung und Designtheorie

• Jürgen Bortz: Statistik für Human- und Sozialwissenschaftler. 6. Auflage. Springer Medizin Verlag, Heidelberg 2005, ISBN 3-540-21271-X. 
• Jürgen Bortz: Forschungsmethoden und Evaluation für Human- und Sozialwissenschaftler. 4. Auflage. Springer Medizin Verlag, Heidelberg 2006, ISBN 3-540-33305-3. 
• Jeffrey H. Dinitz, Douglas Robert Stinson: A Brief Introduction to Design Theory. In: J. H. Dinitz und D. R. Stinson (Hrsg.): Contemporary Design Theory: A Collection of Surveys. John Wiley & Sons, New York 1992, ISBN 0-471-53141-3, Kap. 1, S. 1–12. 
• Klaus Hinkelmann, Oscar Kempthorne: Design and Analysis of Experiments Set. 2. Auflage. I und II. John Wiley & Sons, New York 2008, ISBN 978-0-470-38551-7 (englisch, Verlagsseite über das Buch [abgerufen am 28. Februar 2012]). 

Kombinatorik und Diskrete Mathematik

• Jacobus Hendricus van Lint, Richard M. Wilson: A Course in Combinatorics. 2. Auflage. Cambridge University Press, Cambridge 2001, ISBN 0-521-80340-3. 
• Jiří Matoušek, Jaroslav Nešetřil: Diskrete Mathematik. Eine Entdeckungsreise. Springer, Berlin / Heidelberg / New York / ... 2002, ISBN 3-540-42386-9, S. 157 ff. (Online – englisch: Invitation to Discrete Mathematics. Übersetzt von Hans Mielke, Lehrbuch, das wenig Vorkenntnisse – gehobene Schulmathematik bis 2. Semester Mathematikstudium – voraussetzt). 

Programmierung

• Donald E. Knuth: Volume 4A: Combinatorial Algorithms, Part 1. In: The Art of Computer Programming. 1. Auflage. Addison-Wesley, Reading MA 2011, ISBN 978-0-201-03804-0, S. xv und 883 ff. (englisch, Überblick über das Gesamtwerk [abgerufen am 28. Februar 2012]). 

Weblinks

• Eric W. Weisstein: Latin Square. In: MathWorld (englisch).
• V.M. Mikheev (originator): Latin square. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 1-55608-010-7 (englisch, encyclopediaofmath.org). Vorlage:EoM/id
• V.M. Mikheev (originator): Orthogonal Latin squares. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 1-55608-010-7 (englisch, encyclopediaofmath.org). Vorlage:EoM/id
• Lars Døvling Andersen: The History of Latin Squares. (PDF; 1,2 MB) Vorabdruck. In: The History of Combinatorics. Robin J. Wilson, Dezember 2007, abgerufen am 28. Februar 2012 (englisch, Geschichte der lateinischen Quadrate). 
• Hans Peter Gramatke: Eulersche Quadrate. Exkurs. In: Hans Peters mathematisch-technisch-algorithmisch-linguistisches Sammelsurium. 2. April 2003, abgerufen am 28. Februar 2012 (private Seite mit Wissenswertem und Amüsantem über lateinische und magische Quadraten und einige Varianten). 
• Aale de Winkel: The Magic Encyclopedia. 8. Januar 2001, abgerufen am 28. Februar 2012 (Tabellenkalkulationsprogramme (Microsoft Excel) zur Generierung von magischen und lateinischen Quadraten).