Latin square

A square matrix of order $n$ in which each row and each column are permutations of the elements of a finite set $S$ consisting of $n$ elements. The Latin square is said to be constructed on the set $S$; usually $S = \{ 1 \dots n \}$. A Latin square exists for any $n$; for example, $A = \| a _ {ij} \|$, where

$$a _ {ij} \equiv i + j - 1 ( \mathop{\rm mod} n ) ,\ \ i , j = 1 \dots n ,$$

is a Latin square.

Every Latin square can be regarded as the multiplication table of a quasi-group; the converse is also true: the multiplication table of a finite quasi-group is a Latin square. For a Latin square $A = \| a _ {ij} \|$ to be the Cayley table of a group it is necessary and sufficient that the following condition (the square criterion) is satisfied: If $a _ {ik} = a _ {i _ {1} k _ {1} }$, $a _ {il} = a _ {i _ {1} l _ {1} }$, $a _ {jk} = a _ {j _ {1} k _ {1} } ,$ then $a _ {jl} = a _ {j _ {1} l _ {1} }$.

From two Latin squares, $A = \| a _ {kl} \|$ of order $n$ and $B = \| b _ {rs} \|$ of order $m$, one can always construct a Latin square $C = \| c _ {ij} \|$ of order $mn$, for example as follows:

$$c _ {ij} = b _ {rs} + ( a _ {kl} - 1 ) m ,\ \ i = r + m ( k - 1 ) ,\ \ j = s + m ( l - 1 ) .$$

For the number $L _ {n}$ of Latin squares of order $n$ one has the following lower bound:

$$L _ {n} \geq n ! ( n - 1 ) ! \dots 1 ! .$$

A Latin square is said to be reduced (or a Latin square of standard form) if the elements of its first row and first column are in the natural order. For the number $l _ {n}$ of reduced Latin squares of order $n$ one has

$$L _ {n} = n ! ( n - 1 ) ! l _ {n} ,\ \ l _ {n} \geq m _ {n} = ( n - 2 ) ! ( n - 3 ) ! \dots 1 !$$

Two Latin squares constructed on the same set $S$ are said to be equivalent or isotopic if one of them can be obtained from the other by a permutation of rows and columns and renaming of elements. Let $k _ {n}$ be the number of equivalence classes of Latin squares of order $n$. The following first few values of $l _ {n}$ and $k _ {n}$

are known:

<tbody> </tbody>
 $n$ 3 4 5 6 7 8 $k _ {n}$ 1 2 2 22 563 1 676 257 $l _ {n}$ 1 4 56 9408 16 942 080 535 281 401 856 $m _ {n}$ 1 2 12 288 34 560 24 883 200

Also, $l _ {9} = 377 597 570 964 258 816$. The problem of obtaining bounds for $l _ {n}$ remains unsolved (1982).

In the theory of design of experiments it is required to construct Latin squares with various restrictions on the position of elements in them. A Latin square on $\{ 1 \dots n \}$ is said to be complete if for any natural numbers $\alpha$, $\beta$, $\alpha \neq \beta$, $1 \leq \alpha , \beta \leq n$, there are numbers $i$, $j$, $k$, $l$ such that

$$( a _ {ij} , a _ {i,j+} 1 ) = \ ( \alpha , \beta ) \ \textrm{ and } \ \ ( a _ {kl} , a _ {k+} 1,l ) = ( \alpha , \beta ) ,$$

Algorithms for constructing complete Latin squares are known only for even $n$; there are examples of complete squares for certain odd $n$.

A Latin subsquare of a given Latin square of order $n$ is a submatrix of it such that it is itself a Latin square of order $k$, $k < n$. Any Latin square of order $k$ can be a Latin subsquare of a Latin square of order $n$ if $n \geq 2 k$.

In the construction of orthogonal Latin squares an important role is played by the concept of a transversal of a Latin square. A partial transversal of length $t$ of a Latin square $A = \| a _ {ij} \|$ is a set $T$ consisting of $t$ cells of the Latin square,

$$T = \{ ( i _ {1} , j _ {1} ) \dots ( i _ {t} , j _ {t} ) \} ,$$

such that $i _ {k} \neq i _ {l}$, $j _ {k} \neq j _ {l}$, $a _ {i _ {k} j _ {k} } \neq a _ {i _ {l} j _ {l} }$ for $k \neq l$, $1 \leq k , l \leq t$. One always has $t \leq n$; if $t = n$, a partial transversal is called a transversal. The existence in a Latin square of order $n$ of a set of $n$ disjoint transversals is a necessary and sufficient condition for the existence of an orthogonal mate, i.e. a Latin square on the same symbols orthogonal to the given one. The Latin square of order 6,

