In combinatorics und im Versuchsplan ist ein lateinisches Quadrat ein n × n Reihe hat sich mit n verschiedenen Symbolen, jedes Auftreten genau einmal in jeder Reihe und genau einmal in jeder Säule gefüllt. Hier ist ein Beispiel:

Der Name "der Latin Square" wird von mathematischen Vorträgen von Leonhard Euler motiviert, der lateinische Charaktere als Symbole verwendet hat.

Natürlich können andere Symbole statt lateinischer Briefe verwendet werden: Im obengenannten Beispiel kann die alphabetische Folge A, B, C durch die Folge der ganzen Zahl 1, 2, 3 ersetzt werden.

Reduzierte Form

Wie man

sagt, wird ein lateinisches Quadrat reduziert (auch, um normalisiert, oder in der Standardform), wenn sowohl seine erste Reihe als auch seine erste Säule in ihrer natürlichen Ordnung sind. Zum Beispiel wird das obengenannte lateinische Quadrat nicht reduziert, weil seine erste Säule A, C, B aber nicht A, B, C. ist

Wir können jedes lateinische Quadrat reduziert machen, indem wir (Umstellung) die Reihen und Säulen permutieren. Hier gibt die Schaltung der zweiten und dritten Reihen der obengenannten Matrix nach

der reduziert wird: Sowohl seine erste Reihe als auch seine erste Säule werden A, B, C alphabetisch bestellt.

Eigenschaften

Orthogonale Reihe-Darstellung

Wenn jeder Zugang eines n × n lateinisches Quadrat wird als ein dreifacher geschrieben (r, c, s), wo r die Reihe ist, ist c die Säule, und s ist das Symbol, wir herrschen vor, eine Reihe von n verdreifacht sich, hat die orthogonale Reihe-Darstellung des Quadrats genannt. Zum Beispiel ist die orthogonale Reihe-Darstellung des ersten lateinischen Quadrats, das oben gezeigt ist:

: {(1,1,1), (1,2,2), (1,3,3), (2,1,2), (2,2,3), (2,3,1), (3,1,3), (3,2,1), (3,3,2)},

wo zum Beispiel das dreifache (2,3,1) Mittel, dass in der Reihe 2 und Spalte 3 dort das Symbol 1 ist. Die Definition eines lateinischen Quadrats kann in Bezug auf die orthogonale Reihe geschrieben werden:

• Ein lateinisches Quadrat ist der Satz von allen verdreifacht sich (r, c, s), wo 1  r, c, s  n, solch, dass alle befohlenen Paare (r, c), alle befohlenen Paare verschieden sind (r, s) verschieden ist, und alle befohlenen Paare (c, s) verschieden sind.

Für jedes lateinische Quadrat gibt es n verdreifacht sich seit der Auswahl irgendwelcher zwei einzigartig bestimmt das dritte. (Sonst würde ein befohlenes Paar mehr erscheinen als einmal im lateinischen Quadrat.)

Die orthogonale Reihe-Darstellung zeigt, dass Reihen, Säulen und Symbole ziemlich ähnliche Rollen spielen, wie unten verständlich gemacht wird.

Gleichwertigkeitsklassen von lateinischen Quadraten

Viele Operationen auf einem lateinischen Quadrat erzeugen ein anderes lateinisches Quadrat (zum Beispiel, es auf den Kopf stellend).

Wenn wir die Reihen permutieren, die Säulen permutieren, und die Namen der Symbole eines lateinischen Quadrats permutieren, herrschen wir vor ein neues lateinisches Quadrat hat gesagt, isotopic zum ersten zu sein. Isotopism ist eine Gleichwertigkeitsbeziehung, so wird der Satz aller lateinischen Quadrate in Teilmengen, genannt isotopy Klassen, solch geteilt, dass zwei Quadrate in derselben Klasse isotopic sind und zwei Quadrate in verschiedenen Klassen nicht isotopic sind.

Ein anderer Typ der Operation ist am leichtesten, das Verwenden der orthogonalen Reihe-Darstellung des lateinischen Quadrats zu erklären. Wenn wir systematisch und durchweg wiederbefehlen, dass sich die drei Sachen in jedem verdreifachen, wird eine andere orthogonale Reihe (und, so, ein anderes lateinisches Quadrat) erhalten. Zum Beispiel können wir ersetzen jeder verdreifacht sich (r, c, s) dadurch (c, r, s), der dem Umstellen des Quadrats entspricht (über seine Hauptdiagonale nachdenkend), oder wir ersetzen konnten, verdreifacht sich jeder (r, c, s) dadurch (c, s, r), der eine mehr komplizierte Operation ist. Zusammen gibt es 6 Möglichkeiten einschließlich "tun nichts", uns gebend, 6 lateinische Quadrate haben das Konjugieren (auch Parastrophen) des ursprünglichen Quadrats genannt.

