Latin square

A 7th order Latin square at Gonville and Caius College , Cambridge

A Latin square is a square scheme with rows and columns, with each field being occupied by one of different symbols, so that each symbol appears exactly once in each row and in each column. The natural number is called the order of the Latin square. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

The numbers from to , or different letters or different colors are often used as symbols . The mathematician Leonhard Euler dealt intensively with such squares; he used the Latin alphabet as a set of symbols . The name Latin square goes back to it. ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

In the modern combinatorics and discrete mathematics are a symbol amount mainly the numbers up , more rarely the numbers to be used, and the scheme is as special - matrix considered. ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle n-1}$ ${\displaystyle n\times n}$

Every Latin square can be understood as a connection table (Cayley table) of a finite quasi- group, conversely, every finite quasi-group determines an equivalence class of Latin squares.

Two different Latin squares of the same order can be orthogonal to each other. In synthetic geometry , certain sets of pairwise orthogonal Latin squares of the order finite affine planes are assigned. This results in a necessary and sufficient combinatorial condition for the existence of levels of order : Such a level exists if and only if there is a complete list of pairwise orthogonal squares of order . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Outside of mathematics in the narrower sense, Latin squares are used, among other things, in agricultural experimental planning as block systems and in statistical experimental planning.

Presentation, properties and terms

Representation as a matrix

A Latin square of the order is a square matrix whose entries are all natural numbers from to , in such a way that each of these numbers appears exactly once in each row and in each column of the matrix. This property can be tested in a matrix (for example with a computer algebra system like Maple ) as follows: The following equations must be fulfilled for the entries in the matrix : ${\displaystyle n}$ ${\displaystyle n\times n}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle M_{j,k}}$ ${\displaystyle M}$

• For each line , and ${\displaystyle k,\,1\leq k\leq n}$ ${\displaystyle \sum _{j=1}^{n}2^{M_{j,k}-1}=2^{n}-1}$
• must apply to each column . ${\displaystyle j,\,1\leq j\leq n}$ ${\displaystyle \sum _{k=1}^{n}2^{M_{j,k}-1}=2^{n}-1}$

Triple representation: OAR

A Latin square of order can also be represented as a set of different triples . Thereby stands for the number of a row ("row") in the Latin square, for the number of a column and for the number in the square there. The rule for Latin squares is met if and only if no two of the triples in two entries match. This representation is known as the orthogonal array representation (OAR) of the Latin square. ${\displaystyle n}$ ${\displaystyle Q}$ ${\displaystyle n^{2}}$ ${\displaystyle (r,s,z)\in \{1,2,\ldots n\}^{3}}$ ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle z}$

The OAR suggests a geometric interpretation for a Latin square: The number in a cell of the Latin square can be understood as the height of a cuboid that is to be built on this cell as a base. This turns the Latin square into a spatial bar chart - compare the illustration for the example below.

A related interpretation of the Latin square of the order can also be seen in the picture : If one only fills the cube at the top of each of the columns of the bar chart, then one obtains a three-dimensional picture of axially parallel unit cubes in a larger axially parallel cube with the edge length . The sub-cube with the grid coordinates is “filled” if and only if the Latin square belongs to the OAR. An arrangement of partial cubes in such a cube of edge length belongs to a Latin square of the order precisely when the large cube is opaque when viewed through the partial cube in the three axially parallel directions, i.e. appears completely filled when projected in one axial direction. ${\displaystyle n}$ ${\displaystyle n^{2}}$ ${\displaystyle n}$ ${\displaystyle (r,s,z)}$ ${\displaystyle (r,s,z)}$ ${\displaystyle n^{2}}$ ${\displaystyle n}$ ${\displaystyle n}$

The triples of the OAR representation can be interpreted as spatial coordinates or as heights of columns on the Latin square. In this picture, for the sake of clarity, only the first and the last column (s = 1 and s = 4) of the Latin square of order 4 (red numbers on the base) are shown as columns. The cube at the top of these columns is highlighted in color.

This interpretation makes it clear that the OAR of a Latin square becomes the OAR of a Latin square not only when the row and column numbers are swapped (a transposition in the matrix display), but even when all character numbers are swapped with the row numbers or the column numbers!

example

The example in the illustration on the right shows the first Latin square C below, the second, D , is created by swapping the - with the - axis. If you swap the - with the - axis in the first square C , the square D is also created , because its matrix is ​​symmetrical. ${\displaystyle r}$ ${\displaystyle z}$ ${\displaystyle s}$ ${\displaystyle z}$

