Mutually orthogonal Latin squares

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.

Orthogonal Latin squares were studied in detail by Leonhard Euler, who took the two sets to be S = {A, B, C, ...}, the first n upper-case letters from the Latin alphabet, and T = {α , β, γ, ...}, the first n lower-case letters from the Greek alphabet—hence the name Graeco-Latin square.

A given Latin square of order n possesses an orthogonal mate if and only if it has n disjoint transversals.

[2] The Cayley table (without borders) of any group of odd order forms a Latin square which possesses an orthogonal mate.

Euler was able to construct Graeco-Latin squares of orders that are multiples of four,[2] and seemed to be aware of the following result.

No group based Graeco-Latin squares can exist if the order is an odd multiple of two (that is, equal to 4k + 2 for some positive integer k).

[3] Although recognized for his original mathematical treatment of the subject, orthogonal Latin squares predate Euler.

In the form of an old puzzle involving playing cards,[4] the construction of a 4 x 4 set was published by Jacques Ozanam in 1725.

[5] The problem was to take all aces, kings, queens and jacks from a standard deck of cards, and arrange them in a 4 x 4 grid such that each row and each column contained all four suits as well as one of each face value.

A common variant of this problem was to arrange the 16 cards so that, in addition to the row and column constraints, each diagonal contains all four face values and all four suits as well.

According to Martin Gardner, who featured this variant of the problem in his November 1959 Mathematical Games column,[6] the number of distinct solutions was incorrectly stated to be 72 by Rouse Ball.

This mistake persisted for many years until the correct value of 144 was found by Kathleen Ollerenshaw.

The question revolves around arranging 36 officers to be drawn from 6 different regiments so that they are ranged in a square so that in each line (both horizontal and vertical) there are 6 officers of different ranks and different regiments.Euler was unable to solve the problem, but in this work he demonstrated methods for constructing Graeco-Latin squares where n is odd or a multiple of 4.

[11][12] However, Euler's conjecture resisted solution until the late 1950s, but the problem has led to important work in combinatorics.

Bose and S. S. Shrikhande constructed some counterexamples (dubbed the Euler spoilers) of order 22 using mathematical insights.

In April 1959, Parker, Bose, and Shrikhande presented their paper showing Euler's conjecture to be false for all n ≥ 7.

In the November 1959 edition of Scientific American, Martin Gardner published this result.

Extensions of mutually orthogonal Latin squares to the quantum domain have been studied since 2017.

[17] In these designs, instead of the uniqueness of symbols, the elements of an array are quantum states that must be orthogonal to each other in rows and columns.

In 2021, an Indian-Polish team of physicists (Rather, Burchardt, Bruzda, Rajchel-Mieldzioć, Lakshminarayan, and Życzkowski) found an array of quantum states that provides an example of mutually orthogonal quantum Latin squares of size 6; or, equivalently, an arrangement of 36 officers that are entangled.

The mutual orthogonality property of a set of MOLS is unaffected by Using these operations, any set of MOLS can be put into standard form, meaning that the first row of every square is identical and normally put in some natural order, and one square has its first column also in this order.

Name the q elements of GF(q) as follows: 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).

There exist non-Desarguesian projective planes and their corresponding complete sets of MOLS can not be obtained from finite fields.

[32] An orthogonal array, OA(k,n), of strength two and index one is an n2 × k array A (k ≥ 2 and n ≥ 1, integers) with entries from a set of size n such that within any two columns of A (strength), every ordered pair of symbols appears in exactly one row of A (index).

[33] For example, the MOLS(4) example given above and repeated here, can be used to form an OA(5,4): where the entries in the columns labeled r and c denote the row and column of a position in a square and the rest of the row for fixed r and c values is filled with the entry in that position in each of the Latin squares.

The ordered pairs of entries in each row of the orthogonal array in the columns labeled r and c, will be considered to be the coordinates of the n2 points of the net.

The points on each line are given by (each row below is a parallel class of lines): A transversal design with k groups of size n and index λ, denoted T[k, λ; n], is a triple (X, G, B) where:[36] The existence of a T[k,1;n] design is equivalent to the existence of k-2 MOLS(n).

They are used as a starting point for constructions in the statistical design of experiments, tournament scheduling, and error correcting and detecting codes.

The French writer Georges Perec structured his 1978 novel Life: A User's Manual around a 10×10 Graeco-Latin square.