Orthogonal Latin squares

A pair of Latin squares (cf. Latin square) , of order such that if , . The squares and are called orthogonal mates. The matrix obtained by the superposition of on is called a Greco–Latin or Euler square; its elements are all the ordered pairs of elements from . The orthogonality of and is denoted by . An example of a pair of orthogonal Latin squares and their Euler square for is:

A Latin square of order has an orthogonal mate if and only if non-intersecting transversals exist in (see Latin square). If is a Latin square of order (or ) with a subsquare of order (or ) all cells of which, with the possible exception of (or ) cells, are filled by not more than (or ) elements, then no orthogonal mate exists for . For all , , there are examples of pairs of orthogonal Latin squares, while for , examination of all possibilities proves that there are no such pairs [3].

A number of Latin squares of the same order are called pairwise orthogonal or mutually orthogonal if any two of them are orthogonal. If is the maximum possible number of pairwise orthogonal Latin squares, then .

A set of pairwise orthogonal Latin squares of order is called complete. When , a set of pairwise orthogonal Latin squares can always be made complete. Up till now (1989), the only complete sets known are for , where is a natural number and is a prime number (i.e. ). The following lower bounds have been obtained for :

<tbody> </tbody> 7 52 53 63 90 2 3 4 5 6

Moreover, , , , , , and it has been proved that as ; for example, for sufficiently large (see [2]). If () or (), and if the square-free part of the number contains even one prime factor (), then no complete set of pairwise orthogonal Latin squares of order exists. For example, no complete sets exist for , ().

Complete sets of pairwise orthogonal Latin squares have a statistical application in the creation of symmetric balanced incomplete block designs (cf. Block design) with parameters , , , since complete sets can also be interpreted as finite projective planes (see [2]).

Many methods for constructing orthogonal Latin squares have been proposed (see [2]). They all aim at obtaining the largest possible set of pairwise orthogonal Latin squares of order . Each method belongs to one of the following two groups. The first group (direct constructions) contains methods whose characteristic peculiarity is that they provide a method for constructing a "basic" Latin square and demonstrate how to interchange their rows and columns so as to obtain an orthogonal mate. The second group (recursive methods) contains methods which use known methods for constructing orthogonal Latin squares of lower order to construct orthogonal Latin squares of given order.

If is a Latin square of order on the set , then the ordered set of permutations , , defined by the equations uniquely determines . Not every ordered set of permutations corresponds to a Latin square. If and are two Latin squares defined in the above way by permutations and of the set , then if and only if is a Latin square. If one defines products , , where and are permutations of , then, for example, if and only if is a Latin square.

The methods in the first group are usually used when is the multiplication table of a finite group , i.e. , , ; the difference between one method and the other lies in the choice of the group , the choice of the one-to-one mappings of the group onto itself, and the use of the products , , , etc.

If is an additive group, then the condition reduces to the fact that is an orthomorphism of , i.e. a one-to-one mapping of onto itself such that if for , then . For example, five pairwise orthogonal Latin squares of order 12 have been found after defining four non-trivial orthomorphisms of the Abelian group which is the direct product of the cyclic groups of order 6 and 2 (see [2], [6]).

If is the additive group of a finite field , , then all constructions are significantly simplified, and the following complete set of pairwise orthogonal Latin squares is obtained:

It may be noted that a Latin square of order such that (i.e. a self-orthogonal Latin square) exists if and only if .

The use of the direct product of Latin squares forms the basis of the following method, related to the second group. Let and be orthogonal Latin squares of order on a set , while and are orthogonal Latin squares of order on a set ; the direct products of matrices and will then be orthogonal Latin squares of order on the set . If , then this method yields the bound .

The following construction lies at the basis of many other methods of the second group. Let be pairwise orthogonal Latin squares of order on the set and let be orthogonal Latin squares of order on the set . In order to obtain two Latin squares and of order on the set , rows and columns with numbers with unfilled cells are added to , with the result that a partial Latin square of order containing in the top left corner is obtained. The cells of and having the same numbers as the cells of that contain the element form a common -transversal, , for and . The elements of the -transversal in when are placed in the -th column (and in the -th row) in the same order in which they stood in the rows and columns of , and the number is put in their place. It remains to insert in the bottom right corner of the partial square in order to complete .