${\displaystyle C=\left[{\begin{array}{cccc}3&4&2&1\\4&3&1&2\\1&2&4&3\\2&1&3&4\end{array}}\right];\;D=\left[{\begin{array}{cccc}4&3&1&2\\3&4&2&1\\1&2&4&3\\2&1&3&4\end{array}}\right]}$

The triple representations are

${\displaystyle {\begin{array}{rllll}Q_{C}=\{&(1,1,3),&(1,2,4),&(1,3,2),&(1,4,1),\\&(2,1,4),&(2,2,3),&(2,3,1),&(2,4,2),\\&(3,1,1),&(3,2,2),&(3,3,4),&(3,4,3),\\&(4,1,2),&(4,2,1),&(4,3,3),&(4,4,4)\quad \}\end{array}}}$

or.

${\displaystyle {\begin{array}{rllll}Q_{D}=\{&(1,3,1),&(1,4,2),&(1,2,3),&(1,1,4),\\&(2,4,1),&(2,3,2),&(2,1,3),&(2,2,4),\\&(3,1,1),&(3,2,2),&(3,4,3),&(3,3,4),\\&(4,2,1),&(4,1,2),&(4,3,3),&(4,4,4)\quad \}\end{array}}}$

Number of Latin squares

The numbers of Latin squares of the order form sequence A002860 in OEIS . There is no known formula for the sequence that is easy to calculate . The best known lower and upper bounds for large orders are still far apart. A classic estimate is: ${\displaystyle L(n)}$ ${\displaystyle n=1,2,3,\ldots }$ ${\displaystyle L(n)}$ ${\displaystyle n}$

${\displaystyle {\frac {\left(n!\right)^{2n}}{n^{n^{2}}}}\leq L(n)\leq \prod _{k=1}^{n}\left(k!\right)^{n/k}.}$

The numbers of the structurally different Latin squares (i.e. the squares cannot be made identical by rotation, mirroring or permutation of the symbols) up to order 7 form the sequence A264603 in OEIS .

Reduced Latin Squares

A Latin square is called reduced or normalized if the various symbols are in their "natural order" in the 1st line and in the 1st column . In the triple display with numbers as symbols, this means: for the first row and for the first column. The normalization of any Latin square can always be achieved by interchanging rows and columns. The 3rd order square in the examples below is normalized by swapping the 2nd with the third row, the 4th order square is already reduced. ${\displaystyle n}$ ${\displaystyle \{(1,1,1);(1,2,2);\ldots (1,n,n)\}\subset Q}$ ${\displaystyle \{(1,1,1);(2,1,2);\ldots (n,1,n)\}\subset Q}$

The numbers of reduced Latin squares of the order form sequence A000315 in OEIS . The following applies to the number of all Latin squares ${\displaystyle l(n)}$ ${\displaystyle n=1,2,3,\ldots }$ ${\displaystyle L(n)}$ ${\displaystyle L(n)=n!\cdot (n-1)!\cdot l(n).}$

Examples

Latin squares of the order 3 or 4 in the matrix representation:

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

Tripeldarstellung the left square is: . If you were to swap the numbers 1 and 2 in the first row, the triple (1st row, 1st column contains 2) and the triple (3rd row, 1st column contains 2) would be in two places (column and character ) match and the square would no longer be a Latin square. ${\displaystyle \{(1,1,1);(1,2,2);(1,3,3);(2,1,3);(2,2,1);(2,3,2);(3,1,2);(3,2,3);(3,3,1)\}}$ ${\displaystyle (1,1,2)}$ ${\displaystyle (3,1,2)}$

It is easy to give a Latin square for any given order : To do this, one distributes various symbols arbitrarily on the first row of the square. The following rows are now filled in successively by taking over the previous row shifted by one to the right. The rightmost symbol of the previous row would fall out of the square; instead, it is entered in the new row on the far left. ${\displaystyle n}$ ${\displaystyle n}$

The example of order 3 is constructed in this way, in the example of order 4, instead of shifting to the right, every row was cyclically exchanged to the left . If you start with this construction, as in the example shown, with a sorted first line with the numbers , you always get a reduced Latin square, which can be interpreted as a link table of the remainder class group . To do this, the numbers entered must all be reduced by 1. ${\displaystyle 1,2,\ldots n}$ ${\displaystyle \left(\mathbb {Z} /n\mathbb {Z} ,+\right)}$

Orthogonal Latin Squares and MOLS

Two Latin squares and are called orthogonal if no two of the pairs match that result from writing the entries from and next to each other in a new square scheme . In matrix representation: ${\displaystyle Q}$ ${\displaystyle R}$ ${\displaystyle n^{2}}$ ${\displaystyle Q}$ ${\displaystyle R}$ ${\displaystyle S}$

