View source for Mutually orthogonal Latin squares

{{Short description|Mathematical problem}}
In [[Combinatorics|combinatorial mathematics]], two [[Latin square]]s 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#Combinatorics|orthogonality in combinatorics]] is strongly related to the concept of [[Blocking (statistics)|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.

==Graeco-Latin squares==
A '''Graeco-Latin square''' or '''Euler square''' or pair of '''orthogonal Latin squares''' of order {{math|''n''}} over two [[Set (mathematics)|set]]s {{math|''S''}} and {{math|''T''}} (which may be the same), each consisting of {{math|''n''}} symbols, is an {{math|''n'' &times; ''n''}} arrangement of cells, each cell containing an [[Ordered pair|ordered pair]] {{math|(''s'', ''t'')}}, where {{math|''s''}} is in {{math|''S''}} and {{math|''t''}} is in {{math|''T''}}, such that every row and every column contains each element of {{math|''S''}} and each element of {{math|''T''}} exactly once, and that no two cells contain the same ordered pair.

<gallery caption="Graeco-Latin squares (pairs of orthogonal Latin squares)" class="center" mode="nolines" widths="175px" heights="150px">
GraecoLatinSquare-Order3.svg|Order 3
GrecoLatinSquare-Order4.svg|Order 4
GraecoLatinSquare-Order5.png|Order 5
</gallery>

