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 over two sets and (which may be the same), each consisting of symbols, is an arrangement of cells, each cell containing an ordered pair , where is in and is in , such that every row and every column contains each element of and each element of exactly once, and that no two cells contain the same ordered pair.
The arrangement of the -coordinates by themselves (which may be thought of as Latin characters) and of the -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 from the Cartesian product occurs exactly once.
Orthogonal Latin squares were studied in detail by Leonhard Euler, who took the two sets to be }, the first upper-case letters from the Latin alphabet, and }, the first 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.This has gone under several names in the literature, formule directrix (Euler), directrix, 1-permutation, and diagonal amongst others. 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 4 + 2 for some positive integer ) , 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,. Errata: the construction of a 4 × 4 set was published by Jacques Ozanam in 1725., the solution is in Fig. 35 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:
SolutionNormal formSolution #1 Solution #2
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:Euler: Recherches sur une nouvelle espece de quarres magiques, written in 1779, published in 1782
Euler was unable to solve the problem, but in this work he demonstrated methods for constructing Graeco-Latin squares where is odd or a multiple of 4. Observing that no order two square exists and being unable to construct an order six square, he conjectured that none exist for any oddly even number The non-existence of order six squares was confirmed in 1901 by Gaston Tarry through a proof by exhaustion. However, Euler's conjecture resisted solution until the late 1950s, but the problem has led to important work in combinatorics.
In early 1959, Raj Chandra Bose and S. S. Shrikhande constructed some counterexamples (dubbed the Euler spoilers) of order 22 using mathematical insights. Their work was inspired by work done by Ernest Parker, and based on their work, within days Parker found a counterexample of order 10. Scan of full article. using a one-hour computer search on a UNIVAC 1206 Military Computer while working at the UNIVAC division of Remington Rand (this was one of the earliest combinatorics problems solved on a digital computer).
In April 1959, Parker, Bose, and Shrikhande presented their paper showing Euler's conjecture to be false for all Thus, Graeco-Latin squares exist for all orders except In the November 1959 edition of Scientific American, Martin Gardner published this result. The front cover is the 10 × 10 refutation of Euler's conjecture.
Thirty-six entangled officers problem
Extensions of mutually orthogonal Latin squares to the quantum domain have been studied since 2017. 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. This setup solves a generalization of the 36 Euler's officers problem, as well as provides a new quantum error detection code, allowing to encode a 6-level system into a three 6-level system that certifies occurrence of one error.
Prior and independent work: Choi Seok-jeong What makes the history of orthogonal Latin squares particularly remarkable is that the concept was not discovered once, but twice — independently, centuries apart, and worlds away. Choi Seok-jeong (최석정; 崔錫鼎; 1646–1715) was a leading statesman of the Joseon dynasty of Korea, serving multiple terms as Yeonguijeong (영의정), the highest ministerial office in the kingdom, equivalent to Prime Minister. Yet alongside his political career, he produced mathematical work of extraordinary depth. In his treatise Gusuryak (구수략; 九數略), published around 1700, Choi constructed a pair of orthogonal Latin squares of order 9 — a feat that predates Leonhard Euler's work on the subject by at least 67 years.H.-Y. Song, "Choi's orthogonal Latin squares is at least 67 years earlier than Euler's", Global KMS Conference, Jeju, Korea, 2008. Choi arrived at this structure through an entirely different intellectual tradition — rooted in Neo-Confucianism, the philosophy of the I Ching, and classical Eastern mathematics — with no known connection to contemporary European scholarship. His construction, named Gugumosubyon-gungyang-do (구구모수변궁양도; 九九母數變宮陽圖) in the Gusuryak, was applied to produce a magic square of order 9 in which every row, column, and diagonal sums to 369. Today, Choi is regarded by scholars as the greatest mathematician of the Joseon period — a rare figure who reached the heights of both political power and mathematical achievement.
Examples of mutually orthogonal Latin squares (MOLS) A set of Latin squares of the same order such that every pair of squares are orthogonal (that is, form a Graeco-Latin square) is called a set of mutually orthogonal Latin squares (or pairwise orthogonal Latin squares) and usually abbreviated as MOLS or MOLS(n) when the order is made explicit.
For example, a set of MOLS(4) is given by:
And a set of MOLS(5):
While it is possible to represent MOLS in a "compound" matrix form similar to the Graeco-Latin squares, for instance, {| class="wikitable" |- | 1,1,1,1 | 2,2,2,2 | 3,3,3,3 | 4,4,4,4 | 5,5,5,5 |- | 2,3,5,4 | 3,4,1,5 | 4,5,2,1 | 5,1,3,2 | 1,2,4,3 |- | 3,5,4,2 | 4,1,5,3 | 5,2,1,4 | 1,3,2,5 | 2,4,3,1 |- | 4,2,3,5 | 5,3,4,1 | 1,4,5,2 | 2,5,1,3 | 3,1,2,4 |- | 5,4,2,3 | 1,5,3,4 | 2,1,4,5 | 3,2,5,1 | 4,3,1,2 |} for the MOLS(5) example above, it is more typical to compactly represent the MOLS as an orthogonal array (see below).
In the examples of MOLS given so far, the same alphabet (symbol set) has been used for each square, but this is not necessary as the Graeco-Latin squares show. In fact, totally different symbol sets can be used for each square of the set of MOLS. For example,
Any two of text, foreground color, background color and typeface form a pair of orthogonal Latin squares: fjords jawbox phlegm qiviut zincky zincky fjords jawbox phlegm qiviut qiviut zincky fjords jawbox phlegm phlegm qiviut zincky fjords jawbox jawbox phlegm qiviut zincky fjords
is a representation of the compounded MOLS(5) example above where the four MOLS have the following alphabets, respectively: the background color: black, maroon, teal, navy, and silver the foreground color: white, red, lime, blue, and yellow the text: fjords, jawbox, phlegm, qiviut, and zincky the typeface family: serif, sans-serif, monospaced, cursive, and slab-serif.
The above table therefore allows for testing five values in each of four different dimensions in only 25 observations instead of 625 (= 54) observations required in a full factorial design. Since the five words cover all 26 letters of the alphabet between them, the table allows for examining each letter of the alphabet in five different typefaces and color combinations.
The number of mutually orthogonal Latin squares The mutual orthogonality property of a set of MOLS is unaffected by Permuting the rows of all the squares simultaneously, Permuting the columns of all the squares simultaneously, and Permuting the entries in any square, independently. 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. The MOLS(4) and MOLS(5) examples at the start of this section have been put in standard form.