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
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.
|||V.N. Sachkov, "Combinatorial methods in discrete mathematics" , Moscow (1977) (In Russian)|
|||J. Dênes, "Latin squares and their applications" , Acad. Press (1974)|
|||M. Hall, "Combinatorial theory" , Blaisdell (1967)|
|||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
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].
|[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. V.M. Mikheev (originator), Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Latin_square&oldid=15140