Lateinisches Quadrat

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Ein lateinisches Quadrat der Ordnung 7 am Gonville and Caius College, Cambridge.

Ein lateinisches Quadrat ist ein quadratisches Schema mit n Reihen 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.

Als Symbole werden häufig die Zahlen von 1 bis n, 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 (Cailey-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 statistischen Versuchsplanung angewendet.[1][2]

Darstellung, Eigenschaften und Begriffe[Bearbeiten]

Darstellung als Matrix[Bearbeiten]

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:[3]

  • 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[Bearbeiten]

Ein lateinisches Quadrat der Ordnung n lässt sich auch darstellen als Menge Q von n^2 verschiedenen Tripeln (r,s,z)\in \{1,2,\ldots n\}^3. Dabei steht r für die Nummer einer Zeile („Reihe“) 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 Reihennummern 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[Bearbeiten]

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:[4]

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

Reduzierte lateinische Quadrate[Bearbeiten]

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).[5]

Beispiele[Bearbeiten]

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 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 1,2,\ldots n, dann erhält man stets ein reduziertes lateinisches Quadrat, das sich als Verknüpfungstabelle der Restklassengruppe \left(\Z /n\Z,+\right) interpretieren lässt. Dazu müssen die eingetragenen Zahlen alle um 1 verringert werden.

Orthogonale lateinische Quadrate und MOLS [Bearbeiten]

Zwei lateinische Quadrate Q und R heißen orthogonal,[5][6] 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:[7]


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.[5]
(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 \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.[8]
  • 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[9] 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[Bearbeiten]

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 Reihensummen 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 Reihen- und Spaltensumme, dann spricht man von einem magischen Quadrat.

Anwendungen[Bearbeiten]

Algebra: Lateinische Quadrate und Verknüpfungstafeln[Bearbeiten]

Die erste Abbildung links zeigt die vollständige Verknüpfungstafel der Gruppe C_5=\left(\Z /5\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 Reihen und die Spalten der Verknüpfungstabelle (samt ihrer 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 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_naus 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 Reihe 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 Reihenüberschriften – wenn die Quasigruppe eine Loop ist.

Geometrie: Orthogonale lateinische Quadrate und endliche Ebenen [Bearbeiten]

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:[5]

  • 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\,\and \,(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 \and \beta(j)=x\and \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.[5]

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[Bearbeiten]

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=\Z / 5\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[Bearbeiten]

  • 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.[10]
  • 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.

Äquivalenzklassen lateinischer Quadrate [Bearbeiten]

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 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 in 4. genannten Transformationen sind Spezialfälle der 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 n (mit Symbolen aus \{1,2,\ldots,n\}) eingeführt wird.

Parastrophie[Bearbeiten]

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.[11] Zum Beispiel vertauscht \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[Bearbeiten]

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 a_n der Isotopieklassen von lateinischen Quadraten der Ordnung n bilden Folge A040082 in OEIS. Siehe dazu auch Quasigruppe#Morphismen.

Hauptklassen[Bearbeiten]

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.

Literatur[Bearbeiten]

Fachartikel zu Einzelfragen
Versuchsplanung und 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 0471531413, 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 (http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0470385510.html Verlagsseite über das Buch (HTML), abgerufen am 28. Februar 2012).
Kombinatorik und Diskrete Mathematik
  •  Jacobus Hendricus van Lint, R. M. Wilson: A Course in Combinatorics. 2. Auflage. Cambridge University Press, Cambridge 2001, ISBN 0521803403.
  •  Jiří Matoušek, Jaroslav Nešetřil: Diskrete Mathematik. Eine Entdeckungsreise. Springer, Berlin/Heidelberg/New York/... 2002 (Originaltitel: Invitation to Discrete Mathematics, übersetzt von Hans Mielke), ISBN 3-540-42386-9, S. 157ff (Lehrbuch, das wenig Vorkenntnisse – gehobene Schulmathematik bis 2. Semester Mathematikstudium – voraussetzt, Inhaltsverzeichnis, abgerufen am 8. Februar 2012).
Programmierung

Weblinks[Bearbeiten]

Einzelnachweise und Anmerkungen[Bearbeiten]

  1. Hinkelmann und Kempthorne (2008)
  2. Vorlage:Internetquelle/Wartung/Datum nicht im ISO-FormatThe 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 (HTML, englisch).
  3. Durch die Summe wird für jede Zahl l, die in der Zeile bzw. Spalte auftritt, das „Bit“ mit der Wertigkeit 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. a b c d e 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 R(2)=1 ist, gehört die Matrix A zu keiner nichttrivialen Liste von MOLS.
  10. Colbourn (1984)
  11. Formal: Die Permutationsgruppe S_3 operiert auf \{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.