$$\begin{array}{c} 012 345 \\ 120 453 \\ 201 534 \\ 345 012 \\ 451 320 \\ 534 201 \\ \end{array}$$

does not have a transversal.

In any Latin square of order $n \geq 7$ there is at least one partial transversal of length $t \geq ( 2 n + 1 ) / 3$. For $n \geq 4$ one can always construct a Latin square such that both its main diagonals are transversals.

Some generalizations of Latin squares.

A partial, or incomplete, Latin square of order $n$ is a matrix of order $n$ in which part of the cells are filled by the elements of a set $S$ of cardinality $n$, but such that in every row and every column the elements of $S$ occur at most once. There are partial Latin squares that cannot be completed to a Latin square, for example,

$$\begin{array}{cccc} 1 & . & . & . \\ . & 2 & 3 & 4 \\ . & . & . & . \\ . & . & . & . \\ \end{array}$$

An incomplete Latin square containing exactly $n - 1$ elements can be completed to a Latin square. It is known that when $n > 4$ the Cayley tables of two different groups of order $n$ differ from each other in at least $2 n$ places.

An infinite Latin square is an infinite matrix whose elements are natural numbers that occur in each row and each column exactly once.

There are a few generalizations of the concept of a Latin square to the multi-dimensional case. Thus, an $m$- dimensional permutation cube of order $n$ is an $m$- dimensional matrix

$$A = \| a _ {i _ {1} \dots i _ {m} } \|$$

of order $n$ whose elements are the first $n$ natural numbers and which is such that for any $k$ the set

$$a _ {i _ {1} \dots i _ {k-} 1 1i _ {k+} 1 \dots i _ {m} } ,\ a _ {i _ {1} \dots i _ {k-} 1 2i _ {k+} 1 \dots i _ {m} } \dots$$

$$a _ {i _ {1} \dots i _ {k-} 1 ni _ {k+} 1 \dots i _ {m} }$$

is a permutation of the first $n$ natural numbers. An $m$- dimensional hypercube of order $n$ and class $r$ is an $m$- dimensional matrix of order $n$ with elements belonging to a set of $n ^ {r}$ elements, each of which occurs $n ^ {m-} r$ times in the matrix, and in every $( n - 1 )$- dimensional section of the matrix (that is, among the elements

$$a _ {i _ {1} \dots i _ {k-} 1 i _ {k} ^ {0} i _ {k+} 1 \dots i _ {m} } ,$$

where $i _ {k} ^ {0} = \textrm{ const }$ and the remaining indices run through all the $n$ values) it occurs $n ^ {m-} r- 1$ times.

References

 [1] V.N. Sachkov, "Combinatorial methods in discrete mathematics" , Moscow (1977) (In Russian) [2] J. Dênes, "Latin squares and their applications" , Acad. Press (1974) [3] M. Hall, "Combinatorial theory" , Blaisdell (1967) [4] H.J. Ryser, "Combinatorial mathematics" , Carus Math. Monogr. , 14 , Math. Assoc. Amer. (1963)

The truth of the van der Waerden permanent conjecture (cf. Permanent) implies that

$$L _ {n} \geq \ \frac{( n!) ^ {2n} }{n ^ {n ^ {2} } } ,$$

cf. [a1].

P.W. Shor (cf. [a2]) obtained the lower bound $t \geq n - c ( \mathop{\rm log} n) ^ {2}$ for the length $t$ of a partial transversal in a Latin square (of order $n > 7$).

The assertion that an incomplete Latin square containing exactly $n - 1$ elements may be completed to a Latin square is known as the Evans conjecture. It was proved by B. Smetaniuk [a3].

For a recent survey on Latin squares see [a4].

For a discussion of the role of Latin squares and sets of mutually orthogonal Latin squares in the design of experiments cf. [a5].

References

 [a1] R.M. Wilson, "Nonisomorphic Steiner triple systems" Math. Z. , 135 (1974) pp. 303–313 [a2] P.W. Shor, "A lower bound for the length of a partial transversal in a Latin square" J. Comb. Theory (A) , 33 (1982) pp. 1–8 [a3] B. Smetaniuk, "A new construction of Latin squares I: A proof of the Evans conjecture" Ars. Comb. , 11 (1981) pp. 155–172 [a4] D. Jungnickel, "Lateinische Quadrate, ihre Geometrien und ihre Gruppen" Jahresber. Deutsch. Math. Verein. , 86 (1984) pp. 69–108 [a5] A. Penfold Street, D.J. Street, "Combinatorics of experimental design" , Clarendon Press (1987)
How to Cite This Entry:
Latin square. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Latin_square&oldid=47587
This article was adapted from an original article by V.M. Mikheev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article