The arrangement of the {{math|''s''}}-coordinates by themselves (which may be thought of as Latin characters) and of the {{math|''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 {{math|(''s'',&nbsp;''t'')}} from the [[Cartesian product]] {{math|''S'' &times; ''T''}} occurs exactly once.

Orthogonal Latin squares were studied in detail by [[Biography:Leonhard Euler|Leonhard Euler]], who took the two sets to be {{math|1=''S''&nbsp;=&nbsp;{''A'',&nbsp;''B'',&nbsp;''C'',&nbsp;...}}}, the first {{math|''n''}} upper-case letters from the Latin alphabet, and {{math|1=''T''&nbsp;=&nbsp;{α&nbsp;,&nbsp;β,&nbsp;γ,&nbsp;...}}},
the first {{math|''n''}} lower-case letters from the Greek alphabet&mdash;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.<ref>This has gone under several names in the literature, ''formule directrix'' (Euler), ''directrix'', ''1-permutation'', and ''diagonal'' amongst others. {{harv|Dénes|Keedwell|1974|loc=p. 29}}</ref> 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.<ref name=DK155>{{harvnb|Dénes|Keedwell|1974|loc=p. 155}}</ref>

The [[Cayley table]] (without borders) of any [[Group (mathematics)|group]] of odd order forms a Latin square which possesses an orthogonal mate.<ref name=DK155 />

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,<ref name=DK155 /> 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 4{{mvar|k}} + 2 for some positive integer {{mvar|k}}).<ref>{{harvnb|Dénes|Keedwell|1974|p=156}}</ref>

===History===

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,<ref>{{citation|first=Donald|last=Knuth|url=https://books.google.com/books?id=IkuEBAAAQBAJ&pg=PT28 |title=The Art of Computer Programming|volume=4A: Combinatorial Algorithms Part 1|year=2011|publisher=Addison-Wesley|pages= xv+883pp|isbn=978-0-201-03804-0}}. Errata: [https://cs.stanford.edu/~knuth/all4a.ps.gz]</ref> the construction of a 4 x 4 set was published by Jacques Ozanam in 1725.<ref>{{citation|first=Jacques|last=Ozanam|url=https://archive.org/details/nquicontiennent00ozangoog/page/n447 |title=Recreation mathematiques et physiques|volume=IV|page= 434|year=1725}}, the solution is in [https://books.google.com/books?id=6JP6Hz5EHYQC&pg=PA476 Fig. 35]</ref> 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. 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 [[Biography:Martin Gardner|Martin Gardner]], who featured this variant of the problem in his November 1959 Mathematical Games column,<ref name=Gardner>{{harvnb|Gardner|1966|loc=pp. 162-172}}</ref> 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 [[Biography:Kathleen Ollerenshaw|Kathleen Ollerenshaw]]. Each of the 144 solutions has eight reflections and rotations, giving 1152 solutions in total. The 144&times;8 solutions can be categorized into the following two [[Equivalence class|equivalence class]]es:

{|class="wikitable" align="center" style="font-family:'DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New','Andale Mono','monospace'"
!width="200"|Solution
!width="200"|Normal form
|-
!Solution #1
|align="center"|{{♠|A}} {{♥|K}} {{♦|Q}} {{♣|J}}<br/>{{♣|Q}} {{♦|J}} {{♥|A}} {{♠|K}}<br/>{{♥|J}} {{♠|Q}} {{♣|K}} {{♦|A}}<br/>{{♦|K}} {{♣|A}} {{♠|J}} {{♥|Q}}<br/>
|-
!Solution #2
|align="center"|{{♠|A}} {{♥|K}} {{♦|Q}} {{♣|J}}<br/>{{♦|J}} {{♣|Q}} {{♠|K}} {{♥|A}}<br/>{{♣|K}} {{♦|A}} {{♥|J}} {{♠|Q}}<br/>{{♥|Q}} {{♠|J}} {{♣|A}} {{♦|K}}<br/>
|}

For each of the two solutions, 24&times;24 = 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====
[[File:36_officers_problem.svg|thumb|Generalisation of the 36 officers puzzle for 1 to 8 ranks (chess pieces) and regiments (colours) &ndash; cases 2 and 6 have no solutions]]
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.<ref>{{harvnb|van Lint|Wilson|1993|loc=p.251}}</ref> This problem is known as the ''thirty-six officers problem'',<ref>{{cite journal |  url = https://books.google.com/books?id=cuudxJgEnyEC&q=euler+36-officers&pg=PA54 | journal = Proceedings of the Royal Institution of Great Britain | title = Magic Squares and Other Problems on a Chess Board | author = P. A. MacMahon | year = 1902 | volume = XVII | pages = 50–63}}</ref> and Euler introduced it as follows:<ref>Euler: [https://scholarlycommons.pacific.edu/euler-works/530/ ''Recherches sur une nouvelle espece de quarres magiques''], [http://eulerarchive.maa.org/date-write.html written in 1779], [http://eulerarchive.maa.org/date-publish.html published in 1782]</ref><ref name=CD162 />
{{blockquote|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.|author=Leonhard Euler}}

====Euler's conjecture and disproof====
[[File:Scientific_American_November_1959_Graeco_Latin_square.svg|thumb|link={{filepath:Scientific_American_November_1959_Graeco_Latin_square.svg}}|Redrawing of the November 1959 Scientific American order-10 Graeco-Latin square &ndash; [{{filepath:Scientific_American_November_1959_Graeco_Latin_square.svg}} in the SVG file,] hover over the letters to hide the background and vice versa]]
Euler was unable to solve the problem, but in this work he demonstrated methods for constructing Graeco-Latin squares where {{math|''n''}} 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 [[Singly and doubly even|oddly even]] number {{math|''n'' ≡ 2 ([[Modular arithmetic|mod]] 4).}} The non-existence of order six squares was confirmed in 1901 by [[Biography:Gaston Tarry|Gaston Tarry]] through a [[Proof by exhaustion|proof by exhaustion]].<ref>{{cite journal | first = Gaston | last = Tarry | title = Le Probléme de 36 Officiers | journal = Compte Rendu de l'Association Française pour l'Avancement des Sciences | volume = 1 | pages = 122–123 | year = 1900 | publisher = Secrétariat de l'Association}}</ref><ref>{{cite journal | first = Gaston | last = Tarry | title = Le Probléme de 36 Officiers | journal = Compte Rendu de l'Association Française pour l'Avancement des Sciences | volume = 2 | pages = 170–203 | year = 1901 | publisher = Secrétariat de l'Association}}</ref>  However, Euler's conjecture resisted solution until the late 1950s, but the problem has led to important work in [[Combinatorics|combinatorics]].<ref>{{harvnb|van Lint|Wilson|1993|loc=p.267}}</ref>

In 1959, [[Biography:Raj Chandra Bose|R.C. Bose]] and S. S. Shrikhande constructed some counterexamples (dubbed the ''Euler spoilers'') of order 22 using mathematical insights.<ref>{{citation|first1=R. C.|last1= Bose |first2=S. S. |last2=Shrikhande| title=On the falsity of Euler's conjecture about the non-existence of two orthogonal Latin squares of order 4''t''&nbsp;+&nbsp;2|journal= Proceedings of the National Academy of Sciences USA| volume=45|date=1959|issue= 5 |pages= 734–737|doi= 10.1073/pnas.45.5.734 |pmid= 16590435 |pmc= 222625 |bibcode= 1959PNAS...45..734B |doi-access= free }}</ref>  Then [[Biography:E. T. Parker|E. T. Parker]] found a counterexample of order 10 using a one-hour computer search on a UNIVAC 1206 Military Computer while working at the [[Engineering:UNIVAC|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 {{math|''n'' ≥ 7.}}<ref>{{citation
 | doi = 10.4153/CJM-1960-016-5
 | last1 = Bose | first1 = R. C.
 | last2 = Shrikhande | first2 = S. S.
 | last3 = Parker | first3 = E. T.
 | mr = 0122729
 | journal = Canadian Journal of Mathematics
 | pages = 189–203
 | title = Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler's conjecture
 | volume = 12
 | year = 1960| doi-access = free
 }}</ref> Thus, Graeco-Latin squares exist for all orders {{math|''n''&nbsp;>&nbsp;1}} except {{math|1 = ''n'' = 2, 6.}} In the November 1959 edition of Scientific American, Martin Gardner published this result.<ref name=Gardner /> The front cover is the 10 × 10 refutation of Euler's conjecture.

====Thirty-six entangled officers problem====
[[File:A pair of mutually orthogonal quantum Latin squares of size 6.png|thumb|250px|A quantum solution to a classically impossible problem. If the chess pieces are quantum states in a superposition, then a pair of orthogonal quantum Latin squares of size 6 exists. The relative sizes of chess pieces denote the contribution of the corresponding quantum states.<ref name = "36 entangled officers">{{citation|first1 = Suhail Ahmad |last1 = Rather |first2 = Adam |last2 = Burchardt |first3 = Wojciech |last3 = Bruzda |first4 = Grzegorz |last4 = Rajchel-Mieldzioć |first5 = Arul |last5 = Lakshminarayan |first6 = Karol |last6 = Życzkowski |title = Thirty-six entangled officers of Euler: Quantum solution to a classically impossible problem |journal = Physical Review Letters |volume = 128 |pages = 080507 |year = 2022|issue = 8 |doi = 10.1103/PhysRevLett.128.080507 |pmid = 35275648 |arxiv = 2104.05122 |bibcode = 2022PhRvL.128h0507R |s2cid = 236950798 }}</ref>]]

Extensions of mutually orthogonal Latin squares to the quantum domain have been studied since 2017.<ref>{{citation|first1 = Dardo |last1 = Goyeneche |first2 = Zahra |last2 = Raissi |first3 = Sara |last3 = Di Martino |first4 = Karol |last4 = Życzkowski |title = Entanglement and quantum combinatorial designs |year = 2018 |journal = Physical Review A |volume = 97 |issue = 6 |pages = 062326|doi = 10.1103/PhysRevA.97.062326 |arxiv = 1708.05946 |bibcode = 2018PhRvA..97f2326G |s2cid = 51532085 }}</ref>
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 <ref name = "36 entangled officers"/>
<ref>{{citation|first = Dan |last = Garisto |title = Euler's 243-Year-Old 'Impossible' Puzzle Gets a Quantum Solution |year = 2022 |journal = Quanta Magazine |url = https://www.quantamagazine.org/eulers-243-year-old-impossible-puzzle-gets-a-quantum-solution-20220110/}}</ref>
.<ref>{{citation|first = Stephanie |last = Pappas |title = Centuries-old 'impossible' math problem cracked using the strange physics of Schrödinger's cat |journal = LiveScience |year = 2022 |url = https://www.livescience.com/math-puzzle-quantum-solution}}</ref>
This setup solves a generalization of the 36 Euler's officers problem, as well as provides a new [[Quantum error correction|quantum error detection]] code, allowing to encode a 6-level system into a three 6-level system that certifies occurrence of one error.

==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:<ref name=CD160>{{harvnb|Colbourn|Dinitz|2007|loc=p. 160}}</ref>
:<math>\begin{matrix} 1&2&3&4 \\ 2&1&4&3\\ 3&4&1&2\\4&3&2&1 \end{matrix}\qquad\qquad \begin{matrix} 1&2&3&4 \\ 4&3&2&1 \\2&1&4&3 \\3&4&1&2 \end{matrix}\qquad\qquad\begin{matrix}1&2&3&4 \\3&4&1&2\\4&3&2&1\\2&1&4&3\end{matrix}.</math>
And a set of MOLS(5):<ref>{{harvnb|Colbourn|Dinitz|2007|loc=p. 163}}</ref>
:<math>\begin{matrix}1&2&3&4&5 \\2&3&4&5&1\\3&4&5&1&2\\4&5&1&2&3\\5&1&2&3&4\end{matrix} \qquad\begin{matrix}1&2&3&4&5\\3&4&5&1&2\\5&1&2&3&4\\2&3&4&5&1\\4&5&1&2&3\end{matrix}
\qquad\begin{matrix}1&2&3&4&5\\5&1&2&3&4\\4&5&1&2&3\\3&4&5&1&2\\2&3&4&5&1\end{matrix}
\qquad\begin{matrix}1&2&3&4&5\\4&5&1&2&3\\2&3&4&5&1\\5&1&2&3&4\\3&4&5&1&2\end{matrix}.</math>
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).<ref>{{harvnb|McKay|Meynert|Myrvold|2007|loc=p. 98}}</ref>

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,

{|style="margin: 1em auto 1em auto; font-size:200%; width:300px"
|+style="font-size:50%" | Any two of text, foreground color, background color and typeface form a pair of orthogonal Latin squares:
|-
|style="background:black; color:white; font-family:georgia, times, noto serif, serif; font-weight:bold" align=center | fjords
|style="background:maroon; color:red; font-family:verdana, helvetica, noto sans, sans-serif; font-weight:bold" align=center | jawbox
|style="background:teal; color:lime; font-family:courier new, courier, monospace; font-weight:bold" align=center | phlegm
|style="background:navy; color:blue; font-family:comic sans ms, cursive; font-weight:bold" align=center | qiviut
|style="background:silver; color:yellow; font-family:impact, charcoal, noto sans mono, inconsolata,  fantasy; font-weight:bold" align=center | zincky
|-
|style="background:maroon; color:lime; font-family:comic sans ms, cursive; font-weight:bold" align=center | zincky
|style="background:teal; color:blue; font-family:impact, charcoal, noto sans mono, inconsolata,  fantasy; font-weight:bold" align=center | fjords
|style="background:navy; color:yellow; font-family:georgia, times, noto serif, serif; font-weight:bold" align=center | jawbox
|style="background:silver; color:white; font-family:verdana, helvetica, noto sans, sans-serif; font-weight:bold" align=center | phlegm
|style="background:black; color:red; font-family:courier new, courier, monospace; font-weight:bold" align=center | qiviut
|-
|style="background:teal; color:yellow; font-family:verdana, helvetica, noto sans, sans-serif; font-weight:bold" align=center | qiviut
|style="background:navy; color:white; font-family:courier new, courier, monospace; font-weight:bold" align=center | zincky
|style="background:silver; color:red; font-family:comic sans ms, cursive; font-weight:bold" align=center | fjords
|style="background:black; color:lime; font-family:impact, charcoal, noto sans mono, inconsolata,  fantasy; font-weight:bold" align=center | jawbox
|style="background:maroon; color:blue; font-family:georgia, times, noto serif, serif; font-weight:bold" align=center | phlegm
|-
|style="background:navy; color:red; font-family:impact, charcoal, noto sans mono, inconsolata,  fantasy; font-weight:bold" align=center | phlegm
|style="background:silver; color:lime; font-family:georgia, times, noto serif, serif; font-weight:bold" align=center | qiviut
|style="background:black; color:blue; font-family:verdana, helvetica, noto sans, sans-serif; font-weight:bold" align=center | zincky
|style="background:maroon; color:yellow; font-family:courier new, courier, monospace; font-weight:bold" align=center | fjords
|style="background:teal; color:white; font-family:comic sans ms, cursive; font-weight:bold" align=center | jawbox
|-
|style="background:silver; color:blue; font-family:courier new, courier, monospace; font-weight:bold" align=center | jawbox
|style="background:black; color:yellow; font-family:comic sans ms, cursive; font-weight:bold" align=center | phlegm
|style="background:maroon; color:white; font-family:impact, charcoal, noto sans mono, inconsolata,  fantasy; font-weight:bold" align=center | qiviut
|style="background:teal; color:red; font-family:georgia, times, noto serif, serif; font-weight:bold" align=center | zincky
|style="background:navy; color:lime; font-family:verdana, helvetica, noto sans, sans-serif; font-weight:bold" align=center | fjords
|}

is a representation of the compounded MOLS(5) example above where the four MOLS have the following alphabets, respectively:
* the background color: [[Black|black]], [[Maroon|maroon]], [[Teal|teal]], [[Navy blue|navy]], and [[Silver (color)|silver]]
* the foreground color: [[White|white]], [[Red|red]], [[Lime (color)|lime]], [[Blue|blue]], and [[Yellow|yellow]]
* the text: ''[[Earth:Fjord|fjord]]s'', ''jawbox'', ''[[Biology:Phlegm|phlegm]]'', ''qiviut'', and ''[[Chemistry:Zinc|zinc]]ky''
* the typeface family: serif, sans-serif, monospaced, cursive, and slab-serif. <!-- don't specify actual fonts here -- each system may pick a different front from the font stack specified in the table. -->

The above table therefore allows for testing five values in each of four different dimensions in only 25 observations instead of 625 (= 5<sup>4</sup>) observations required in a [[Factorial experiment|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.<ref>{{harvnb|Dénes|Keedwell|1974|loc=p. 159}}</ref> The MOLS(4) and MOLS(5) examples at the start of this section have been put in standard form.

By putting a set of MOLS({{mvar|n}}) in standard form and examining the entries in the second row and first column of each square, it can be seen that no more than {{nobreak|{{mvar|n}} &minus; 1}} squares can exist.<ref>{{harvnb|Dénes|Keedwell|1974|loc=p. 158}}</ref> A set of {{mvar|n}} &minus; 1 MOLS({{mvar|n}}) is called a ''complete set of MOLS''. Complete sets are known to exist when {{math|''n''}} is a [[Prime number|prime number]] or [[Exponentiation|power]] of a prime (see Finite field construction below). However, the number of MOLS that may exist for a given order {{math|''n''}} is not known for general {{math|''n''}}, and is an area of research in [[Combinatorics|combinatorics]].

====Projective planes====
 
A set of {{math|''n''}} − 1 MOLS({{mvar|n}}) is equivalent to a finite [[Affine plane|affine plane]] of order {{math|''n''}} (see Nets below).<ref name=CD162>{{harvnb|Colbourn|Dinitz|2007|loc=p. 162}}</ref> As every finite affine plane is uniquely extendable to a finite projective plane of the same order, this equivalence can also be expressed in terms of the existence of these projective planes.<ref>The term "order" used here for MOLSs, affine planes and projective planes is defined differently in each setting, but these definitions are coordinated so that the numerical value is the same.</ref>

As mentioned above, complete sets of MOLS({{mvar|n}}) exist if {{mvar|n}} is a prime or prime power, so projective planes of such orders exist. Finite projective planes with an order different from these, and thus complete sets of MOLS of such orders, are not known to exist.<ref name=CD162 />

The only general result on the non-existence of finite projective planes is the Bruck&ndash;Ryser theorem, which says that if a projective plane of order {{mvar|n}} exists and {{nobreak|{{mvar|n}} ≡ 1 (mod 4)}} or {{mvar|n}} ≡ 2 (mod 4), then {{mvar|n}} must be the sum of two (integer) squares.<ref>{{Citation
|last1=Bruck |first1=R.H.
|first2=H.J.|last2=Ryser
|year=1949
|title=The nonexistence of certain finite projective planes
|journal=Canadian Journal of Mathematics
|volume=1
|pages=88&ndash;93
 |doi=10.4153/cjm-1949-009-2|s2cid=123440808
|doi-access=free
}}</ref> This rules out projective planes of orders 6 and 14 for instance, but does not guarantee the existence of a plane when {{mvar|n}} satisfies the condition. In particular, {{mvar|n}} = 10 satisfies the conditions, but no projective plane of order 10 exists, as was shown by a very long computer search,<ref>{{citation
|first=C. W. H.
|title=The Search for a Finite Projective Plane of Order 10
|url=http://www.cecm.sfu.ca/organics/papers/lam/
|journal=[[American Mathematical Monthly]]
|volume=98
|number=4
|year=1991
|pages=305–318
|doi=10.2307/2323798
|jstor=2323798 }}</ref> which in turn implies that there do not exist nine MOLS of order 10.

No other existence results are known. {{as of|2020|post=,}} the smallest order for which the existence of a complete set of MOLS is undetermined is 12.<ref name=CD162 />

====McNeish's theorem====
The minimum number of MOLS({{mvar|n}}) is known to be 2 for all {{math|''n''}} except for {{math|''n''}} = 2 or 6, where it is 1. However, more can be said, namely,<ref>{{harvnb|Dénes|Keedwell|1974|loc=p. 390}}</ref>

''MacNeish's Theorem'': If <math>n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}</math> is the factorization of the integer {{mvar|n}} into powers of distinct primes <math>p_1,p_2,\cdots,p_r</math> then 
::{{nobreak|the minimum number of MOLS({{mvar|n}}) <math>\ge \underset{i}{\operatorname{min}} \{p_i^{\alpha_i} - 1 \}.</math>}}

MacNeish's theorem does not give a very good lower bound, for instance if {{mvar|n}} ≡ 2 (mod 4), that is, there is a single 2 in the prime factorization, the theorem gives a lower bound of 1, which is beaten if {{mvar|n}} > 6. On the other hand, it does give the correct value when {{mvar|n}} is a power of a prime.

For general composite numbers, the number of MOLS is not known. The first few values starting with {{math|''n''}} = 2, 3, 4... are 1, 2, 3, 4, 1, 6, 7, 8, ... {{OEIS|A001438}}.

The smallest case for which the exact number of MOLS({{mvar|n}}) is not known is {{mvar|n}} = 10. From the Graeco-Latin square construction, there must be at least two and from the non-existence of a projective plane of order 10, there are fewer than nine. However, no set of three MOLS(10) has ever been found even though many researchers have attempted to discover such a set.<ref>{{harvnb|McKay|Meynert|Myrvold|2007|loc=p. 102}}</ref>

For large enough {{math|''n''}}, the number of MOLS is greater than <math>\sqrt[14.8]{n}</math>, thus for every {{math|''k''}}, there are only a finite number of {{math|''n''}} such that the number of MOLS is {{math|''k''}}.<ref>{{Cite book|url=https://www.cambridge.org/core/books/design-theory/0DED6E91AC297F825256C649C76D87F8|title=Design Theory by Thomas Beth|last1=Lenz|first1=H.|last2=Jungnickel|first2=D.|date=November 1999|publisher=Cambridge Core|doi=10.1017/cbo9781139507660|access-date=2019-07-06|last3=Beth|first3=Thomas|isbn=9780521772310}}</ref> Moreover, the minimum is 6 for all {{math|''n''}} > 90.

====Finite field construction====
A complete set of MOLS({{mvar|q}}) exists whenever {{mvar|q}} is a prime or prime power. This follows from a construction that is based on a [[Finite field|finite field]] '''GF'''({{mvar|q}}), which only exist if {{mvar|q}} is a prime or prime power.<ref>{{harvnb|Dénes|Keedwell|1974|loc=p. 167}}</ref> The multiplicative group of '''GF'''({{mvar|q}}) is a [[Cyclic group|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 {{mvar|q}} elements of '''GF'''({{mvar|q}}) as follows: 
::α<sub>0</sub> = 0, α<sub>1</sub> = 1, α<sub>2</sub> = λ, α<sub>3</sub> = λ<sup>2</sup>, ..., α<sub>{{mvar|q}}-1</sub> = λ<sup>{{mvar|q}}-2</sup>.

Now, λ<sup>{{mvar|q}}-1</sup> = 1 and the product rule in terms of the α's is α<sub>{{mvar|i}}</sub>α<sub>{{mvar|j}}</sub> = α<sub>{{mvar|t}}</sub>, where {{mvar|t}} = {{mvar|i}} + {{mvar|j}} -1 (mod {{mvar|q}} -1). The Latin squares are constructed as follows, the ({{mvar|i, j}})th entry in Latin square L<sub>{{mvar|r}}</sub> (with {{mvar|r}} ≠ 0) is L<sub>{{mvar|r}}</sub>({{mvar|i,j}}) = α<sub>{{mvar|i}}</sub> + α<sub>{{mvar|r}}</sub>α<sub>{{mvar|j}}</sub>, where all the operations occur in '''GF'''({{mvar|q}}). In the case that the field is a prime field ({{mvar|q}} = {{mvar|p}} a prime), where the field elements are represented in the usual way, as the integers modulo {{mvar|p}}, the naming convention above can be dropped and the construction rule can be simplified to L<sub>{{mvar|r}}</sub>({{mvar|i,j}}) = {{mvar|i}} + {{mvar|rj}}, where {{mvar|r}} ≠ 0 and {{mvar|i}}, {{mvar|j}} and {{mvar|r}} are elements of '''GF'''({{mvar|p}}) and all operations are in '''GF'''({{mvar|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 plane|Desarguesian projective plane]]. There exist non-Desarguesian projective planes and their corresponding complete sets of MOLS can not be obtained from finite fields.<ref>{{harvnb|Dénes|Keedwell|1974|loc=p. 169}}</ref>

===Orthogonal array===
{{main|Orthogonal array}}
An '''orthogonal array''', OA({{mvar|k,n}}), of strength two and index one is an {{math|''n''<sup>2</sup> × ''k''}} array {{mvar|A}} ({{mvar|k}} ≥ 2 and {{mvar|n}} ≥ 1, integers) with entries from a set of size {{mvar|n}} such that within any two columns of {{mvar|A}} (''strength''), every ordered pair of symbols appears in exactly one row of {{mvar|A}} (''index'').<ref name=Stinson>{{harvnb|Stinson|2004|loc=p. 140}}</ref>

An OA({{mvar|s}} + 2, {{mvar|n}}) is equivalent to {{mvar|s}} MOLS({{mvar|n}}).<ref name=Stinson />
For example, the MOLS(4) example given above and repeated here,
:<math>\begin{matrix} 1&2&3&4 \\ 2&1&4&3\\ 3&4&1&2\\4&3&2&1\\& L_1&& \end{matrix}\qquad\qquad \begin{matrix} 1&2&3&4 \\ 4&3&2&1 \\2&1&4&3 \\3&4&1&2 \\& L_2&&\end{matrix}\qquad\qquad\begin{matrix}1&2&3&4 \\3&4&1&2\\4&3&2&1\\2&1&4&3\\& L_3&&\end{matrix}</math>
can be used to form an OA(5,4):
:{| class="wikitable"
|-
! r
! c
! L<sub>1</sub>
! L<sub>2</sub>
! L<sub>3</sub>
|-
| 1
| 1
| 1
| 1
| 1
|-
| 1
| 2
| 2
| 2
| 2
|-
| 1
| 3
| 3
| 3
| 3
|-
| 1
| 4
|4
|4
|4
|-
| 2
| 1
| 2
| 4
| 3
|- 
|2 
|2
|1
|3
|4
|- 
|2
|3
|4
|2
|1
|- 
|2
|4
|3
|1
|2
|- 
|3
|1
|3
|2
|4
|- 
|3
|2
|4
|1
|3
|- 
|3
|3
|1
|4
|2
|- 
|3
|4
|2
|3
|1
|- 
|4
|1
|4
|3
|2
|- 
|4
|2
|3
|4
|1
|- 
|4
|3
|2
|1
|4
|- 
|4
|4
|1
|2
|3
|}
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. This process is reversible; given an OA({{mvar|s}},{{mvar|n}}) with {{mvar|s}} ≥ 3, choose any two columns to play the ''r'' and ''c'' roles and then fill out the Latin squares with the entries in the remaining columns.

More general orthogonal arrays represent generalizations of the concept of MOLS, such as mutually orthogonal Latin cubes.

===Nets===
A (geometric) ({{mvar|k,n}})-net is a set of {{mvar|n}}<sup>2</sup> elements called ''points'' and a set of {{mvar|kn}} subsets called ''lines'' or ''blocks'' each of size {{mvar|n}} with the property that two distinct lines intersect in at most one point. Moreover, the lines can be partitioned into {{mvar|k}} parallel classes (no two of its lines meet) each containing {{mvar|n}} lines.<ref>{{harvnb|Colbourn|Dinitz|2007|loc=p. 161}}</ref>

An ({{mvar|n}} + 1, {{mvar|n}})-net is an affine plane of order {{mvar|n}}.

A set of {{mvar|k}} MOLS({{mvar|n}}) is equivalent to a ({{mvar|k}} + 2, {{mvar|n}})-net.<ref name=CD162 />

To construct a ({{mvar|k}} + 2, {{mvar|n}})-net from {{mvar|k}} MOLS({{mvar|n}}), represent the MOLS as an orthogonal array, OA({{mvar|k}} + 2, {{mvar|n}}) (see above). The ordered pairs of entries in each row of the orthogonal array in the columns labeled {{mvar|r}} and {{mvar|c}}, will be considered to be the coordinates of the {{mvar|n}}<sup>2</sup> points of the net. Each other column (that is, Latin square) will be used to define the lines in a parallel class. The {{mvar|n}} lines determined by the column labeled L<sub>''i''</sub> will be denoted by ''l''<sub>''ij''</sub>. The points on ''l''<sub>''ij''</sub> will be those with coordinates corresponding to the rows where the entry in the L<sub>''i''</sub> column is {{mvar|j}}. There are two additional parallel classes, corresponding to the {{mvar|r}} and {{mvar|c}} columns. The lines {{mvar|r}}<sub>''j''</sub> and {{mvar|c}}<sub>''j''</sub> consist of the points whose first coordinates are {{mvar|j}}, or second coordinates are {{mvar|j}} respectively. This construction is reversible.<ref>{{harvnb|Dénes|Keedwell|1974|loc=p. 270}}</ref>

For example, the OA(5,4) in the above section can be used to construct a (5,4)-net (an affine plane of order 4). The points on each line are given by (each row below is a parallel class of lines):
:{| class="wikitable"
|-
|{{mvar|l}}<sub>11</sub>:
|(1,1) (2,2) (3,3) (4,4)
|{{mvar|l}}<sub>12</sub>:
|(1,2) (2,1) (3,4) (4,3)
|{{mvar|l}}<sub>13</sub>:
|(1,3) (2,4) (3,1) (4,2)
|{{mvar|l}}<sub>14</sub>:
|(1,4) (2,3) (3,2) (4,1)
|-
|{{mvar|l}}<sub>21</sub>:
|(1,1) (2,4) (3,2) (4,3)
|{{mvar|l}}<sub>22</sub>:
|(1,2) (2,3) (3,1) (4,4)
|{{mvar|l}}<sub>23</sub>:
|(1,3) (2,2) (3,4) (4,1)
|{{mvar|l}}<sub>24</sub>:
|(1,4) (2,1) (3,3) (4,2)
|-
|{{mvar|l}}<sub>31</sub>:
|(1,1) (2,3) (3,4) (4,2)
|{{mvar|l}}<sub>32</sub>:
|(1,2) (2,4) (3,3) (4,1)
|{{mvar|l}}<sub>33</sub>:
|(1,3) (2,1) (3,2) (4,4)
|{{mvar|l}}<sub>34</sub>:
|(1,4) (2,2) (3,1) (4,3)
|-
|{{mvar|r}}<sub>1</sub>:
|(1,1) (1,2) (1,3) (1,4)
|{{mvar|r}}<sub>2</sub>:
|(2,1) (2,2) (2,3) (2,4)
|{{mvar|r}}<sub>3</sub>:
|(3,1) (3,2) (3,3) (3,4)
|{{mvar|r}}<sub>4</sub>:
|(4,1) (4,2) (4,3) (4,4)
|-
| {{mvar|c}}<sub>1</sub>:
|(1,1) (2,1) (3,1) (4,1)
| {{mvar|c}}<sub>2</sub>:
|(1,2) (2,2) (3,2) (4,2)
| {{mvar|c}}<sub>3</sub>:
|(1,3) (2,3) (3,3) (4,3)
| {{mvar|c}}<sub>4</sub>:
|(1,4) (2,4) (3,4) (4,4)
|}

===Transversal designs===
A ''transversal design'' with {{mvar|k}} groups of size {{mvar|n}} and index λ, denoted T[{{mvar|k}}, λ; {{mvar|n}}], is a triple ({{mvar|X, G, B}}) where:<ref>{{harvnb|Street|Street|1987|loc=p. 133}}</ref>
* {{mvar|X}} is a set of {{mvar|kn}} varieties;
* {{math|1=''G'' = {''G''<sub>1</sub>, ''G''<sub>2</sub>, ..., ''G''<sub>''k''</sub>}}} is a family of {{mvar|k n}}-sets (called ''groups'', but not in the algebraic sense) which form a partition of {{mvar|X}};
* {{mvar|B}} is a family of {{mvar|k}}-sets (called ''blocks'') of varieties such that each {{mvar|k}}-set in {{mvar|B}} intersects each group {{mvar|G<sub>i</sub>}} in precisely one variety, and any pair of varieties which belong to different groups occur together in precisely λ blocks in {{mvar|B}}.

The existence of a T[{{mvar|k}},1;{{mvar|n}}] design is equivalent to the existence of {{mvar|k}}-2 MOLS({{mvar|n}}).<ref>{{harvnb|Street|Street|1987|loc=p. 135}}</ref>

A transversal design T[{{mvar|k}},1;{{mvar|n}}] is the [[Duality (projective geometry)|dual]] [[Incidence structure|incidence structure]] of an ({{mvar|k,n}})-net. That is, it has {{mvar|nk}} points and {{mvar|n}}<sup>2</sup> blocks. Each point is in {{mvar|n}} blocks; each block contains {{mvar|k}} points. The points fall into {{mvar|k}} equivalence classes (groups) of size {{mvar|n}} so that two points in the same group are not contained in a block while two points in different groups belong to exactly one block.<ref>{{harvnb|van Lint|Wilson|1993|loc=p.257}}</ref>

For example, using the (5,4)-net of the previous section we can construct a T[5,1;4] transversal design. The block associated with the point ({{mvar|i, j}}) of the net will be denoted {{mvar|b}}<sub>''ij''</sub>. The points of the design will be obtained from the following scheme: {{mvar|r}}<sub>''i''</sub> ↔ {{mvar|i}}, {{mvar|c}}<sub>''j''</sub> ↔ 5{{mvar|j}}, and {{mvar|l}}<sub>''ij''</sub> ↔ 5{{mvar|i}} + {{mvar|j}}. The points of the design are thus denoted by the integers 1, ..., 20. The blocks of the design are:
:{| class="wikitable"
|-
|{{mvar|b}}<sub>11</sub>:
|6 11 16 1 5
|{{mvar|b}}<sub>22</sub>:
|6 13 19 2 10
|{{mvar|b}}<sub>33</sub>:
|6 14 17 3 15
|{{mvar|b}}<sub>44</sub>:
|6 12 18 4 20
|-
|{{mvar|b}}<sub>12</sub>:
|7 12 17 1 10
|{{mvar|b}}<sub>21</sub>:
|7 14 18 2 5
|{{mvar|b}}<sub>34</sub>:
|7 13 16 3 20
|{{mvar|b}}<sub>43</sub>:
|7 11 19 4 15
|-
|{{mvar|b}}<sub>13</sub>:
|8 13 18 1 15
|{{mvar|b}}<sub>24</sub>:
|8 11 17 2 20
|{{mvar|b}}<sub>31</sub>:
|8 12 19 3 5
|{{mvar|b}}<sub>42</sub>:
|8 14 16 4 10
|-
|{{mvar|b}}<sub>14</sub>:
|9 14 19 1 20
|{{mvar|b}}<sub>23</sub>:
|9 12 16 2 15
|{{mvar|b}}<sub>32</sub>:
|9 11 18 3 10
|{{mvar|b}}<sub>41</sub>:
|9 13 17 4 5
|}
The five "groups" are:
:{| class="wikitable"
|-
|6 7 8 9
|-
|11 12 13 14
|-
|16 17 18 19
|-
|1 2 3 4
|-
|5 10 15 20
|}

===Graph theory===
A set of {{mvar|k}} MOLS({{mvar|n}}) is equivalent to an edge-partition of the complete ({{mvar|k}} + 2)-partite graph K<sub>''n'',...,''n''</sub> into [[Complete graph|complete subgraphs]] of order {{mvar|k}} + 2.<ref name=CD162 />

==Applications==
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|design of experiments]], tournament scheduling, and [[Error detection and correction|error correcting and detecting codes]]. Euler's interest in Graeco-Latin squares arose from his desire to construct [[Magic square#Euler's method|magic squares]]. The French writer Georges Perec structured his 1978 novel Life: A User's Manual around a 10&times;10 Graeco-Latin square.

==See also==
{{div col}}
*36 cube
*[[Block design]]
*[[Blocking (statistics)]]
*[[Combinatorial design]]
{{div col end}}

==Notes==
{{Reflist}}

== References ==
* {{citation|last1=Colbourn|first1=Charles J.|last2=Dinitz|first2=Jeffrey H.|title=Handbook of Combinatorial Designs|year=2007|publisher=Chapman & Hall/ CRC|location=Boca Raton|isbn=978-1-58488-506-1|edition=2nd|url-access=registration|url=https://archive.org/details/handbookofcombin0000unse}}
* {{citation|last1=Dénes|first1=J.|last2=Keedwell|first2=A. D.|title=Latin squares and their applications|publisher=Academic Press  |location=New York-London|year=1974|pages=547|mr=351850|isbn=0-12-209350-X}}
* {{citation
 | year = 1966
 | title = Martin Gardner's New Mathematical Diversions from Scientific American
  | publisher=Fireside
 |isbn=0-671-20913-2
 }}
* {{citation|url=http://cs.anu.edu.au/~bdm/papers/ls_final.pdf |last1=McKay|first1=Brendan D.|last2=Meynert|first2=Alison|last3=Myrvold|first3=Wendy|title=Small Latin Squares, Quasigroups and Loops|journal=Journal of Combinatorial Designs|year=2007|volume=15|issue=2|pages=98–119|doi=10.1002/jcd.20105|s2cid=82321 }}|doi-broken-date=2020-10-03| zbl=1112.05018 | citeseerx=10.1.1.151.3043}}
* {{citation 
| title = Constructions and Combinatorial Problems in Design of Experiments 
| author = Raghavarao, Damaraju 
| location = New York 
| year = 1988 
| edition = corrected reprint of the 1971 Wiley 
| publisher = Dover }}
* {{cite book 
| title = Block Designs: Analysis, Combinatorics and Applications 
| author = Raghavarao, Damaraju 
| author2 = Padgett, L.V. 
| name-list-style = amp
| location = 
| year = 2005 
| edition = 
| publisher = World Scientific }}
* {{citation|first=Douglas R.|last=Stinson|title=Combinatorial Designs / Constructions and Analysis|year=2004|publisher=Springer|isbn=978-0-387-95487-5}}
* {{citation |last1=Street |first1=Anne Penfold |author1-link= Anne Penfold Street 
| title = Combinatorics of Experimental Design |title-link= Combinatorics of Experimental Design
| publisher = Oxford U. P. [Clarendon] | year = 1987 
| isbn = 0-19-853256-3 }}
* {{citation|first1=J.H.|last1=van Lint|first2=R.M.|last2=Wilson|title=A Course in Combinatorics|year=1993|publisher=Cambridge University Press|isbn=978-0-521-42260-4}}

==External links==
*[https://www.ams.org/publicoutreach/feature-column/fcarc-latinii1 Leonhard Euler's Puzzle of the 36 Officiers] AMS featured column archive (Latin Squares in Practice and Theory II)
*{{MathWorld |title=36 Officer Problem |id=36OfficerProblem}}
*[https://web.archive.org/web/20070713214718/http://mathdl.maa.org/convergence/1/?pa=content&sa=viewDocument&nodeId=1434&bodyId=1597 Euler's work on Latin Squares and Euler Squares] at Convergence
* [http://www.cut-the-knot.org/Curriculum/Algebra/OrthoLatin.shtml Java Tool which assists in constructing Graeco-Latin squares (it does not construct them by itself)] at cut-the-knot
* [http://plus.maths.org/issue38/features/aiden/ ''Anything but square: from magic squares to Sudoku'']
* Historical facts and correlation with Magic Squares, [https://omerkel.github.io/eulersquare/src/ Javascript Application to solve Graeco-Latin Squares from size 1x1 to 10x10] and related [https://github.com/OMerkel/eulersquare source code] (Javascript in Firefox browser and HTML5 mobile devices)
{{Experimental design|state=expanded}}
{{Statistics|state=collapsed}}

[[Category:Latin squares]]

{{Sourceattribution|Mutually orthogonal Latin squares}}