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=15140