Lateinisches Quadrat

Ein lateinisches Quadrat ist ein Quadrat aus $n\cdot n$ Feldern, 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 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 diskreten Mathematik und insbesondere in der Kombinatorik sind lateinische Quadrate von Bedeutung, da sie im Zusammenhang zu manchen endlichen Objekten stehen. Lateinische Quadrate treten beispielsweise als Verknüpfungstabellen von Quasigruppen und Gruppen auf, und eine Parallelenklasse einer endlichen affinen Ebene lässt sich bei geeigneter Wahl eines Koordinatensystems als lateinisches Quadrat interpretieren.

Es folgt jeweils ein lateinisches Quadrat der Ordnung 3 und 4: $\begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\ \end{bmatrix} \quad\quad \begin{bmatrix} a & b & d & c \\ b & c & a & d \\ c & d & b & a \\ d & a & c & b \end{bmatrix}$

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 bei diesem Vorgehen aus dem Quadrat hinausfallen; stattdessen trägt man es in der folgenden Reihe ganz links ein.

Das erste der obigen Beispiele kann auf diese Art konstruiert werden.

Ein lateinisches Quadrat der Ordnung 9 mit der Zusatzbedingung, dass in der Aufteilung in 9 $3\times 3$-Quadrate in jedem dieser Quadrate alle Symbole jeweils genau einmal auftreten, führt zu dem Zahlenrätsel Sudoku.