${\displaystyle Q:={\begin{bmatrix}3&2&1\\2&1&3\\1&3&2\end{bmatrix}}\quad R:={\begin{bmatrix}2&3&1\\1&2&3\\3&1&2\end{bmatrix}}\longrightarrow S={\begin{bmatrix}32&23&11\\21&12&33\\13&31&22\end{bmatrix}}}$

The Latin squares and combined here to form the matrix are orthogonal. In this case, the square represented by is called a Greco-Latin square . The numbers of pairs of orthogonal Latin squares of the order form sequence A072377 in OEIS . ${\displaystyle S}$ ${\displaystyle Q}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle n=1,2,3,\ldots }$

The following sentence is important for use in geometry:

Let be a set of Latin squares, the order , with the property that two different Latin squares are always orthogonal to each other. Then contains at most elements. ${\displaystyle {\mathfrak {L}}}$ ${\displaystyle n\geq 2}$ ${\displaystyle L_{1},L_{2}\in {\mathfrak {L}}}$ ${\displaystyle {\mathfrak {L}}}$ ${\displaystyle n-1}$

(assumed) maximum numbers of MOLS

Order n	R (n)
0	${\displaystyle \infty }$
1	${\displaystyle \infty }$
2	1
3	2
4th	3
5	4th
6th	1
7th	6th
8th	7th
9	8th
10	${\displaystyle {}\geq 2\;({}=2?)}$
11	10
12	${\displaystyle {}\geq 5}$
13	12

A list of pairwise orthogonal Latin squares of the order is said to be complete . The sequence of the largest possible number of pairwise orthogonal Latin squares ( MOLS = mutually orthogonal Latin squares ) of the order is sequence A001438 in OEIS , what is known about the values ​​to is shown in the table on the right, the values ​​for 0 and 1 are convention. The following applies: ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle R(n)}$ ${\displaystyle n}$ ${\displaystyle n=13}$

• Is and , then is , because a list of pairwise orthogonal Latin squares can always be completed. ${\displaystyle n>4}$ ${\displaystyle R(n)\geq n-3}$ ${\displaystyle R(n)=n-1}$ ${\displaystyle n-3\geq 2}$
• For is , for is ${\displaystyle n>6}$ ${\displaystyle R(n)\geq 2}$ ${\displaystyle n>52}$ ${\displaystyle R(n)\geq 4.}$
• Is a prime number and then is . ${\displaystyle p}$ ${\displaystyle r\in \mathbb {N} }$ ${\displaystyle R(p^{r})=p^{r}-1}$
• To date, it is not known whether there is a natural number that is not a prime power and for which applies. ${\displaystyle n}$ ${\displaystyle R(n)=n-1}$
• For sufficiently large is , so is . ${\displaystyle n}$ ${\displaystyle R(n)\geq n^{1/17}-2}$ ${\displaystyle \lim _{n\to \infty }R(n)=\infty }$
• It is valid for ever , because of a list of MOLS of order and a list of t MOLS of order always can be a list of the order MOLS produce. The procedure is demonstrated here using a trivial example: ${\displaystyle n,m\geq 3}$ ${\displaystyle R(n\cdot m)\geq \min(R(n),R(m))}$ ${\displaystyle t}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle t}$ ${\displaystyle n\cdot m}$

${\displaystyle A={\begin{bmatrix}{\color {Red}1}&{\color {Blue}2}\\{\color {Green}2}&{\color {Cyan}1}\end{bmatrix}}{\mathrel {\widehat {=}}}{\begin{bmatrix}{\color {Red}0}&{\color {Blue}1}\\{\color {Green}1}&{\color {Cyan}0}\end{bmatrix}},\quad B={\begin{bmatrix}1&2&3\\2&3&1\\3&1&2\\\end{bmatrix}}}$

