Orthogonale Lateinische Quadrate

Ein Lateinisches Quadrat der Ordnung n ist eine nxn-Matrix $L\; =\; (a$_i,j ) mit Einträgen aus einer n-elementigen Menge $A$, so daß jedes Element aus $A$ in jeder Zeile und jeder Spalte von $L$ genau einmal vorkommt. Daher ist $L$ nichts anderes als die Cayley-Tafel einer endlichen Quasigruppe $(A,*)$.

Zwei Lateinische Quadrate $(a$_i,j ) und $(b$_i,j ) über derselben n-elementigen Menge $A$ heißen orthogonal, wenn zu jedem Paar $(a,b)$ aus $AxA$ genau eine Koordinate $i,j$ existiert, so daß $a\; =\; a$_i,j und $b\; =\; b$_i,j gilt.

Denkt man sich zwei orthogonale Lateinische Quadrate "übereinandergelegt", so gibt es für jedes Paar $(a,b)$ aus $AxA$ also genau eine Stelle, an der $a$ und $b$ in dieser Reihenfolge übereinander liegen.

Für $n\; =\; 1$, also etwa $A\; =\; \{\; a\; \}$, gibt es trivialerweise genau ein lateinisches Quadrat der Ordnung 1 und dieses ist offensichtlich zu sich selbst orthogonal.

Für $n\; >\; 1$ kann dagegen kein Lateinisches Quadrat der Ordnung n zu sich selbst orthogonal sein, da beim "Übereinanderlegen" nur Paare der Gestalt $(a,a)$ entstehen, also nicht sämtliche Elemente aus $AxA$. Da es für $n\; =\; 2$ nur genau eine Quasigruppe (und damit ein Lateinisches Quadrat) der Ordnung 2 gibt, existiert in diesem Fall kein Paar orthogonaler Lateinischer Quadrate. Leonhard Euler bemühte sich vergeblich, ein Paar orthogonaler Lateinischer Quadrate der Ordnung 6 zu finden und er vermutete daraufhin, daß es kein Paar orthogonaler Quadrate der Ordnung n geben könnte, wenn n=2 mod 4 ist. Diese Vermutung wurde erst im Jahre 1900 für n=6 bewiesen, jedoch wurde dann 1959/1960 gezeigt, daß die Vermutung für alle anderen n = 2 mod 4 falsch ist, daß also dann stets Paare orthogonaler Lateinischer Quadrate existieren. Schon vorher hatte man eine Konstruktionsmethode gefunden, die es für alle n, die nicht kongruent 2 modulo 4 sind, gestattete, Paare orthogonaler Lateinischer Quadrate anzugeben. Diese Methode wird im folgenden beschrieben.

Es sei zunächst $n\; =\; pk$ eine Primzahlpotenz und $n\; >\; 2$. Dann gibt es einen Körper $(K,+,*)$ der Ordnung n und in $K\; \backslash \; \{\; 0\; \}$ zwei verschiedene Elemente $c$₁ und $c$₂. Jetzt definiert man zwei Verknüpfungen $*$₁ und $*$₁ auf $K$ durch

(1) $a*$_ib = c_i*a + b

für alle $a,\; b$ aus $K$.

Sind nun $a,\; b$ aus $K$ beliebig gegeben, so sind $x$_i = b - c_i*a und $y$_i = c_i^-1*(b - a) die eindeutig bestimmten Elemente aus $K$ mit $a*$_i x_i = c_i*a + x_i = b bzw. $y$_i*_i a = c_i*y_i + a = (b - a) + a = b. Also sind $(K,*$_i ) beides Quasigruppen und ihre Cayley-Tafeln daher Lateinische Quadrate. Es bleibt zu zeigen, daß dieses Paar Lateinischer Quadrate orthogonal ist. Dazu sei $(c,d)$ ein beliebiges Paar aus $KxK$. Dann bilden $a\; =\; (c$₁ - c₂)^-1*(c-d) und $b\; =\; c\; -\; c$₁*a die eindeutig bestimmte Lösung des linearen Gleichungssystems

$a*$₁b = c₁*a + b = c$$
$a*$₂b = c₂*a + b = d$.$

Also bestimmen $a$ und $b$ die Zeile bzw. die Spalte in den Cayley-Tafeln von $(K,*$₁ ) und $(K,*$₂ ), wo $c$ und $d$ jeweils stehen. Daher sind diese beiden Lateinischen Quadrate orthogonal.

Für $n\; >\; 3$ kann man die Konstruktion geringfügig modifizieren, um sogar zwei idempotente Quasigruppen $(K,*$_i ) zu erhalten. Dazu wähle man $c$₁ und $c$₂ sogar aus $K\; \backslash \; \{\; 0,\; 1\; \}$ und definiere anstelle von (1)

(1') $a*$_ib = c_i*a + (1 - c_i )*b

für alle $a,\; b$ aus $K$. Setzt man hierin nämlich $a=b$, so ergibt sich unmittelbar die Idempotenz beider Verknüpfungen. Die restlichen Aussagen sind wie oben zu zeigen.

Ist nun n eine beliebige natürliche Zahl, die nicht kongruent 2 modulo 4 ist, so ist der Fall $n=1$ oben schon erledigt und man kann für n eine Primfaktorzerlegung gemäß

(2) $n\; =\; 2m*n$₁*...*n_k,

Zur Veranschaulichung sei die Konstruktion für n=5 mittels (1') konkret ausgeführt. In dem Körper $K\; =\; Z/(5)\; =\; \{0,\; 1,\; 2,\; 3,\; 4\}$ wähle man etwa $c$₁ = 2 und $c$₂ = 4 = -1. Dann sind die beiden Verknüpfungen also gemäß $a*$₁b = 2*a - b und $a*$₂b = -a + 2*b definiert. Damit berechnet man die Cayley-Tafeln von $*$₁ zu

Wegen $a*$₂b = b*₁a ergibt sich die Cayley-Tafel von $*$₂ hieraus durch Spiegelung an der Hauptdiagonalen und man kann sofort die beiden orthogonalen Lateinischen Quadrate angeben.