Schließlich können wir diese zwei Gleichwertigkeitsoperationen verbinden: Wie man sagt, sind zwei lateinische Quadrate Parathema, auch Hauptklasse isotopic, wenn einer von ihnen isotopic zu einem verbundenen vom anderen ist. Das ist wieder eine Gleichwertigkeitsbeziehung, mit genannten Hauptklassen der Klassen der Gleichwertigkeit, Arten oder paratopy Klassen. Jede Hauptklasse enthält bis zu 6 isotopy Klassen.

Zahl

Es gibt keine bekannte leicht berechenbare Formel für die Nummer L (n) von n × n lateinische Quadrate mit Symbolen 1,2..., n. Die genauesten oberen und niedrigeren für großen n bekannten Grenzen sind einzeln weit. Ein klassisches Ergebnis ist

:

(das, das von van Lint und Wilson gegeben ist).

Hier werden wir alle bekannten genauen Werte geben. Es kann gesehen werden, dass die Zahlen außerordentlich schnell wachsen. Für jeden n ist die Zahl von lateinischen Quadraten zusammen n! (n-1)! Zeiten die Zahl von reduzierten lateinischen Quadraten.

Für jeden n enthält jede isotopy Klasse bis dazu (n!) Lateinische Quadrate (ändert sich die genaue Zahl), während jede Hauptklasse entweder 1, 2, 3 oder 6 isotopy Klassen enthält.

Beispiele

Wir führen ein Beispiel eines lateinischen Quadrats von jeder Hauptklasse bis zum Auftrag 5 an.

\begin {bmatrix }\

1

\end {bmatrix }\

\quad

\begin {bmatrix }\

1 & 2 \\

2 & 1

\end {bmatrix }\\quad\begin {bmatrix }\

1 & 2 & 3 \\

2 & 3 & 1 \\

3 & 1 & 2

\end {bmatrix }\

</Mathematik> </Zentrum>

\begin {bmatrix }\

1 & 2 & 3 & 4 \\

2 & 1 & 4 & 3 \\

3 & 4 & 1 & 2 \\

4 & 3 & 2 & 1

\end {bmatrix }\\quad\begin {bmatrix }\ 1 & 2 & 3 & 4 \\

2 & 4 & 1 & 3 \\

3 & 1 & 4 & 2 \\

4 & 3 & 2 & 1\end {bmatrix }\</Mathematik> </Zentrum>\begin {bmatrix }\

1 & 2 & 3 & 4 & 5 \\

2 & 3 & 5 & 1 & 4 \\

3 & 5 & 4 & 2 & 1 \\

4 & 1 & 2 & 5 & 3 \\

5 & 4 & 1 & 3 & 2

\end {bmatrix }\\quad\begin {bmatrix }\ 1 & 2 & 3 & 4 & 5 \\

2 & 4 & 1 & 5 & 3 \\

3 & 5 & 4 & 2 & 1 \\

4 & 1 & 5 & 3 & 2 \\

5 & 3 & 2 & 1 & 4

\end {bmatrix }\</Mathematik> </Zentrum>

Sie, präsentieren beziehungsweise, die Multiplikationstabellen der folgenden Gruppen:

• {0} - die triviale 1-Element-Gruppe
• - die binäre Gruppe
• - zyklische Gruppe des Auftrags 3
• - der Klein vier-Gruppen-
• - zyklische Gruppe des Auftrags 4
• - zyklische Gruppe des Auftrags 5
• der letzte ist ein Beispiel einer Quasigruppe, oder eher eine Schleife, die nicht assoziativ ist.

Anwendungen

Lateinische Quadrate werden in der Statistik und in der Mathematik verwendet.

• Im Design von Experimenten sind lateinische Quadrate ein spezieller Fall von Designs der Reihe-Säule für zwei blockierende Faktoren: Viele Designs der Reihe-Säule werden durch das Verketten lateinischer Quadrate gebaut.
• In der Algebra sind lateinische Quadrate Generalisationen von Gruppen; tatsächlich werden lateinische Quadrate charakterisiert als, die Multiplikationstabellen (Tische von Cayley) Quasigruppen zu sein.

Fehler, der Codes korrigiert

Sätze von lateinischen Quadraten, die zu einander orthogonal sind, haben eine Anwendung als Fehler gefunden, der Codes in Situationen korrigiert, wo Kommunikation durch mehr Typen des Geräusches gestört wird als einfaches weißes Geräusch, solcher als, wenn man versucht, Breitbandinternet über powerlines zu übersenden.

Erstens wird die Nachricht durch das Verwenden mehrerer Frequenzen oder Kanäle, eine übliche Methodik gesandt, die das Signal weniger verwundbar für das Geräusch an irgendwelcher spezifischer Frequenz macht. Ein Brief in der zu sendenden Nachricht wird durch das Senden einer Reihe von Signalen an verschiedenen Frequenzen an aufeinander folgenden Zeitabständen verschlüsselt. Im Beispiel unten werden die Briefe A an L durch das Senden von Signalen an vier verschiedenen Frequenzen in vier Zeitschlitzen verschlüsselt. Der Brief C wird zum Beispiel durch das erste Senden an der Frequenz 3, dann 4, 1 und 2 verschlüsselt.

