Orthogonale Lateinische Quadrate


Ein Lateinisches Quadrat der Ordnung n ist eine nxn-Matrix L = (ai,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 (ai,j ) und (bi,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 = ai,j und b = bi,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 \ { 0 } zwei verschiedene Elemente c1 und c2. Jetzt definiert man zwei Verknüpfungen *1 und *1 auf K durch

(1) a*ib = ci*a + b

für alle a, b aus K.

Sind nun a, b aus K beliebig gegeben, so sind xi = b - ci*a und yi = ci-1*(b - a) die eindeutig bestimmten Elemente aus K mit a*i xi = ci*a + xi = b bzw. yi*i a = ci*yi + 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 = (c1 - c2)-1*(c-d) und b = c - c1*a die eindeutig bestimmte Lösung des linearen Gleichungssystems

a*1b = c1*a + b = c
a*2b = c2*a + b = d.

Also bestimmen a und b die Zeile bzw. die Spalte in den Cayley-Tafeln von (K,*1 ) und (K,*2 ), 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 c1 und c2 sogar aus K \ { 0, 1 } und definiere anstelle von (1)

(1') a*ib = ci*a + (1 - ci )*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*n1*...*nk,

voraussetzen, wobei m /= 1 gilt und die ni > 2 Potenzen ungerader Primzahlen sind. Für jede in (2) auftretende Primzahlpotenz kennt man aber nach der oben angegebenen Konstruktion ein Paar von Quasigruppen, das ein Paar orthogonaler Lateinischer Quadrate liefert. Bildet man jetzt die direkten Produkte der jeweiligen Quasigruppen, so erhält man wiederum ein Paar von Quasigruppen der Ordnung n, welche das zu konstruierende Paar orthogonaler Lateinischer Quadrate liefert.


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 c1 = 2 und c2 = 4 = -1. Dann sind die beiden Verknüpfungen also gemäß a*1b = 2*a - b und a*2b = -a + 2*b definiert. Damit berechnet man die Cayley-Tafeln von *1 zu

*1
0 1 2 3 4
0
1
2
3
4
0 4 3 2 1
2 1 0 4 3
4 3 2 1 0
1 0 4 3 2
3 2 1 0 4

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

0 4 3 2 1
2 1 0 4 3
4 3 2 1 0
1 0 4 3 2
3 2 1 0 4
 
0 2 4 1 3
4 1 3 0 2
3 0 2 4 1
2 4 1 3 0
1 3 0 2 4