Mutually orthogonal Latin squares

In combinatorics, 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 older term for a pair of orthogonal Latin squares is Graeco-Latin square, introduced by Euler.

Graeco-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.

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 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.

Existence 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. Thus Graeco-Latin squares exist for all odd orders as there are groups that exist of these orders. Such Graeco-Latin squares are said to be group based. Euler was able to construct Graeco-Latin squares of orders that are multiples of four, and seemed to be aware of the following result. Unable to find a solution for a 6 square, and knowing that 2 square had no possible solution, Euler conjectured that no group based Graeco-Latin squares could exist if the order was an odd multiple of two (that is, equal to 4k + 2 for some positive integer k) , that is, 2, 6, 10, 14, 18, 22 and so on. Later on, though, it was proven that only 2 and 6 didn't have solutions.

History Although Euler is recognized for his original mathematical treatment of the subject, orthogonal Latin squares predate him. In the form of an old puzzle involving playing cards, the construction of a 4 × 4 set was published by Jacques Ozanam in 1725. The problem was to take all aces, kings, queens and jacks from a standard deck of cards, and arrange them in a 4 × 4 grid such that each row and each column contained all four suits as well as one of each face value. This problem has several solutions. 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, 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. Each of the 144 solutions has eight reflections and rotations, giving 1152 solutions in total. The 144×8 solutions can be categorized into the following two equivalence classes:

For each of the two solutions, 242 = 576 solutions can be derived by permuting the four suits and the four face values, independently. No permutation will convert the two solutions into each other, because suits and face values are different.

Thirty-six officers problem

A problem similar to the card problem above was circulating in St. Petersburg in the late 1700s and, according to folklore, Catherine the Great asked Euler to solve it, since he was residing at her court at the time. This problem is known as the thirty-six officers problem, and Euler introduced it as follows:

A very curious question, which has exercised for some time the ingenuity of many people, has involved me in the following studies, which seem to open a new field of analysis, in particular the study of combinations. 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.

… excerpt ends here. Continue reading the full article.