${\displaystyle \longrightarrow {\begin{bmatrix}{\color {Red}0}\cdot 3+1&{\color {Red}0}\cdot 3+2&{\color {Red}0}\cdot 3+3&{\color {Blue}1}\cdot 3+1&{\color {Blue}1}\cdot 3+2&{\color {Blue}1}\cdot 3+3\\{\color {Red}0}\cdot 3+2&{\color {Red}0}\cdot 3+3&{\color {Red}0}\cdot 3+1&{\color {Blue}1}\cdot 3+2&{\color {Blue}1}\cdot 3+3&{\color {Blue}1}\cdot 3+1\\{\color {Red}0}\cdot 3+3&{\color {Red}0}\cdot 3+1&{\color {Red}0}\cdot 3+2&{\color {Blue}1}\cdot 3+3&{\color {Blue}1}\cdot 3+1&{\color {Blue}1}\cdot 3+2\\{\color {Green}1}\cdot 3+1&{\color {Green}1}\cdot 3+2&{\color {Green}1}\cdot 3+3&{\color {Cyan}0}\cdot 3+1&{\color {Cyan}0}\cdot 3+2&{\color {Cyan}0}\cdot 3+3\\{\color {Green}1}\cdot 3+2&{\color {Green}1}\cdot 3+3&{\color {Green}1}\cdot 3+1&{\color {Cyan}0}\cdot 3+2&{\color {Cyan}0}\cdot 3+3&{\color {Cyan}0}\cdot 3+1\\{\color {Green}1}\cdot 3+3&{\color {Green}1}\cdot 3+1&{\color {Green}1}\cdot 3+2&{\color {Cyan}0}\cdot 3+3&{\color {Cyan}0}\cdot 3+1&{\color {Cyan}0}\cdot 3+2\end{bmatrix}}={\begin{bmatrix}{\color {Red}1}&{\color {Red}2}&{\color {Red}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}\\{\color {Red}2}&{\color {Red}3}&{\color {Red}1}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}4}\\{\color {Red}3}&{\color {Red}1}&{\color {Red}2}&{\color {Blue}6}&{\color {Blue}4}&{\color {Blue}5}\\{\color {Green}4}&{\color {Green}5}&{\color {Green}6}&{\color {Cyan}1}&{\color {Cyan}2}&{\color {Cyan}3}\\{\color {Green}5}&{\color {Green}6}&{\color {Green}4}&{\color {Cyan}2}&{\color {Cyan}3}&{\color {Cyan}1}\\{\color {Green}6}&{\color {Green}4}&{\color {Green}5}&{\color {Cyan}3}&{\color {Cyan}1}&{\color {Cyan}2}\\\end{bmatrix}}}$

Magic squares

According to its construction, a Greco-Latin square of the order n , if the pairs of numbers are bijectively recoded to successive natural numbers - e.g. B. - all line sums and row sums are the same, for example the square S can be the square ${\displaystyle (j,k)\mapsto (j-1)\cdot n+k}$ ${\displaystyle {\hat {S}}}$

${\displaystyle S={\begin{bmatrix}32&23&11\\21&12&33\\13&31&22\end{bmatrix}}\quad \longrightarrow \quad {\hat {S}}={\begin{bmatrix}8&6&1\\4&2&9\\3&7&5\end{bmatrix}}}$

assign where every row and every column has the magic sum . ${\displaystyle s=15}$

If the sum of the two diagonals in such a square is also equal to the sum of the rows and columns, then one speaks of a magic square .

Applications

Algebra: Latin squares and linking tables

Link table of the cyclic group C ₅ as a Latin square in color. The neutral element is black. Colored linking tables are used in the online math encyclopedia MathWorld , as are those in grayscale

The first image on the left shows the group's full linkage table : ${\displaystyle C_{5}=\left(\mathbb {Z} /5\mathbb {Z} ,+\right)}$

${\displaystyle +}$ 0 1 2 3 4th 0 0 1 2 3 4th 1 1 2 3 4th 0 2 2 3 4th 0 1 3 3 4th 0 1 2 4th 4th 0 1 2 3

${\displaystyle \longrightarrow \left[{\begin{array}{ccccc}0&1&2&3&4\\1&2&3&4&0\\2&3&4&0&1\\3&4&0&1&2\\4&0&1&2&3\end{array}}\right]\longrightarrow \left[{\begin{array}{ccccc}1&2&3&4&5\\2&3&4&5&1\\3&4&5&1&2\\4&5&1&2&3\\5&1&2&3&4\end{array}}\right]}$

In the middle matrix, the row and column headings, i.e. the group elements linked with "+", have been left out, so this matrix represents a Latin square with the set of symbols that is common for residual classes. If you add 1 to each entry, the result is a Latin square with the standard amount of symbols . This Latin square is normalized here because the group elements of the group for the link table were arranged in their "natural order" as a multiple of the generating element 1 and this group is cyclical . ${\displaystyle \{0,1,2,3,4\}}$ ${\displaystyle \{1,2,3,4,5\}}$ ${\displaystyle C_{5}}$

