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 quasi-group; the converse is also true: the multiplication table of a finite quasi-group 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> $ n $ 3 4 5 6 7 8 $ k _ {n} $ 1 2 2 22 563 1 676 257 $ l _ {n} $ 1 4 56 9408 16 942 080 535 281 401 856 $ m _ {n} $ 1 2 12 288 34 560 24 883 200

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 multi-dimensional 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