Latin square
A square matrix of order 
in which each row and each column are permutations of the elements of a finite set 
consisting of 
elements. The Latin square is said to be constructed on the set 
; usually 
. A Latin square exists for any 
; for example, 
, where
 |
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 
to be the Cayley table of a group it is necessary and sufficient that the following condition (the square criterion) is satisfied: If 
, 
, 
then 
.
From two Latin squares, 
of order 
and 
of order 
, one can always construct a Latin square 
of order 
, for example as follows:
 |
For the number 
of Latin squares of order 
one has the following lower bound:
 |
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 
of reduced Latin squares of order 
one has
 |
Two Latin squares constructed on the same set 
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 
be the number of equivalence classes of Latin squares of order 
. The following first few values of 
and 
are known:'
<tbody> </tbody>
|
Also, 
. The problem of obtaining bounds for 
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 
is said to be complete if for any natural numbers 
, 
, 
, 
, there are numbers 
, 
, 
, 
such that
 |
Algorithms for constructing complete Latin squares are known only for even 
; there are examples of complete squares for certain odd 
.
A Latin subsquare of a given Latin square of order 
is a submatrix of it such that it is itself a Latin square of order 
, 
. Any Latin square of order 
can be a Latin subsquare of a Latin square of order 
if 
.
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 
of a Latin square 
is a set 
consisting of 
cells of the Latin square,
 |
such that 
, 
, 
for 
, 
. One always has 
; if 
, a partial transversal is called a transversal. The existence in a Latin square of order 
of a set of 
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,
 |
does not have a transversal.
In any Latin square of order 
there is at least one partial transversal of length 
. For 
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 
is a matrix of order 
in which part of the cells are filled by the elements of a set 
of cardinality 
, but such that in every row and every column the elements of 
occur at most once. There are partial Latin squares that cannot be completed to a Latin square, for example,
 |
An incomplete Latin square containing exactly 
elements can be completed to a Latin square. It is known that when 
the Cayley tables of two different groups of order 
differ from each other in at least 
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 
-dimensional permutation cube of order 
is an 
-dimensional matrix
 |
of order 
whose elements are the first 
natural numbers and which is such that for any 
the set
 |
 |
is a permutation of the first 
natural numbers. An 
-dimensional hypercube of order 
and class 
is an 
-dimensional matrix of order 
with elements belonging to a set of 
elements, each of which occurs 
times in the matrix, and in every 
-dimensional section of the matrix (that is, among the elements
 |
where 
and the remaining indices run through all the 
values) it occurs 
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
 |
cf. [a1].
P.W. Shor (cf. [a2]) obtained the lower bound 
for the length 
of a partial transversal in a Latin square (of order 
).
The assertion that an incomplete Latin square containing exactly 
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) |
Latin square. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Latin_square&oldid=47587