Ein lateinisches Quadrat ist ein quadratisches Schema mit Reihen und Spalten, wobei jedes Feld mit einem von verschiedenen Symbolen belegt ist, so dass jedes Symbol in jeder Zeile und in jeder Spalte jeweils genau einmal auftritt. Die natürliche Zahl wird Ordnung des lateinischen Quadrats genannt.
Als Symbole werden häufig die Zahlen von bis , oder verschiedene Buchstaben oder auch 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 bis , seltener die Zahlen von bis verwendet, und das Schema wird als spezielle -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 können orthogonal zueinander sein. In der synthetischen Geometrie werden bestimmten Mengen von paarweise orthogonalen lateinischen Quadraten der Ordnung endliche affine Ebenen zugeordnet. Daraus ergibt sich dort eine notwendige und hinreichende kombinatorische Bedingung für die Existenz von Ebenen der Ordnung : Eine solche Ebene existiert genau dann, wenn es eine vollständige Liste paarweise orthogonaler Quadrate der Ordnung 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 Bearbeiten
Darstellung als Matrix Bearbeiten
Ein lateinisches Quadrat der Ordnung ist eine quadratische Matrix, deren sämtliche Einträge natürliche Zahlen von bis 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 der Matrix müssen folgende Gleichungen erfüllt sein:
- Für jede Zeile muss und
- für jede Spalte muss gelten.
Tripeldarstellung: OAR Bearbeiten
Ein lateinisches Quadrat der Ordnung lässt sich auch als Menge von verschiedenen Tripeln darstellen. Dabei steht für die Nummer einer Zeile („Reihe“) im lateinischen Quadrat, für die Nummer einer Spalte und 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 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 achsparallelen Einheitswürfeln in einem größeren achsparallelen Würfel mit der Kantenlänge . Der Teilwürfel mit den Gitterkoordinaten ist genau dann „gefüllt“, wenn zu der OAR des lateinischen Quadrates gehört. Eine Anordnung von Teilwürfeln in einem solchen Würfel der Kantenlänge gehört genau dann zu einem lateinischen Quadrat der Ordnung , 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.
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 Bearbeiten
Das Beispiel in der Abbildung rechts zeigt das erste lateinische Quadrat C unten, das zweite, D, entsteht daraus, indem man die - mit der -Achse vertauscht. Wenn man im ersten Quadrat C die - mit der -Achse vertauscht, entsteht ebenfalls das Quadrat D, denn dessen Matrix ist symmetrisch.
Die Tripeldarstellungen lauten
bzw.
Anzahl der lateinischen Quadrate Bearbeiten
Die Anzahlen lateinischer Quadrate der Ordnung , bilden Folge A002860 in OEIS. Es ist keine einfach zu berechnende Formel für die Folge bekannt. Die besten bekannten unteren und oberen Schranken für große Ordnungen sind noch weit auseinander. Eine klassische Abschätzung lautet:
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 Bearbeiten
Ein lateinisches Quadrat heißt reduziert oder auch normalisiert, wenn in der 1. Zeile und in der 1. Spalte die verschiedenen Symbole in ihrer „natürlichen Reihenfolge“ stehen. In der Tripeldarstellung mit Zahlen als Symbolen bedeutet das: für die erste Zeile und 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 reduzierter lateinischer Quadrate der Ordnung bilden Folge A000315 in OEIS. Für die Anzahl aller lateinischen Quadrate gilt
Beispiele Bearbeiten
Lateinische Quadrate der Ordnung 3 bzw. 4 in der Matrixdarstellung:
Die Tripeldarstellung des linken Quadrates lautet: . Würde man dort in der ersten Zeile die Zahlen 1 und 2 vertauschen, so würden das Tripel (1. Zeile, 1. Spalte enthält 2) und das Tripel (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 angeben: Dazu verteilt man 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 , dann erhält man stets ein reduziertes lateinisches Quadrat, das sich als Verknüpfungstabelle der Restklassengruppe interpretieren lässt. Dazu müssen die eingetragenen Zahlen alle um 1 verringert werden.
Orthogonale lateinische Quadrate und MOLS Bearbeiten
Zwei lateinische Quadrate und heißen orthogonal (sie werden auch als Griechisch-Lateinische-Quadrate oder Euler-Quadrate bezeichnet), wenn keine zwei von den Paaren übereinstimmen, die entstehen, wenn man die Einträge von und jeweils nebeneinander in ein neues quadratisches Schema schreibt. In Matrixdarstellung:
Die hier zur Matrix kombinierten lateinischen Quadrate und sind orthogonal. In diesem Fall nennt man das durch repräsentierte Quadrat ein griechisch-lateinisches Quadrat. Die Anzahlen der Paare von orthogonalen lateinischen Quadraten der Ordnung bilden Folge A072377 in OEIS.
Für die Anwendung in der Geometrie ist folgender Satz wichtig:
| Ordnung n | R(n) |
|---|---|
| 0 | |
| 1 | |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 4 |
| 6 | 1 |
| 7 | 6 |
| 8 | 7 |
| 9 | 8 |
| 10 | |
| 11 | 10 |
| 12 | |
| 13 | 12 |
Eine Liste von paarweise orthogonalen lateinischen Quadraten der Ordnung wird als vollständig bezeichnet. Die Folge der größtmöglichen Anzahlen von paarweise orthogonalen lateinischen Quadraten (MOLS = mutually orthogonal Latin squares) der Ordnung ist Folge A001438 in OEIS, was über die Werte bis bekannt ist, zeigt die Tabelle rechts, die Werte für 0 und 1 sind Konvention. Es gilt:
- Ist und , dann ist , denn eine Liste von paarweise orthogonalen lateinischen Quadraten lässt sich stets vervollständigen.
- Für ist , für ist
- Ist eine Primzahl und , dann ist .
- Bis heute ist nicht bekannt, ob es eine natürliche Zahl gibt, die keine Primzahlpotenz ist und für die gilt.
- Für hinreichend große ist , also ist .
- Es gilt für immer , denn aus einer Liste von MOLS der Ordnung und einer Liste von t MOLS der Ordnung lässt sich stets eine Liste von MOLS der Ordnung herstellen. Das Verfahren wird hier an einem trivialen Beispiel demonstriert:
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. – alle Zeilensummen und Reihensummen gleich, zum Beispiel kann man dem Quadrat S so das Quadrat
zuordnen, bei dem jede Zeile und jede Spalte die magische Summe 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 :
|
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 , die für Restklassen üblich ist, dar. Addiert man zu jedem Eintrag 1, so entsteht ein lateinisches Quadrat mit der Standardsymbolmenge . Hier ist dieses lateinische Quadrat normalisiert, weil die Gruppenelemente der Gruppe 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 die symmetrische Gruppe auf Elementen, dann wird durch eine Permutation , 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 ein lateinisches Quadrat der Ordnung in der Matrixdarstellung, dann existiert eine Quasigruppe mit Elementen, die – bei geeigneter Anordnung und Nummerierung ihrer Elemente – die Matrix als Inhalt ihrer Verknüpfungstabelle hat. Genau die lateinischen Quadrate die durch eine gleichartige Zeilen- und Spaltenpermutation und eine „Umnummerierung“ aus hervorgehen, für die also gilt, können als Verknüpfungstabellen dieser Quasigruppe aufgefasst werden.
- Wählt man die Anordnung der Elemente einer endlichen Loop , also einer Quasigruppe mit einem zugleich links- und rechtsneutralen Element , so, dass als erstes Element in der Verknüpfungstafel auftritt und ordnet den Elementen in ihrer ansonsten beliebigen Anordnung der Reihe nach die Zahlen zu, dann ist der Inhalt ihrer Verknüpfungstafel, mit den zugeordneten natürlichen Zahlen geschrieben, ein reduziertes lateinisches Quadrat der Ordnung . (Die Zahl steht für die Anzahl der Elemente von ).
- Eine Quasigruppe, die das lateinische Quadrat der Ordnung als Inhalt ihrer Verknüpfungstafel hat, ist genau dann kommutativ, wenn die Matrix symmetrisch ist, wenn also 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 von paarweise orthogonalen lateinischen Quadraten der Ordnung lässt sich eine endliche affine Ebene der Ordnung konstruieren und umgekehrt. Dabei geht man so vor:
- Die Punktmenge besteht aus den Paaren natürlicher Zahlen von 1 bis :
- Jedes lateinische Quadrat bestimmt eine Parallelenschar der Ebene:
- Die Parallelenschar besteht aus den Geraden
- Dazu kommen zwei „Achsrichtungen“, und mit den Geraden
- Die Geradenmenge ist die Vereinigungsmenge der so definierten Parallelenscharen: .
Umgekehrt kann man in einer endlichen affinen Ebene der Ordnung n ein affines Koordinatensystem 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 Zahlen als „kombinatorische Koordinaten“ zuordnen, so dass
Damit hat man für jeden Punkt der Ebene über die auf die Punktbasis bezogene Koordinatendarstellung ein eindeutiges Zahlenpaar . Jede der 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:
- ,
- und
Weil jede endliche affine Ebene der Ordnung 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:
Wenn man die hier beschriebene Konstruktion mit einer unvollständigen Liste von MOLS durchführt, erhält man eine Inzidenzstruktur mit Punkten auf jeder Geraden und Parallelenscharen, also ein sogenanntes -Netz.
Konstruktion von orthogonalen lateinischen Quadraten aus Ternärkörpern Bearbeiten
Ist ein endlicher Ternärkörper, dann wird für jedes durch die Verknüpfung zu einer Quasigruppe . Bei gleicher Anordnung der Elemente von für die Multiplikationstabellen sind die lateinischen Quadrate zu zwei solchen Verknüpfungen bei unterschiedlichen Faktoren stets orthogonal zueinander. So erhält man durch einen Ternärkörper der Ordnung stets eine vollständige Liste von paarweise orthogonalen lateinischen Quadraten.
Der Restklassenkörper ist ein Ternärkörper. Die Inhalte der Multiplikationstabellen für die oben beschriebenen Quasigruppenverknüpfungen – da ein Körper ist, gilt hier – lauten:
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 über die entsprechenden Quasigruppenverknüpfungen im endlichen Körper immer paarweise orthogonale lateinische Quadrate bestimmen.
Jedes dieser lateinischen Quadrate beschreibt dann die Inzidenzrelation in einer der Parallelenscharen der affinen Ebene über 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.
- Ein lateinisches Quadrat der Ordnung 9 mit der Zusatzbedingung, dass in der Aufteilung in neun -Quadrate in jedem dieser Quadrate alle Symbole jeweils genau einmal auftreten, führt zu dem Zahlenrätsel Sudoku.
Besuche von Politikern und Informatikern Bearbeiten
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 Bearbeiten
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 , , oder mit verwendet. Allerdings sind die Anbaubedingungen auf den 16 Bereichen inhomogen. In -Richtung nimmt das Gefälle immer weiter zu, während in -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 Bearbeiten
Durch viele unterschiedliche Transformationen, die man auf ein lateinisches Quadrat anwenden kann, erhält man ein neues lateinisches Quadrat:
- Man kann das Quadrat (in der Matrixschreibweise) an der Hauptdiagonalen spiegeln, die Matrixdarstellung also transponieren,
- man kann die Reihen und/oder Spalten des lateinischen Quadrates permutieren,
- man kann die eingetragenen Zahlsymbole bijektiv umbenennen,
- 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 (mit Symbolen aus ) eingeführt wird.
Parastrophie Bearbeiten
Zwei lateinische Quadrate heißen parastroph zueinander, wenn sie in der OAR als Tripel durch eine Permutation auseinander hervorgehen, wenn also gilt. Zum Beispiel vertauscht 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 der Isotopieklassen von lateinischen Quadraten der Ordnung 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 der Hauptklassen von lateinischen Quadraten der Ordnung bilden Folge A003090 in OEIS.
Geschichte Bearbeiten
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 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 Bearbeiten
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 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 und 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 Bearbeiten
- 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).
- 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).
- 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 Bearbeiten
- Hinkelmann und Kempthorne (2008)
- 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).
- Durch die Summe wird für jede Zahl , die in der Zeile bzw. Spalte auftritt, das „Bit“ mit der Wertigkeit 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).
- Lint & Wilson
- ↑ Matoušek & Nešetřil, 8.3 Orthogonale lateinische Quadrate.
- ↑ L. D. Anderson, Chapter on the history of latin squares (pdf), Universität Aalborg, veröffentlicht in The History of Combinatorics
- Diese Verwendung des Attributs „orthogonal“ hat nichts mit der im Artikel erläuterten englischen Bezeichnung „orthogonal array representation“ zu tun!
- Formal korrekter aber weniger übersichtlich müssten die Einträge der Matrix S als Zahlenpaare geschrieben werden.
- J. Dénes, A.D. Keedwell: Latin squares and their applications. Acad. Press, 1974
- Da ist, gehört die Matrix zu keiner nichttrivialen Liste von MOLS.
- MathWorld: Cyclic Group C_8 Die zyklische Gruppe C5 ist nicht enthalten, aber C8 zum Beispiel.
- Colbourn (1984).
- Claupein, Link, Mayus: (PDF) Universität Hohenheim, 2. April 2007, archiviert vom am 23. Februar 2017; abgerufen am 22. Februar 2017.
- Felipe de Mendiburu: agricolae: Statistical Procedures for Agricultural Research. 12. Juni 2016, abgerufen am 22. Februar 2017.
- Formal: Die Permutationsgruppe operiert auf , 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.
- Martin Gardner: Mathematische Knobeleien, dritte Auflage, Verlag Friedrich Vieweg Sohn, Braunschweig/Wiesbaden 1984, ISBN 978-3-528-28321-6, Seite 133
- John T. E. Richardson, Who introduced Western mathematicians to Latin squares ?, British Journal for the History of Mathematics, Band 34, 2019, S. 95–103, Abstract
- Sauveur Construction générale des quarrés magiques, Mémoires de l’Academie Royales des Sciences, 1710, S. 92–138.
- John J. O’Connor, Edmund F. Robertson: Choi.html Lateinisches Quadrat. In: MacTutor History of Mathematics archive.
- Tarry, Le problème des 36 officiers, C. R. Assoc. Franc. Av. Sci., Band 29, 1900, S. 170–203
- Bose, Shrikhande, Parker, Canadian J. Math., Band 12, 1960, S. 189–203
- Orthogonal latin squares, cut-the-knot
- MacNeish, Euler squares, Annals of Mathematics, Band 23, 1922, S. 221–227
- Eine englische Übersetzung erschien schon 1790: On the advantage and economy of feeding sheep in the house with roots, Annals of Agriculture, Band 14, 1790, S. 51–55.