is constructed from and in the same way, but only by using transversals with the numbers . The squares and will be Latin, but not necessarily orthogonal. A pair of orthogonal Latin squares of order can always be obtained if , is odd and ; it has been shown, using the above construction, how to obtain a pair of orthogonal Latin squares of order when (), (see [2]).

The applications of orthogonal Latin squares in statistics, information theory and in the theory of experimental design (cf. [2]) require the construction of special forms of orthogonal Latin squares and the transfer of the concept of orthogonality to other subjects. Thus, orthogonal arrays (cf. Orthogonal array) are a generalization of orthogonal Latin squares. Two partial Latin squares of the same order are orthogonal if when superposed on each other the ordered pairs in the cells are all different. A Latin square is said to be imbedded in the Latin square if coincides with a submatrix of (with the exception of the empty cells of ). Each square in a set of pairwise orthogonal Latin squares can be imbedded in a Latin square in such a way that the Latin squares obtained will be orthogonal (see [6]).

References

[1]	V.N. Sachkov, "Combinatorial methods in discrete mathematics" , Moscow (1977) (In Russian)
[2]	J. Dénes, A.D. Keedwell, "Latin squares and their applications" , Acad. Press (1974)
[3]	M. Hall, "Combinatorial theory" , Wiley, reprint (1986)
[4]	H.J. Ryser, "Combinatorial mathematics" , Math. Assoc. Amer. (1963)
[5]	A. Hedayat, E. Seiden, "On the theory and application of sum composition of Latin squares and orthogonal Latin squares" Pacif. J. Math. , 54 : 2 (1974) pp. 85–113
[6]	Ch. Lindner, "Embedding orthogonal partial Latin squares" Proc. Amer. Math. Soc. , 59 : 1 (1976) pp. 184–186

Comments

For a complete proof of the fact that there are no pairs of orthogonal Latin squares for see [a1]. Some more bounds for are as follows:

1) For the first few non-prime powers: , , , , , , . See [a1] or [a2]. These references contain a table of lower bounds on for .

2) In addition to the main article above one has

<tbody> </tbody> 11 77 781 65279 3 6 7 30

See [a1].

3) The best asymptotic bound today (1989) is (see [a3]).

4) The Bruck–Ryser theorem states that there is no complete set of pairwise orthogonal Latin squares if () or () and if the square-free part of contains a prime (). In conjunction with Bruck's completion theorem, this non-existence result gives the only known non-trivial upper bounds on , e.g. for ; for (see [a1]).

A set of mutually orthogonal Latin squares (MOLS) of order is equivalent to a net of order and degree (or, dually, a transversal design). This allows one to consider the study of MOLS as a part of finite geometry and to associate geometric invariants (like automorphism groups and groups of projectivities) with them. Cf. [a1] for fundamental results and [a2] for a recent survey.

The 4 known MOLS of order 15 also have been obtained by using orthomorphisms. The construction of MOLS by orthomorphisms of an additively written group of order can be more conveniently phrased by using "difference matrices" over : Let be a matrix with rows and columns with entries from . is called a difference matrix if the differences contain each element of exactly once (for all choices of rows and of ). can be used to construct MOLS of order . Most direct constructions are more sophisticated versions of this approach (cf. [a1] and [a2]), and are therefore also called "difference methods" .

The most important recursive constructions are much more involved and use the geometric interpretation of MOLS as transversal designs, see [3] and [a1].

For the existence of self-orthogonal Latin squares see [a1]. For applications of orthogonal Latin squares see also [a4].

References

[a1]	T. Beth, D. Jungnickel, H. Lenz, "Design theory" , Cambridge Univ. Press (1986)
[a2]	D. Jungnickel, "Latin squares, their geometries and their groups. A survey" , Proc. IMA Workshops on Coding and Design Theory Minneapolis, 1988 , Springer (to appear)
[a3]	T. Beth, "Eine Bemerkung zur Abschätzung der Anzahl orthogonaler lateinischer Quadrate mittels Siebverfahren" Abh. Math. Sem. Hamburg , 53 (1983) pp. 284–288
[a4]	A.S. Hedayat, J. Stufken, "Orthogonal arrays and their applications" (To appear)