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 quasigroup; the converse is also true: the multiplication table of a finite quasigroup 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>

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 multidimensional 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) 
Comments
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) Zbl 0622.05001 
Latin square. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Latin_square&oldid=52779