It must be noted that there is generally no specific arrangement for the elements of a group or quasi-group: If the symmetrical group is based on elements, then a permutation that successively affects the rows and columns of the link table (including their row or column headings) is used, another valid link table of the same group from the original table (left); the Latin square assigned to the group (right) also changes. ${\displaystyle S_{n}}$ ${\displaystyle n}$ ${\displaystyle \pi \in S_{n}}$

Formally and more generally, the following applies: If the order in the matrix is a Latin square , then there is a quasi-group with elements that - with a suitable arrangement and numbering of their elements - the matrix has as the content of its link table. Just the Latin squares by a similar row and column permutation and a "renumbering" from arising, so for the true, can be regarded as a link tables of this quasi group. ${\displaystyle M=(M_{j,k})}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle (M_{j,k})}$ ${\displaystyle N=(N_{j,k})}$ ${\displaystyle \pi \in S_{n}}$ ${\displaystyle \rho \in S_{n}}$ ${\displaystyle M=(M_{j,k})}$ ${\displaystyle N_{\pi (j),\pi (k)}=\rho \left(M_{j,k}\right)\,(1\leq j,k\leq n)}$

• If you choose the arrangement of the elements of a finite loop , i.e. a quasi-group with a left and right neutral element at the same time , so that the first element appears in the link table and assigns the numbers to the elements in their otherwise arbitrary order in sequence , then is the contents of their table of associations, written with the associated natural numbers, a reduced Latin square of order . (The number stands for the number of elements of ). ${\displaystyle L}$ ${\displaystyle e}$ ${\displaystyle e}$ ${\displaystyle 1,2,\ldots \#L}$ ${\displaystyle \#L}$ ${\displaystyle \#L}$ ${\displaystyle L}$
• A quasi-group, which has the Latin square of the order as the content of its connection table, is commutative if and only if the matrix is symmetric , that is, if holds. In the case of a commutative quasi-group, the elements can always be numbered so that the content of the multiplication table is a reduced Latin square. It should be noted that here the first row of the square can only be brought into line with the column headings of the link table - and thus at the same time the first column with the row headings - if the quasi-group is a loop. ${\displaystyle M=(M_{j,k})}$ ${\displaystyle n}$ ${\displaystyle (M_{j,k})}$ ${\displaystyle M_{k,j}=M_{j,k}\,(1\leq j,k\leq n)}$

Geometry: Orthogonal Latin Squares and Finite Planes

From a complete list of pairwise orthogonal Latin squares of the order , a finite affine plane of the order can be constructed and vice versa. This is how it works: ${\displaystyle {\mathfrak {L}}=\{L_{1},L_{2},\ldots L_{n-1}\}}$ ${\displaystyle n}$ ${\displaystyle n}$

• The point set consists of the pairs of natural numbers from 1 to : ${\displaystyle n}$

${\displaystyle {\mathcal {P}}=\{(j,k):1\leq j,k\leq n\}.}$

• Each Latin square defines a set of parallels in the plane: ${\displaystyle L_{i}\in {\mathfrak {L}},\;(1\leq i\leq n-1)}$ ${\displaystyle R_{i}}$
• The family of parallels consists of the straight lines ${\displaystyle R_{i}=\{g_{i,m}:1\leq m\leq n-1\}}$

${\displaystyle g_{i,m}=\{(j,k):\,1\leq j,k\leq n\,\land \,(L_{i})_{j,k}=m\}.}$

• There are also two "axis directions", and with the straight lines ${\displaystyle R_{0}=\{g_{0,m}:1\leq m\leq n\}}$ ${\displaystyle R_{n}=\{g_{n,m}:1\leq m\leq n\}}$

${\displaystyle g_{0,m}=\{(j,m):1\leq j\leq n\}\quad \mathrm {bzw.} \quad g_{n,m}=\{(m,k):1\leq k\leq n\}.}$

• The straight set is the union of the same crowds as defined: . ${\displaystyle {\mathcal {G}}=\bigcup _{i=0}^{n}R_{i}}$

Conversely, one can choose an affine coordinate system in a finite affine plane of order n and assign numbers as "combinatorial coordinates" to the points on the first axis, i.e. the ternary body elements via any bijection except for the archetype n of the origin O , so that ${\displaystyle (O,E_{1},E_{2})}$ ${\displaystyle \beta :\{1,2,\ldots n\}\rightarrow K=OE_{1}}$

${\displaystyle K=OE_{1}=\{\beta (1),\beta (2),\beta (3),\ldots \beta (n)=O\}}$ applies.

This gives you a unique pair of numbers for each point on the plane using the coordinate representation based on the point base . Each of the parallel sets except the two sets parallel to the axes defines a Latin square as described above and the squares determined in this way are orthogonal in pairs. Expressed by the ternary connection T - also determined by the list of orthogonal Latin squares - the straight lines then have the straight line equations: ${\displaystyle (O,E_{1},E_{2})}$ ${\displaystyle (x,y)\in K^{2}=(OE_{1})^{2}}$ ${\displaystyle (\beta ^{-1}(x),\beta ^{-1}(y))=(j,k)\in \{1,2,\ldots n\}^{2}}$ ${\displaystyle n-1}$

• ${\displaystyle g_{0,m}:\;y=\beta (m)\;(1\leq m\leq n)}$,
• ${\displaystyle g_{n,m}:\;T(O,y,x)=x=\beta (m)\;(1\leq m\leq n)}$ and
• ${\displaystyle g_{i,m}:\;T(\beta (i),y,x)=\beta (m)\Leftrightarrow (L_{i})_{j,k}=m\land \beta (j)=x\land \beta (k)=y\;(1\leq m\leq n,1\leq i\leq n-1).}$

Because every finite affine plane of order has a projective plane of the same order as a projective closure and every finite projective plane can be slotted in such a way that a finite affine plane of the same order arises: ${\displaystyle n}$

For each there is a projective plane of order if and only if there are pairwise orthogonal Latin squares of order . ${\displaystyle n\geq 2}$ ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n}$

