Latin squares

In combinatorics and in experimental design, a Latin square is an ''n'' × ''n'' array filled with ''n'' different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin square is

The name "Latin square" was inspired by mathematical papers by Leonhard Euler (1707–1783), who used Latin characters as symbols, but any set of symbols can be used: in the above example, the alphabetic sequence A, B, C can be replaced by the integer sequence 1, 2, 3. Euler began the general theory of Latin squares.

History

The Korean mathematician Choi Seok-jeong was the first to publish an example of Latin squares of order nine, in order to construct a magic square in 1700, predating Leonhard Euler by 67 years.

Reduced form

A Latin square is said to be ''reduced'' (also, ''normalized'' or ''in standard form'') if both its first row and its first column are in their natural order. For example, the Latin square above is not reduced because its first column is A, C, B rather than A, B, C.

Any Latin square can be reduced by permuting (that is, reordering) the rows and columns. Here switching the above matrix's second and third rows yields the following square:

This Latin square is reduced; both its first row and its first column are alphabetically ordered A, B, C.

Properties

Orthogonal array representation

If each entry of an ''n'' × ''n'' Latin square is written as a triple (''r'',''c'',''s''), where ''r'' is the row, ''c'' is the column, and ''s'' is the symbol, we obtain a set of ''n''² triples called the orthogonal array representation of the square. For example, the orthogonal array representation of the Latin square

is

: ,
where for example the triple (2, 3, 1) means that in row 2 and column 3 there is the symbol 1. Orthogonal arrays are usually written in array form where the triples are the rows, such as:

The definition of a Latin square can be written in terms of orthogonal arrays:
* A Latin square is a set of ''n''² triples (''r'', ''c'', ''s''), where 1 ≤ ''r'', ''c'', ''s'' ≤ ''n'', such that all ordered pairs (''r'', ''c'') are distinct, all ordered pairs (''r'', ''s'') are distinct, and all ordered pairs (''c'', ''s'') are distinct.

This means that the ''n''² ordered pairs (''r'', ''c'') are all the pairs (''i'', ''j'') with 1 ≤ ''i'', ''j'' ≤ ''n'', once each. The same is true of the ordered pairs (''r'', ''s'') and the ordered pairs (''c'', ''s'').

The orthogonal array representation shows that rows, columns and symbols play rather similar roles, as will be made clear below.

Equivalence classes of Latin squares

Many operations on a Latin square produce another Latin square (for example, turning it upside down).

If we permute the rows, permute the columns, and permute the names of the symbols of a Latin square, we obtain a new Latin square said to be '' isotopic'' to the first. Isotopism is an equivalence relation, so the set of all Latin squares is divided into subsets, called ''isotopy classes'', such that two squares in the same class are isotopic and two squares in different classes are not isotopic.

Another type of operation is easiest to explain using the orthogonal array representation of the Latin square. If we systematically and consistently reorder the three items in each triple (that is, permute the three columns in the array form), another orthogonal array (and, thus, another Latin square) is obtained. For example, we can replace each triple (''r'',''c'',''s'') by (''c'',''r'',''s'') which corresponds to transposing the square (reflecting about its main diagonal), or we could replace each triple (''r'',''c'',''s'') by (''c'',''s'',''r''), which is a more complicated operation. Altogether there are 6 possibilities including "do nothing", giving us 6 Latin squares called the conjugates (also parastrophes) of the original square.

Finally, we can combine these two equivalence operations: two Latin squares are said to be ''paratopic'', also ''main class isotopic'', if one of them is isotopic to a conjugate of the other. This is again an equivalence relation, with the equivalence classes called ''main classes'', ''species'', or ''paratopy classes''. Each main class contains up to six isotopy classes.

Number of Latin squares

There is no known easily computable formula for the number of Latin squares with symbols . The most accurate upper and lower bounds known for large are far apart. One classic result is that
$\prod_^n \left(k!\right)^\geq L_n\geq\frac.$

A simple and explicit formula for the number of Latin squares was published in 1992, but it is still not easily computable due to the exponential increase in the number of terms. This formula for the number of Latin squares is
$L_n = n! \sum_^ (-1)^ \binom,$
where is the set of all -matrices, is the number of zero entries in matrix , and is the permanent of matrix .

The table below contains all known exact values. It can be seen that the numbers grow exceedingly quickly. For each , the number of Latin squares altogether is times the number of reduced Latin squares .

For each , each isotopy class contains up to Latin squares (the exact number varies), while each main class contains either 1, 2, 3 or 6 isotopy classes.

The number of structurally distinct Latin squares (i.e. the squares cannot be made identical by means of rotation, reflection, and/or permutation of the symbols) for = 1 up to 7 is 1, 1, 1, 12, 192, 145164, 1524901344 respectively .

Examples

We give one example of a Latin square from each main class up to order five.

$\begin 1 \end \quad \begin 1 & 2 \\ 2 & 1 \end \quad \begin 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end$

$\begin 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \end \quad \begin 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \\ 3 & 1 & 4 & 2 \\ 4 & 3 & 2 & 1 \end$

$\begin 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 \quad \begin 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$

They present, respectively, the multiplication tables of the following groups:
* – the trivial 1-element group
*$\mathbb_2$ – the binary group
*$\mathbb_3$ – cyclic group of order 3
*$\mathbb_2 \times \mathbb_2$ – the Klein four-group
*$\mathbb_4$ – cyclic group of order 4
*$\mathbb_5$ – cyclic group of order 5
* the last one is an example of a quasigroup, or rather a loop, which is not associative.

Transversals and rainbow matchings

A transversal in a Latin square is a choice of ''n'' cells, where each row contains one cell, each column contains one cell, and there is one cell containing each symbol.

One can consider a Latin square as a complete bipartite graph in which the rows are vertices of one part, the columns are vertices of the other part, each cell is an edge (between its row and its column), and the symbols are colors. The rules of the Latin squares imply that this is a proper edge coloring. With this definition, a Latin transversal is a matching in which each edge has a different color; such a matching is called a rainbow matching.

Therefore, many results on Latin squares/rectangles are contained in papers with the term "rainbow matching" in their title, and vice versa.

Some Latin squares have no transversal. For example, when ''n'' is even, an ''n''-by-''n'' Latin square in which the value of cell ''i'',''j'' is (''i''+''j'') mod ''n'' has no transversal. Here are two examples:$\begin 1 & 2 \\ 2 & 1 \end \quad \begin 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ 3 & 4 & 1 & 2 \\ 4 & 1 & 2 & 3 \end$In 1967, H. J. Ryser

HOME


Content is Copyleft
Website design, code, and AI is Copyrighted (c) 2014-2017 by Stephen Payne


Consider donating to Wikimedia



As an Amazon Associate I earn from qualifying purchases