Namespaces
Variants
Actions

Latin square

From Encyclopedia of Mathematics
Jump to: navigation, search

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>
3 4 5 6 7 8
1 2 2 22 563 1 676 257
1 4 56 9408 16 942 080 535 281 401 856
1 2 12 288 34 560 24 883 200

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)
How to Cite This Entry:
Latin square. V.M. Mikheev (originator), Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Latin_square&oldid=15140
This text originally appeared in Encyclopedia of Mathematics - ISBN 1402006098