Латын квадраттарының ортогоналдығы және қолданыстары

Mathematical problem
In combinatorial mathematics, two Latin squares of the same size (order) are said to be orthogonal if when superimposed the ordered paired entries in the positions are all distinct. A set of Latin squares, all of the same order, all pairs of which are orthogonal is called a set of mutually orthogonal Latin squares. This concept of orthogonality in combinatorics is strongly related to the concept of blocking in statistics, which ensures that independent variables are truly independent with no hidden confounding correlations. "Orthogonal" is thus synonymous with "independent" in that knowing one variable's value gives no further information about another variable's likely value. An outdated term for pair of orthogonal Latin squares is Graeco Latin square, found in older literature.

A Graeco Latin square or Euler square or pair of orthogonal Latin squares of order n over two sets S and T (which may be the same), each consisting of n symbols, is an n × n arrangement of cells, each cell containing an ordered pair (s, t), where s is in S and t is in T, such that every row and every column contains each element of S and each element of T exactly once, and that no two cells contain the same ordered pair. The arrangement of the s coordinates by themselves (which may be thought of as Latin characters) and of the t coordinates (the Greek characters) each forms a Latin square. A Graeco Latin square can therefore be decomposed into two orthogonal Latin squares. Orthogonality here means that every pair (s, t) from the Cartesian product S × T occurs exactly once. Orthogonal Latin squares were studied in detail by Leonhard Euler, who took the two sets to be 1=S = {A, B, C,  }, the first n upper case letters from the Latin alphabet, and 1=T = {α , β, γ,  },
the first n lower case letters from the Greek alphabet—hence the name Graeco Latin square.

When a Graeco Latin square is viewed as a pair of orthogonal Latin squares, each of the Latin squares is said to have an orthogonal mate. In an arbitrary Latin square, a selection of positions, one in each row and one in each column whose entries are all distinct is called a transversal of that square. Consider one symbol in a Graeco Latin square. The positions containing this symbol must all be in different rows and columns, and furthermore the other symbol in these positions must all be distinct. Hence, when viewed as a pair of Latin squares, the positions containing one symbol in the first square correspond to a transversal in the second square (and vice versa). A given Latin square of order n possesses an orthogonal mate if and only if it has n disjoint transversals. The Cayley table (without borders) of any group of odd order forms a Latin square which possesses an orthogonal mate.

A complete set of MOLS(q) exists whenever q is a prime or prime power. This follows from a construction that is based on a finite field GF(q), which only exist if q is a prime or prime power. The multiplicative group of GF(q) is a cyclic group, and so, has a generator, λ, meaning that all the non zero elements of the field can be expressed as distinct powers of λ. Name the q elements of GF(q) as follows:
α0 = 0, α1 = 1, α2 = λ, α3 = λ2, , αq 1 = λq 2. Now, λq 1 = 1 and the product rule in terms of the α's is αiαj = αt, where t = i + j 1 (mod q 1). The Latin squares are constructed as follows, the (i, j)th entry in Latin square Lr (with r ≠ 0) is Lr(i,j) = αi + αrαj, where all the operations occur in GF(q). In the case that the field is a prime field (q = p a prime), where the field elements are represented in the usual way, as the integers modulo p, the naming convention above can be dropped and the construction rule can be simplified to Lr(i,j) = i + rj, where r ≠ 0 and i, j and r are elements of GF(p) and all operations are in GF(p). The MOLS(4) and MOLS(5) examples above arose from this construction, although with a change of alphabet. Not all complete sets of MOLS arise from this construction. The projective plane that is associated with the complete set of MOLS obtained from this field construction is a special type, a Desarguesian projective plane. There exist non Desarguesian projective planes and their corresponding complete sets of MOLS can not be obtained from finite fields.

A set of k MOLS(n) is equivalent to an edge partition of the complete (k + 2) partite graph Kn, ,n into complete subgraphs of order k + 2.

Mutually orthogonal Latin squares have a great variety of applications. They are used as a starting point for constructions in the statistical design of experiments, tournament scheduling, and error correcting and detecting codes. Euler's interest in Graeco Latin squares arose from his desire to construct magic squares. The French writer Georges Perec structured his 1978 novel Life: A User's Manual around a 10×10 Graeco Latin square.