If you carry out the construction described here with an incomplete list of MOLS, you get an incidence structure with points on every straight line and sets of parallels, i.e. a so-called - network . ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m+2<n+1}$ ${\displaystyle (m+2,n)}$

Construction of orthogonal Latin squares from ternary solids

If a finite ternary field , then for each one becomes a quasi-group through the connection . With the same arrangement of the elements of for the multiplication tables, the Latin squares for two such combinations are always orthogonal to one another with different factors . A ternary body of the order always gives a complete list of pairwise orthogonal Latin squares. ${\displaystyle (K,T,0,1)}$ ${\displaystyle K}$ ${\displaystyle a\in K\setminus \{0\}}$ ${\displaystyle x\star _{a}y=T(a,y,x)}$ ${\displaystyle (K,\star _{a})}$ ${\displaystyle K}$ ${\displaystyle \star _{a},\star _{b}}$ ${\displaystyle a\neq b;\,a,b\in K\setminus \{0\}}$ ${\displaystyle n}$ ${\displaystyle n-1}$

Examples

The remainder class field is a ternary field. The contents of the multiplication tables for the quasi-group connections described above - since there is a body, the following applies here - are: ${\displaystyle K=\mathbb {Z} /5\mathbb {Z} }$ ${\displaystyle \star _{a},a\in \{1,2,3,4\}}$ ${\displaystyle K}$ ${\displaystyle x\star _{a}y=T(a,y,x)=x+a\cdot y}$

${\displaystyle \left[{\begin{array}{ccccc}0&1&2&3&4\\1&2&3&4&0\\2&3&4&0&1\\3&4&0&1&2\\4&0&1&2&3\end{array}}\right],\left[{\begin{array}{ccccc}0&2&4&1&3\\1&3&0&2&4\\2&4&1&3&0\\3&0&2&4&1\\4&1&3&0&2\end{array}}\right],\left[{\begin{array}{ccccc}0&3&1&4&2\\1&4&2&0&3\\2&0&3&1&4\\3&1&4&2&0\\4&2&0&3&1\end{array}}\right],\left[{\begin{array}{ccccc}0&4&3&2&1\\1&0&4&3&2\\2&1&0&4&3\\3&2&1&0&4\\4&3&2&1&0\end{array}}\right].}$

For the standard notation, 0 has to be replaced by 5, then you have created a set of 4 pairwise orthogonal Latin squares. Analogously, pairwise orthogonal Latin squares can always be determined for each prime power using the corresponding quasi-group links in the finite field . ${\displaystyle p^{r}}$ ${\displaystyle \star _{a},a\in \mathbb {F} _{p^{r}}\setminus \{0\}}$ ${\displaystyle \mathbb {F} _{p^{r}}}$ ${\displaystyle p^{r}-1}$

Each of these Latin squares then describes the incidence relation in one of the sets of parallels of the affine plane as shown in the previous section. ${\displaystyle p^{r}+1}$ ${\displaystyle \mathbb {F} _{p^{r}}}$

Math puzzles

• The question of whether a partially filled square can be completed to a Latin square is a NP-complete problem in the language of complexity theory .
• A Latin square of the 9th order with the additional condition that all symbols appear exactly once in the division into nine squares in each of these squares leads to the number puzzle Sudoku . ${\displaystyle 3\times 3}$

