Lateinisches Quadrat

Ein lateinisches Quadrat ist ein quadratisches Schema mit ${\displaystyle n}$ Reihen und ${\displaystyle n}$ Spalten, wobei jedes Feld mit einem von ${\displaystyle n}$ verschiedenen Symbolen belegt ist, so dass jedes Symbol in jeder Zeile und in jeder Spalte jeweils genau einmal auftritt. Die natürliche Zahl ${\displaystyle 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 ${\displaystyle 1}$ bis ${\displaystyle n}$, oder ${\displaystyle n}$ verschiedene Buchstaben oder auch ${\displaystyle 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 ${\displaystyle 1}$ bis ${\displaystyle n}$, seltener die Zahlen von ${\displaystyle 0}$ bis ${\displaystyle n-1}$ verwendet, und das Schema wird als spezielle ${\displaystyle n\times n}$-Matrix betrachtet.

Jedes lateinische Quadrat k​ann als Verknüpfungstafel (Cayley-Tafel) e​iner endlichen Quasigruppe aufgefasst werden, umgekehrt bestimmt j​ede endliche Quasigruppe e​ine Äquivalenzklasse v​on lateinischen Quadraten.

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

Außerhalb d​er Mathematik i​m engeren Sinn werden lateinische Quadrate u​nter anderem i​n der agrarwissenschaftlichen Versuchsplanung a​ls Blockanlagen u​nd der statistischen Versuchsplanung angewendet.[1][2]

Darstellung, Eigenschaften und Begriffe

Darstellung als Matrix

Ein lateinisches Quadrat der Ordnung ${\displaystyle n}$ ist eine quadratische ${\displaystyle n\times n}$ Matrix, deren sämtliche Einträge natürliche Zahlen von ${\displaystyle 1}$ bis ${\displaystyle 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 ${\displaystyle M_{j,k}}$ der Matrix ${\displaystyle M}$ müssen folgende Gleichungen erfüllt sein:[3]

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

Tripeldarstellung: OAR

Ein lateinisches Quadrat der Ordnung ${\displaystyle n}$ lässt sich auch als Menge ${\displaystyle Q}$ von ${\displaystyle n^{2}}$ verschiedenen Tripeln ${\displaystyle (r,s,z)\in \{1,2,\ldots n\}^{3}}$ darstellen. Dabei steht ${\displaystyle r}$ für die Nummer einer Zeile („Reihe“) im lateinischen Quadrat, ${\displaystyle s}$ für die Nummer einer Spalte und ${\displaystyle 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 l​egt eine geometrische Interpretation für e​in lateinisches Quadrat nahe: Man k​ann die Zahl i​n einer Zelle d​es lateinischen Quadrates a​ls Höhe e​ines Quaders auffassen, d​er auf dieser Zelle a​ls Grundfläche errichtet werden soll. Damit w​ird aus d​em lateinischen Quadrat e​in räumliches Säulendiagramm – vergleiche d​ie Abbildung z​u dem Beispiel unten.

In dem Bild ist auch eine verwandte Interpretation des lateinischen Quadrates der Ordnung ${\displaystyle 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 ${\displaystyle n^{2}}$ achsparallelen Einheitswürfeln in einem größeren achsparallelen Würfel mit der Kantenlänge ${\displaystyle n}$. Der Teilwürfel mit den Gitterkoordinaten ${\displaystyle (r,s,z)}$ ist genau dann „gefüllt“, wenn ${\displaystyle (r,s,z)}$ zu der OAR des lateinischen Quadrates gehört. Eine Anordnung von ${\displaystyle n^{2}}$ Teilwürfeln in einem solchen Würfel der Kantenlänge ${\displaystyle n}$ gehört genau dann zu einem lateinischen Quadrat der Ordnung ${\displaystyle 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 m​acht anschaulich, d​ass die OAR e​ines lateinischen Quadrates n​icht nur b​ei Vertauschen d​er Zeilen- m​it den Spaltennummern (einer Transposition i​n der Matrixdarstellung) z​ur OAR e​ines lateinischen Quadrates wird, sondern sogar, w​enn alle Zeichennummern m​it den Reihennummern o​der 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 ${\displaystyle r}$- mit der ${\displaystyle z}$-Achse vertauscht. Wenn man im ersten Quadrat C die ${\displaystyle s}$- mit der ${\displaystyle z}$-Achse vertauscht, entsteht ebenfalls das Quadrat D, denn dessen Matrix ist symmetrisch.

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

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

${\displaystyle {\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 ${\displaystyle L(n)}$ lateinischer Quadrate der Ordnung ${\displaystyle n=1,2,3,\ldots }$, bilden Folge A002860 in OEIS. Es ist keine einfach zu berechnende Formel für die Folge ${\displaystyle L(n)}$ bekannt. Die besten bekannten unteren und oberen Schranken für große Ordnungen ${\displaystyle n}$ sind noch weit auseinander. Eine klassische Abschätzung lautet:[4]

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

Die Anzahlen d​er strukturell unterschiedlichen lateinischen Quadrate (d. h. d​ie Quadrate s​ind nicht d​urch Drehung, Spiegelung, o​der Permutation d​er Symbole identisch z​u machen) b​is zur Ordnung 7 bilden Folge A264603 i​n OEIS.

Reduzierte lateinische Quadrate

Ein lateinisches Quadrat heißt reduziert oder auch normalisiert, wenn in der 1. Zeile und in der 1. Spalte die ${\displaystyle n}$ verschiedenen Symbole in ihrer „natürlichen Reihenfolge“ stehen. In der Tripeldarstellung mit Zahlen als Symbolen bedeutet das: ${\displaystyle \{(1,1,1);(1,2,2);\ldots (1,n,n)\}\subset Q}$ für die erste Zeile und ${\displaystyle \{(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 ${\displaystyle l(n)}$ reduzierter lateinischer Quadrate der Ordnung ${\displaystyle n=1,2,3,\ldots }$ bilden Folge A000315 in OEIS. Für die Anzahl aller lateinischen Quadrate ${\displaystyle L(n)}$ gilt ${\displaystyle L(n)=n!\cdot (n-1)!\cdot l(n).}$[5]

Beispiele

Lateinische Quadrate d​er Ordnung 3 bzw. 4 i​n der Matrixdarstellung:

${\displaystyle {\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: ${\displaystyle \{(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 ${\displaystyle (1,1,2)}$ (1. Zeile, 1. Spalte enthält 2) und das Tripel ${\displaystyle (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 ${\displaystyle n}$ angeben: Dazu verteilt man ${\displaystyle n}$ verschiedene Symbole beliebig auf die erste Reihe des Quadrats. Die folgenden Reihen füllt man nun sukzessive aus, indem man die jeweils vorangehende Reihe um eins nach rechts verschoben übernimmt. Das äußerste rechte Symbol der vorangehenden Reihe würde dabei aus dem Quadrat hinausfallen; stattdessen trägt man es in der neuen Reihe 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 ${\displaystyle 1,2,\ldots n}$, dann erhält man stets ein reduziertes lateinisches Quadrat, das sich als Verknüpfungstabelle der Restklassengruppe ${\displaystyle \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 ${\displaystyle Q}$ und ${\displaystyle R}$ heißen orthogonal,[5][6] wenn keine zwei von den ${\displaystyle n^{2}}$ Paaren übereinstimmen, die entstehen, wenn man die Einträge von ${\displaystyle Q}$ und ${\displaystyle R}$ jeweils nebeneinander in ein neues quadratisches Schema ${\displaystyle S}$ schreibt. In Matrixdarstellung:[7]

${\displaystyle 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 ${\displaystyle S}$ kombinierten lateinischen Quadrate ${\displaystyle Q}$ und ${\displaystyle R}$ sind orthogonal. In diesem Fall nennt man das durch ${\displaystyle S}$ repräsentierte Quadrat ein griechisch-lateinisches Quadrat. Die Anzahlen der Paare von orthogonalen lateinischen Quadraten der Ordnung ${\displaystyle n=1,2,3,\ldots }$ bilden Folge A072377 in OEIS.

Für d​ie Anwendung i​n der Geometrie i​st folgender Satz wichtig:

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

(vermutete) maximale Anzahlen von MOLS

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

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

• Ist ${\displaystyle n>4}$ und ${\displaystyle R(n)\geq n-3}$, dann ist ${\displaystyle R(n)=n-1}$, denn eine Liste von ${\displaystyle n-3\geq 2}$ paarweise orthogonalen lateinischen Quadraten lässt sich stets vervollständigen.
• Für ${\displaystyle n>6}$ ist ${\displaystyle R(n)\geq 2}$, für ${\displaystyle n>52}$ ist ${\displaystyle R(n)\geq 4.}$
• Ist ${\displaystyle p}$ eine Primzahl und ${\displaystyle r\in \mathbb {N} }$, dann ist ${\displaystyle R(p^{r})=p^{r}-1}$.
• Bis heute ist nicht bekannt, ob es eine natürliche Zahl ${\displaystyle n}$ gibt, die keine Primzahlpotenz ist und für die ${\displaystyle R(n)=n-1}$ gilt.
• Für hinreichend große ${\displaystyle n}$ ist ${\displaystyle R(n)\geq n^{1/17}-2}$, also ist ${\displaystyle \lim _{n\to \infty }R(n)=\infty }$.[8]
• Es gilt für ${\displaystyle n,m\geq 3}$ immer ${\displaystyle R(n\cdot m)\geq \min(R(n),R(m))}$, denn aus einer Liste von ${\displaystyle t}$ MOLS der Ordnung ${\displaystyle n}$ und einer Liste von t MOLS der Ordnung ${\displaystyle m}$ lässt sich stets eine Liste von ${\displaystyle t}$ MOLS der Ordnung ${\displaystyle n\cdot m}$ herstellen. Das Verfahren wird hier an einem trivialen[9] Beispiel demonstriert:

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

${\displaystyle \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. ${\displaystyle (j,k)\mapsto (j-1)\cdot n+k}$ – alle Zeilensummen und Reihensummen gleich, zum Beispiel kann man dem Quadrat S so das Quadrat ${\displaystyle {\hat {S}}}$

${\displaystyle 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 ${\displaystyle s=15}$ hat.

Ist i​n einem solchen Quadrat zusätzlich n​och die Summe d​er beiden Diagonalen gleich d​er Reihen- u​nd Spaltensumme, d​ann spricht m​an von e​inem 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[10]

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

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

${\displaystyle \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 ${\displaystyle \{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 ${\displaystyle \{1,2,3,4,5\}}$. Hier ist dieses lateinische Quadrat normalisiert, weil die Gruppenelemente der Gruppe ${\displaystyle 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 ${\displaystyle S_{n}}$ die symmetrische Gruppe auf ${\displaystyle n}$ Elementen, dann wird durch eine Permutation ${\displaystyle \pi \in S_{n}}$, die nacheinander auf die Reihen und die Spalten der Verknüpfungstabelle (samt ihren Reihen- 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 ${\displaystyle M=(M_{j,k})}$ ein lateinisches Quadrat der Ordnung ${\displaystyle n}$ in der Matrixdarstellung, dann existiert eine Quasigruppe mit ${\displaystyle n}$ Elementen, die – bei geeigneter Anordnung und Nummerierung ihrer Elemente – die Matrix ${\displaystyle (M_{j,k})}$ als Inhalt ihrer Verknüpfungstabelle hat. Genau die lateinischen Quadrate ${\displaystyle N=(N_{j,k})}$ die durch eine gleichartige Zeilen- und Spaltenpermutation ${\displaystyle \pi \in S_{n}}$ und eine „Umnummerierung“ ${\displaystyle \rho \in S_{n}}$ aus ${\displaystyle M=(M_{j,k})}$ hervorgehen, für die also ${\displaystyle 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 ${\displaystyle L}$, also einer Quasigruppe mit einem zugleich links- und rechtsneutralen Element ${\displaystyle e}$, so, dass ${\displaystyle e}$ als erstes Element in der Verknüpfungstafel auftritt und ordnet den Elementen in ihrer ansonsten beliebigen Anordnung der Reihe nach die Zahlen ${\displaystyle 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 ${\displaystyle \#L}$. (Die Zahl ${\displaystyle \#L}$ steht für die Anzahl der Elemente von ${\displaystyle L}$).
• Eine Quasigruppe, die das lateinische Quadrat ${\displaystyle M=(M_{j,k})}$ der Ordnung ${\displaystyle n}$ als Inhalt ihrer Verknüpfungstafel hat, ist genau dann kommutativ, wenn die Matrix ${\displaystyle (M_{j,k})}$ symmetrisch ist, wenn also ${\displaystyle 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 Reihenüberschriften – wenn die Quasigruppe eine Loop ist.

Geometrie: Orthogonale lateinische Quadrate und endliche Ebenen

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

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

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

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

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

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

${\displaystyle 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: ${\displaystyle {\mathcal {G}}=\bigcup _{i=0}^{n}R_{i}}$.

Umgekehrt kann man in einer endlichen affinen Ebene der Ordnung n ein affines Koordinatensystem ${\displaystyle (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 ${\displaystyle \beta$ :\{1,2,\ldots n\}\rightarrow K=OE_{1}} Zahlen als „kombinatorische Koordinaten“ zuordnen, so dass

${\displaystyle 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 ${\displaystyle (O,E_{1},E_{2})}$ bezogene Koordinatendarstellung ${\displaystyle (x,y)\in K^{2}=(OE_{1})^{2}}$ ein eindeutiges Zahlenpaar ${\displaystyle (\beta ^{-1}(x),\beta ^{-1}(y))=(j,k)\in \{1,2,\ldots n\}^{2}}$. Jede der ${\displaystyle 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:

• ${\displaystyle g_{0,m}:\;y=\beta (m)\;(1\leq m\leq n)}$,
• ${\displaystyle g_{n,m}:\;T(O,y,x)=x=\beta (m)\;(1\leq m\leq n)}$ und
• ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle n\geq 2}$ gibt es genau dann eine projektive Ebene der Ordnung ${\displaystyle n}$, wenn es ${\displaystyle n-1}$ paarweise orthogonale lateinische Quadrate der Ordnung ${\displaystyle n}$ gibt.[5]

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

Konstruktion von orthogonalen lateinischen Quadraten aus Ternärkörpern

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

Beispiele

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

${\displaystyle \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 ${\displaystyle p^{r}}$ über die entsprechenden Quasigruppenverknüpfungen ${\displaystyle \star _{a},a\in \mathbb {F} _{p^{r}}\setminus \{0\}}$ im endlichen Körper ${\displaystyle \mathbb {F} _{p^{r}}}$ immer ${\displaystyle p^{r}-1}$ paarweise orthogonale lateinische Quadrate bestimmen.

Jedes dieser lateinischen Quadrate beschreibt dann die Inzidenzrelation in einer der ${\displaystyle p^{r}+1}$ Parallelenscharen der affinen Ebene über ${\displaystyle \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.[11]
• Ein lateinisches Quadrat der Ordnung 9 mit der Zusatzbedingung, dass in der Aufteilung in neun ${\displaystyle 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 a​n jedem v​on 4 Tagen g​enau einen Informatiker. Jeder Informatiker h​at an j​edem der 4 Tage g​enau einen Politiker z​u Besuch. Nach d​en 4 Tagen h​at jeder Politiker j​eden Informatiker g​enau einmal besucht.

Dieser Ablauf k​ann mit e​inem lateinischen Quadrat d​er Ordnung 4 dargestellt werden. Die Zeilen stellen d​ie Politiker, d​ie Spalten stellen d​ie Informatiker u​nd die Farben stellen d​ie Tage dar. Die Anzahl d​er Möglichkeiten für d​ie Konstellationen d​er Besuche a​n den 4 Tagen i​st gleich d​er Anzahl d​er lateinischen Quadrate d​er Ordnung 4 (Folge A002860 i​n OEIS). Es g​ibt 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 ${\displaystyle A}$, ${\displaystyle B}$, ${\displaystyle C}$ oder ${\displaystyle D}$ mit ${\displaystyle D-C=C-B=B-A>0}$ verwendet. Allerdings sind die Anbaubedingungen auf den 16 Bereichen inhomogen. In ${\displaystyle x}$-Richtung nimmt das Gefälle immer weiter zu, während in ${\displaystyle 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.[12] 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 [13] 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 v​iele unterschiedliche Transformationen, d​ie man a​uf ein lateinisches Quadrat anwenden kann, erhält m​an ein n​eues lateinisches Quadrat:

1. Man kann das Quadrat (in der Matrixschreibweise), an der Hauptdiagonalen spiegeln, die Matrixdarstellung also transponieren,
2. man kann die Reihen 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 i​n 4. genannten Transformationen s​ind Spezialfälle d​er Reihen- 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 ${\displaystyle n}$ (mit Symbolen aus ${\displaystyle \{1,2,\ldots ,n\}}$) eingeführt wird.

Parastrophie

Zwei lateinische Quadrate ${\displaystyle Q_{1},Q_{2}}$ heißen parastroph zueinander, wenn sie in der OAR als Tripel durch eine Permutation ${\displaystyle \pi \in S_{3}}$ auseinander hervorgehen, wenn also ${\displaystyle (r,s,z)\in Q_{1}\Leftrightarrow \pi (r,s,z)\in Q_{2}}$ gilt.[14] Zum Beispiel vertauscht ${\displaystyle \pi =(1,2)\in S_{3}}$ die Reihennummer 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 Reihen-, Spaltenpermutationen und bijektive Umbenennungen der Einträge hervorgehen. Die Anzahlen ${\displaystyle a_{n}}$ der Isotopieklassen von lateinischen Quadraten der Ordnung ${\displaystyle 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 ${\displaystyle h_{n}}$ der Hauptklassen von lateinischen Quadraten der Ordnung ${\displaystyle n}$ bilden Folge A003090 in OEIS.

Literatur

Fachartikel z​u 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 u​nd Designtheorie

• Jürgen Bortz: Statistik für Human- und Sozialwissenschaftler. 6. Auflage. Springer Medizin Verlag, Heidelberg 2005, ISBN 978-3-540-21271-3.
• Jürgen Bortz: Forschungsmethoden und Evaluation für Human- und Sozialwissenschaftler. 4. Auflage. Springer Medizin Verlag, Heidelberg 2006, ISBN 978-3-540-33305-0.
• Jeffrey H. Dinitz, Douglas Robert Stinson: A Brief Introduction to Design Theory. In: J. H. Dinitz and 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 u​nd Diskrete Mathematik

• Jacobus Hendricus van Lint, R. 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 0-201-03804-8, 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 978-1-55608-010-4 (englisch, online).
• V.M. Mikheev (originator): Orthogonal Latin squares. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 978-1-55608-010-4 (englisch, online).
• 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).

Einzelnachweise und Anmerkungen

1. Hinkelmann und Kempthorne (2008)
2. The latin square. In: A field guide to Experimental design. Washington State University, Tree Fruit Research and Extension Center, 16. August 2000, abgerufen am 28. Februar 2012 (englisch).
3. Durch die Summe wird für jede Zahl ${\displaystyle I}$, die in der Zeile bzw. Spalte auftritt, das „Bit“ mit der Wertigkeit ${\displaystyle 2^{l-1}}$ in einer n-stelligen Binärzahl gesetzt. Damit die getestete Matrix dann mit Sicherheit ein lateinisches Quadrat darstellt muss die zusätzliche Voraussetzung erfüllt sein, dass alle Einträge natürliche Zahlen sind. Dies wird durch den Test selbst nicht gewährleistet. (Knuth, 2011).
4. Lint & Wilson
5. Matoušek & Nešetřil, 8.3 Orthogonale lateinische Quadrate.
6. Diese Verwendung des Attributs „orthogonal“ hat nichts mit der im Artikel erläuterten englischen Bezeichnung „orthogonal array representation“ zu tun!
7. Formal korrekter aber weniger übersichtlich müssten die Einträge der Matrix S als Zahlenpaare geschrieben werden.
8. J. Dénes, A.D. Keedwell: Latin squares and their applications. Acad. Press, 1974
9. Da ${\displaystyle R(2)=1}$ ist, gehört die Matrix ${\displaystyle A}$ zu keiner nichttrivialen Liste von MOLS.
10. MathWorld: Cyclic Group C_8 Die zyklische Gruppe C₅ ist nicht enthalten, aber C₈ zum Beispiel.
11. Colbourn (1984).
12. Claupein, Link, Mayus: Anlage und Durchführung von Feldversuchen. (PDF) Universität Hohenheim, 2. April 2007, archiviert vom Original am 23. Februar 2017; abgerufen am 22. Februar 2017.
13. Felipe de Mendiburu: agricolae: Statistical Procedures for Agricultural Research. 12. Juni 2016, abgerufen am 22. Februar 2017.
14. Formal: Die Permutationsgruppe ${\displaystyle S_{3}}$ operiert auf ${\displaystyle \{1,2,\ldots n\}^{3}}$, der Menge aller Tripel von positiven ganzen Zahlen bis n. Dabei wird die OAR des ursprünglichen lateinischen Quadrates auf die OAR eines lateinischen Quadrates abgebildet, das auch mit dem Ausgangsquadrat übereinstimmen kann.