\begin {Matrix-}\

\\

B \\

C \\

D \\

\end {Matrix-}\

\begin {bmatrix }\ 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\

4 & 3 & 2 & 1 \\

\end {bmatrix }\

\quad\begin {Matrix-}\

E \\

F \\

G \\

H \\

\end {Matrix-}\\begin {bmatrix }\

1 & 3 & 4 & 2 \\

2 & 4 & 3 & 1 \\

3 & 1 & 2 & 4 \\

4 & 2 & 1 & 3 \\

\end {bmatrix }\\quad\begin {Matrix-}\

Ich \\

J \\

K \\

L \\

\end {Matrix-}\\begin {bmatrix }\

1 & 4 & 2 & 3 \\

2 & 3 & 1 & 4 \\

3 & 2 & 4 & 1 \\

4 & 1 & 3 & 2 \\

\end {bmatrix }\</Mathematik> </Zentrum>

Die Verschlüsselung der zwölf Briefe wird von drei lateinischen Quadraten gebildet, die zu einander orthogonal sind. Stellen Sie sich jetzt vor, dass dort Geräusch in Kanälen 1 und 2 während der ganzen Übertragung hinzugefügt hat. Der Brief A würde dann als aufgenommen:

:

12 & 12 & 123 & 124 \\

\end {Matrix} </Mathematik>

Mit anderen Worten im ersten Ablagefach erhalten wir Signale sowohl von der Frequenz 1 als auch von Frequenz 2; während das dritte Ablagefach Signale von Frequenzen 1, 2 und 3 hat. Wegen des Geräusches können wir nicht mehr erzählen, ob die ersten zwei Ablagefächer 1,1 oder 1,2 oder 2,1 oder 2,2 waren. Aber der 1,2 Fall ist der einzige, der eine Folge nachgibt, die einen Brief im obengenannten Tisch, den Brief A. vergleicht

Ähnlich können wir uns einen Ausbruch statisch über alle Frequenzen im dritten Ablagefach vorstellen:

:

1 & 2 & 1234 & 4 \\

\end {Matrix} </Mathematik>

Wieder sind wir im Stande, aus dem Tisch von encodings abzuleiten, dass es der Brief A gewesen sein muss, der wird übersendet. Die Zahl von Fehlern, die dieser Code entdecken kann, ist diejenige weniger als die Zahl von Zeitschlitzen. Es ist auch bewiesen worden, dass, wenn die Zahl von Frequenzen eine Blüte oder eine Macht einer Blüte ist, die orthogonalen lateinischen Quadrate Fehler erzeugen, der Codes entdeckt, die so effizient sind wie möglich.

Mathematische Rätsel

Das Problem der Bestimmung, wenn ein teilweise gefülltes Quadrat vollendet werden kann, um ein lateinisches Quadrat zu bilden, ist NP-complete.

Die populären Rätsel von Sudoku sind ein spezieller Fall von lateinischen Quadraten; jede Lösung eines Rätsels von Sudoku ist ein lateinisches Quadrat. Sudoku erlegt die zusätzliche Beschränkung auf, dass neun besondere 3&times;3 angrenzende Subquadrate auch die Ziffern 1-9 (in der Standardversion) enthalten müssen. Die neueren Rätsel von KenKen sind auch Beispiele von lateinischen Quadraten.

Heraldik

Das lateinische Quadrat erscheint auch in den Armen der Statistischen Gesellschaft Kanadas, in seinem Wappenschild spezifisch erwähnt werden. Außerdem erscheint es im Firmenzeichen der Internationalen Biometric Gesellschaft.

Siehe auch

• Lateinischer Hyperwürfel, der ausfällt
• Der Graeco-Latin Square
• Der Magic Square
• Probleme in lateinischen Quadraten
• Kleine lateinische Quadrate und Quasigruppen
• Mathematik von Sudoku
• Futoshiki
• Der Graph der Saatkrähe, ein Graph, der lateinische Quadrate als sein colorings hat
• Acht Königinnen verwirren
• Block-Design
• Der Word Square

Referenzen

• Vorveröffentlichungskapitel sind online verfügbar.
• J. H. van Lint, R. M. Wilson: Ein Kurs in Combinatorics. Universität von Cambridge Presse 1992, internationale Standardbuchnummer 0-521-42260-4, p. 157

Links

• Lateinische Quadrate in der Enzyklopädie der Mathematik
• Lateinische Quadrate in Java an der Knoten-Kürzung
• Unendliches lateinisches Quadrat (Java) an der Knoten-Kürzung
• Der Magic Square im lateinischen Quadrat