Statistical design of experiments

An agronomist wants to find out what concentration of fertilizer will maximize the amount of crops harvested. To do this, he divides his field into four by four individual areas. In each of the areas 16 is one of the four fertilizer concentrations , , or with used. However, the growing conditions in the 16 areas are inhomogeneous. In -direction the gradient increases, while in -direction the ground becomes deeper and deeper. In addition to the fertilizer concentration, the two block factors of slope and depth can also have an influence on the harvest yield, which must be taken into account in the test plan. If you have two block factors and one factor of interest, use a Latin square as a design. Each of the three factors has four factor levels, which in R generates the following test design with the function from the package : ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle D}$ ${\displaystyle D-C=C-B=B-A>0}$ ${\displaystyle x}$ ${\displaystyle y}$design.lsdagricolae

Area	Row (slope)	Column (thoroughness)	Fertilizer concentration
1	1	1	A.
2	1	2	C.
3	1	3	D.
4th	1	4th	B.
5	2	1	C.
6th	2	2	A.
7th	2	3	B.
8th	2	4th	D.
9	3	1	B.
10	3	2	D.
11	3	3	A.
12	3	4th	C.
13	4th	1	D.
14th	4th	2	B.
15th	4th	3	C.
16	4th	4th	A.

	1	2	3	4th
1	A.	C.	D.	B.
2	C.	A.	B.	D.
3	B.	D.	A.	C.
4th	D.	B.	C.	A.

Equivalence classes of Latin squares

There are many different transformations that can be applied to a Latin square to create a new Latin square:

1. You can mirror the square (in matrix notation) on the main diagonal, i.e. transpose the matrix representation,
2. you can permute the rows and / or columns of the Latin square,
3. you can rename the entered number symbols bijectively,
4. you can read the square "from bottom to top" or from "right to left" ...

The transformations mentioned in 4. are special cases of row or column permutations.

Important for the application and useful for counting the possible Latin squares of a fixed order are the sets of transformations described below, through which an equivalent class division is introduced on the set of all Latin squares of the order (with symbols off ). ${\displaystyle n}$ ${\displaystyle \{1,2,\ldots ,n\}}$

Parastrophy

Two Latin squares called parastroph each other when in the OAR as triples by a permutation emerge from one another, so if true. For example, the row number swaps with the column number and thus corresponds to the transposition in the matrix display. Each class of Latin square parastrophic to one another contains 1, 2, 3 or 6 different Latin squares, this is a consequence of the orbit formula . See also quasi-group # parastrophies . ${\displaystyle Q_{1},Q_{2}}$ ${\displaystyle \pi \in S_{3}}$ ${\displaystyle (r,s,z)\in Q_{1}\Leftrightarrow \pi (r,s,z)\in Q_{2}}$ ${\displaystyle \pi =(1,2)\in S_{3}}$

Isotopy

Two Latin squares are called isotopic to each other if they emerge apart through a combination of row and column permutations and bijective renaming of the entries. The numbers of isotope classes of Latin squares of the order form sequence A040082 in OEIS . See also quasi-group # morphisms . ${\displaystyle a_{n}}$ ${\displaystyle n}$

Main classes

If one combines the equivalence relations parastrophy and isotopy, one arrives at a new equivalence class division, the division into the so-called main classes . Two Latin squares belong to the same main class if they can be converted into one another by a combination of parastrophy and isotope operations. Each main class contains 1, 2, 3 or 6 isotope classes. The numbers of the main classes of Latin squares of the order form sequence A003090 in OEIS . ${\displaystyle h_{n}}$ ${\displaystyle n}$

literature

Technical articles on individual questions

• Charles Colbourn : The complexity of completing partial latin squares . In: Discrete Applied Mathematics . tape 8 , 1984, pp. 25-30 , doi : 10.1016 / 0166-218X (84) 90075-1 .

Design of experiments and design theory

• Jürgen Bortz: Statistics for human and social scientists . 6th edition. Springer Medizin Verlag, Heidelberg 2005, ISBN 978-3-540-21271-3 .
• Jürgen Bortz: Research Methods and Evaluation for Human and Social Scientists . 4th edition. Springer Medizin Verlag, Heidelberg 2006, ISBN 978-3-540-33305-0 .
• Jeffrey H. Dinitz , Douglas Robert Stinson: A Brief Introduction to Design Theory . In: JH Dinitz and DR Stinson (Eds.): Contemporary Design Theory: A Collection of Surveys . John Wiley & Sons, New York 1992, ISBN 0-471-53141-3 , chap. 1 , p. 1-12 .
• Klaus Hinkelmann, Oscar Kempthorne: Design and Analysis of Experiments Set . 2nd Edition. I and II. John Wiley & Sons, New York 2008, ISBN 978-0-470-38551-7 (English, publisher's page about the book [accessed February 28, 2012]).

Combinatorics and Discrete Mathematics

• Jacobus Hendricus van Lint , RM Wilson: A Course in Combinatorics . 2nd Edition. Cambridge University Press, Cambridge 2001, ISBN 0-521-80340-3 .
• Jiří Matoušek, Jaroslav Nešetřil: Discrete Mathematics . A journey of discovery. Springer, Berlin / Heidelberg / New York / ... 2002, ISBN 3-540-42386-9 , pp. 157 ff . ( Online - English: Invitation to Discrete Mathematics . Translated by Hans Mielke, textbook that requires little previous knowledge - advanced school mathematics up to the 2nd semester of mathematics studies).

programming

• Donald E. Knuth : Volume 4A: Combinatorial Algorithms, Part 1 . In: The Art of Computer Programming . 1st edition. Addison-Wesley, Reading MA 2011, ISBN 0-201-03804-8 , pp. xv and 883 ff . (English, overview of the complete works [accessed on February 28, 2012]).

Web links

• Eric W. Weisstein : Latin Square . In: MathWorld (English).
• VM Mikheev (originator): Latin square . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).
• VM Mikheev (originator): Orthogonal Latin squares . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).
• Harder than Sudoku: Euler's squares. In: Spectrum of Science. Retrieved February 28, 2012 (puzzle applet that requires coloring in an Euler's square (Greek-Latin square)). 
• Lars Døvling Andersen: The History of Latin Squares. (PDF; 1.2 MB) preprint. In: The History of Combinatorics. Robin J. Wilson, December 2007, accessed February 28, 2012 (History of Latin Squares). 
• Hans Peter Gramatke: Euler's squares. Digression. In: Hans Peters mathematical-technical-algorithmic-linguistic conglomeration. April 2, 2003, accessed on February 28, 2012 (private page with interesting and amusing facts about Latin and magic squares and some variants). 
• Aale de Winkel: The Magic Encyclopedia. January 8, 2001, Retrieved February 28, 2012 (Spreadsheet programs ( Microsoft Excel ) for generating magic and Latin squares). 

References and comments

1. ↑ Hinkelmann and Kempthorne (2008)
2. ^ The latin square. In: A field guide to Experimental design. Washington State University, Tree Fruit Research and Extension Center, August 16, 2000, accessed February 28, 2012 . 
3. ↑ The sum sets the "bit" with the valency in an n -digit binary number for every number that appears in the row or column . In order for the tested matrix to represent a Latin square with certainty, the additional requirement must be fulfilled that all entries are natural numbers. This is not guaranteed by the test itself. (Knuth, 2011). ${\displaystyle I}$ ${\displaystyle 2^{l-1}}$
4. ^ Lint & Wilson
5. ↑ ^{a b c d e} Matoušek & Nešetřil, 8.3 Orthogonal Latin squares .
6. ↑ This use of the attribute “orthogonal” has nothing to do with the English term “orthogonal array representation” explained in the article!
7. ↑ Formally more correct but less clear, the entries of the matrix S would have to be written as pairs of numbers.
8. ↑ J. Dénes, AD Keedwell: Latin squares and their applications . Acad. Press, 1974
9. ↑ There is, the matrix does not belong to any nontrivial list of MOLS. ${\displaystyle R(2)=1}$ ${\displaystyle A}$
10. ↑ MathWorld: Cyclic Group C_8 The cyclic group C ₅ is not included, but C ₈ for example.
11. ↑ Colbourn (1984).
12. ^ Claupein, Link, Mayus: Creation and implementation of field tests. (PDF) (No longer available online.) In: Creation and implementation of field tests. University of Hohenheim, April 2, 2007, archived from the original on February 23, 2017 ; accessed on February 22, 2017 . Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.  
13. ↑ Felipe de Mendiburu: agricolae: Statistical Procedures for Agricultural Research. June 12, 2016. Retrieved February 22, 2017 . 
14. ↑ Formal: The permutation group operates on , the set of all triples from positive integers to n . The OAR of the original Latin square is mapped onto the OAR of a Latin square, which can also coincide with the starting square. ${\displaystyle S_{3}}$ ${\displaystyle \{1,2,\ldots n\}^{3}}$