{{short description|Square array with symbols that each occur once per row and column}} {{CS1 config|mode=cs1}} [[File:Fisher-stainedglass-gonville-caius.jpg|thumb|upright|Displaying a 7 × 7 Latin square, this stained-glass window at Gonville and Caius College, Cambridge, honored Ronald Fisher, whose ''Design of Experiments'' discussed Latin squares. The Sir Ronald Fisher window was removed in 2020 because of Fisher's connection with eugenics.<ref>{{cite web|last=Busby|first=Mattha|date=27 June 2020|title=Cambridge college to remove window commemorating eugenicist|url=http://www.theguardian.com/education/2020/jun/27/cambridge-gonville-caius-college-eugenicist-window-ronald-fisher|access-date=2020-06-28|website=The Guardian}}</ref>]] In combinatorics and in experimental design<!-- alternatively, in mathematics and in statistics -->, a '''Latin square''' is an ''n'' × ''n'' array filled with ''n'' different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3 × 3 Latin square is {| class="wikitable" style="margin-left:auto;margin-right:auto;text-align:center;width:6em;height:7em;table-layout:fixed;" |- | A || B || C |- | C || A || B |- | B || C || A |} The name "Latin square" was inspired by mathematical papers by Leonhard Euler (1707–1783), who used Latin characters as symbols,<ref>{{cite book|title=Introduction to Combinatorics|first1=W. D.|last1=Wallis|first2=J. C.|last2=George|publisher=CRC Press|year=2011|isbn=978-1-4398-0623-4|page=212|url=https://books.google.com/books?id=PTbb7x-mI5gC&pg=PA212}}</ref><ref>(Euler, 1782), pp. 90-91. From p. 90: ''"Pour cet effect nous reprenons le quarré latin fondamentel, qui, en omettant les exponsans, aura la forme suivante: ..."'' (For this purpose, we take the fundamental Latin square, which, by omitting the exponents, will have the following form: ...) From p. 91: ''"§.8 Ayant donc établi ce quarré'' latin, ...''"'' (§.8 Having thus established this ''Latin'' square, ...")</ref> but any set of symbols can be used: in the above example, the alphabetic sequence A, B, C can be replaced by the integer sequence 1, 2, 3. Euler began the general theory of Latin squares.<ref>{{cite journal |last1=Euler |first1=Leonhard |title=Recherches sur une nouvelle espèce de quarrés magiques |journal=Verhandelingen Uitgegeven Door Het Zeeuwsch Genootschap der Wetenschappen te Vlissingen (Proceedings Published by the Zeeland Society of Sciences in Flushing [, Netherlands]) |date=1782 |volume=9 |pages=85–239 |url=https://books.google.com/books?id=VA4VAAAAQAAJ&pg=RA1-PA85 |trans-title=Investigations into a new type of magic squares |language=French}} (Note: Euler first presented this memoir to the Imperial Academy of Sciences of St. Petersburg, Russia on 8 March 1779.)</ref>
== History ==
The Korean mathematician Choi Seok-jeong was the first to publish an example of Latin squares of order nine, in order to construct a magic square in 1700, predating Leonhard Euler by 67 years.<ref>{{cite book|last1=Colbourn|first1=Charles J.|last2=Dinitz|first2=Jeffrey H.|title=Handbook of Combinatorial Designs|year=2007|edition=2nd |publisher=CRC Press|isbn=9781420010541|page=12|url=https://books.google.com/books?id=Q9jLBQAAQBAJ&pg=PA12|access-date=28 March 2017|language=en}}</ref>
===Counting=== This account follows {{harvtxt|McKay|Meynert|Myrvold|2007|p=100}}.<ref>{{cite journal | last1 = McKay | first1 = Brendan D. | author1-link = Brendan McKay (mathematician) | last2 = Meynert | first2 = Alison | last3 = Myrvold | first3 = Wendy | author3-link = Wendy Myrvold | doi = 10.1002/jcd.20105 | issue = 2 | journal = Journal of Combinatorial Designs | mr = 2291523 | pages = 98–119 | title = Small Latin squares, quasigroups, and loops | volume = 15 | year = 2007}}</ref>
The counting of Latin squares has a long history, but the published accounts contain many errors. Euler in 1782,<ref>{{cite journal|first=L.|last=Euler|year=1782|title=Recherches sur une nouvelle espèce de quarrés magiques|journal=Verhandelingen/Uitgegeven Door Het Zeeuwsch Genootschap der Wetenschappen te Vlissingen|issue=9|pages=85–239}}</ref> and Cayley in 1890,<ref>{{cite journal|first=A.|last=Cayley|year=1890|title=On Latin Squares|journal=Oxford Camb. Dublin Messenger of Math.|volume=19|pages=85–239}}</ref> both knew the number of reduced Latin squares up to order five. In 1915, MacMahon<ref>{{cite book|first=P.A.|last=MacMahon|title=Combinatory Analysis|year=1915|publisher=Cambridge University Press|page=300}}</ref> approached the problem in a different way, but initially obtained the wrong value for order five. M.Frolov in 1890,<ref>{{cite journal|first=M.|last=Frolov|title=Sur les permutations carrées|journal=J. De Math. Spéc.|year=1890|volume=IV|pages=8–11, 25–30}}</ref> and Tarry in 1901,<ref>{{cite journal | first = Gaston | last = Tarry | title = Le problème des 36 officiers | journal = Comptes rendus de l'Association française pour l'avancement des sciences | volume = 29 | number = 1 | pages = 122–123 | year = 1900 | url = https://hdl.handle.net/2027/njp.32101076521697?urlappend=%3Bseq=242%3Bownerid=27021597768906376-252}}</ref><ref>{{cite journal | first = Gaston | last = Tarry | title = Le problème des 36 officiers | journal = Comptes rendus de l'Association française pour l'avancement des sciences | volume = 29 | number = 2 | pages = 170–203 | year = 1901 | url = https://hdl.handle.net/2027/hvd.32044106224272?urlappend=%3Bseq=182%3Bownerid=27021597765797130-188}}</ref> found the number of reduced squares of order six. M. Frolov gave an incorrect count of reduced squares of order seven. R.A. Fisher and F. Yates,<ref>{{cite journal|first1=R.A.|last1=Fisher|first2=F.|last2=Yates|title=The 6 × 6 Latin squares|year=1934|journal=Proc. Cambridge Philos. Soc.|volume=30|issue=4|pages=492–507|doi=10.1017/S0305004100012731|bibcode=1934PCPS...30..492F|s2cid=120585553 }}</ref> unaware of earlier work of E. Schönhardt,<ref>{{cite journal|first=E.|last=Schönhardt|title=Über lateinische Quadrate und Unionen|journal=J. Reine Angew. Math.|year=1930|volume=1930|issue=163 |pages=183–230|doi=10.1515/crll.1930.163.183 |s2cid=115237080 }}</ref> gave the number of isotopy classes of orders up to six. In 1939, H. W. Norton found 562 isotopy classes of order seven,<ref>{{cite journal|first=H.W.|last=Norton|year=1939|title=The 7 × 7 squares|journal=Annals of Eugenics|volume = 9|issue=3|pages=269–307|doi=10.1111/j.1469-1809.1939.tb02214.x|doi-access=free}}</ref> but acknowledged that his method was incomplete. A. Sade, in 1951,<ref>{{cite journal|first=A.|last=Sade|year=1951|title=An omission in Norton's list of 7 × 7 squares|journal=Ann. Math. Stat.|volume=22|issue=2|pages=306–307|doi=10.1214/aoms/1177729654|doi-access=free}}</ref> but privately published earlier in 1948, and P. N. Saxena<ref>{{cite journal|first=P.N.|last=Saxena|year=1951|title=A simplified method of enumerating Latin squares by MacMahon's differential operators; II. The 7 × 7 Latin squares|journal=J. Indian Soc. Agric. Statistics|volume=3|pages=24–79}}</ref> found more classes and, in 1966, D. A. Preece noted that this corrected Norton's result to 564 isotopy classes.<ref>{{cite journal|first=D.A.|last=Preece|year=1966|title=Classifying Youden rectangles|journal=J. Roy. Statist. Soc. Ser. B|volume=28|pages=118–130|doi=10.1111/j.2517-6161.1966.tb00625.x }}</ref> However, in 1968, J. W. Brown announced an incorrect value of 563,<ref>{{cite journal|first=J.W.|last=Brown|year=1968|title=Enumeration of Latin squares with application to order 8|journal=Journal of Combinatorial Theory|volume=5|issue=2|pages=177–184|doi=10.1016/S0021-9800(68)80053-5|doi-access=free}}</ref> which has often been repeated. He also gave the wrong number of isotopy classes of order eight. The correct number of reduced squares of order eight had already been found by M. B. Wells in 1967,<ref>{{cite journal|first=M.B.|last=Wells|year=1967|title=The number of Latin squares of order eight|journal=Journal of Combinatorial Theory|volume=3|pages=98–99|doi=10.1016/S0021-9800(67)80021-8|doi-access=free}}</ref> and the numbers of isotopy classes, in 1990, by G. Kolesova, C.W.H. Lam and L. Thiel.<ref>{{cite journal|first1=G.|last1=Kolesova|first2=C.W.H.|last2=Lam|first3=L.|last3=Thiel|title=On the number of 8 × 8 Latin squares|year=1990|journal=Journal of Combinatorial Theory, Series A|volume=54|pages=143–148|doi=10.1016/0097-3165(90)90015-O|doi-access=free}}</ref> The number of reduced squares for order nine was obtained by S. E. Bammel and J. Rothstein,<ref>{{cite journal|first1=S.E.|last1=Bammel|first2=J.|last2=Rothstein|title=The number of 9 × 9 Latin squares|year=1975|journal=Discrete Mathematics|volume=11|pages=93–95|doi=10.1016/0012-365X(75)90108-9|doi-access=free}}</ref> for order 10 by B. D. McKay and E. Rogoyski,<ref>{{cite journal|first1=B.D.|last1=McKay|first2=E.|last2=Rogoyski|year=1995|title=Latin squares of order ten|journal=Electronic Journal of Combinatorics |volume=2|pages=4|article-number=N3 |doi=10.37236/1222|doi-access=free}}</ref> and for order 11 by B. D. McKay and I. M. Wanless.<ref>{{cite journal|first1=B.D.|last1=McKay|first2=I.M.|last2=Wanless|year=2005|title=On the number of Latin squares|journal=Ann. Comb.|volume=9|issue=3|pages=335–344|doi=10.1007/s00026-005-0261-7|s2cid=7289396}}</ref>
== Reduced form ==
A Latin square is said to be ''reduced'' (also, ''normalized'' or ''in standard form'') if both its first row and its first column are in their natural order.<ref>{{harvnb|Dénes|Keedwell|1974|loc=p. 128}}</ref> For example, the Latin square above is not reduced because its first column is A, C, B rather than A, B, C.
Any Latin square can be reduced by permuting (that is, reordering) the rows and columns. Here switching the above matrix's second and third rows yields the following square:
{| class="wikitable" style="margin-left:auto;margin-right:auto;text-align:center;width:6em;height:7em;table-layout:fixed;" |- | A || B || C |- | B || C || A |- | C || A || B |}
This Latin square is reduced; both its first row and its first column are alphabetically ordered A, B, C.
==Properties==
===Orthogonal array representation===
If each entry of an ''n'' × ''n'' Latin square is written as a triple (''r'',''c'',''s''), where ''r'' is the row, ''c'' is the column, and ''s'' is the symbol, we obtain a set of ''n''<sup>2</sup> triples called the orthogonal array representation of the square. For example, the orthogonal array representation of the Latin square
{| class="wikitable" style="margin-left:auto;margin-right:auto;text-align:center;width:6em;height:7em;table-layout:fixed;" |- | 1 || 2 || 3 |- | 2 || 3 || 1 |- | 3 || 1 || 2 |}
is
: { (1, 1, 1), (1, 2, 2), (1, 3, 3), (2, 1, 2), (2, 2, 3), (2, 3, 1), (3, 1, 3), (3, 2, 1), (3, 3, 2) }, where for example the triple (2, 3, 1) means that in row 2 and column 3 there is the symbol 1. Orthogonal arrays are usually written in array form where the triples are the rows, such as {|class="wikitable" style="margin-left:auto;margin-right:auto;text-align:center;width:6em;height:6em;table-layout:fixed;" !''r'' !''c'' !''s'' |- |1 |1 |1 |- |1 |2 |2 |- |1 |3 |3 |- |2 |1 |2 |- |2 |2 |3 |- |2 |3 |1 |- |3 |1 |3 |- |3 |2 |1 |- |3 |3 |2 |}
The definition of a Latin square can be written in terms of orthogonal arrays: * A Latin square is a set of ''n''<sup>2</sup> triples (''r'', ''c'', ''s''), where 1 ≤ ''r'', ''c'', ''s'' ≤ ''n'', such that all ordered pairs (''r'', ''c'') are distinct, all ordered pairs (''r'', ''s'') are distinct, and all ordered pairs (''c'', ''s'') are distinct.
This means that the ''n''<sup>2</sup> ordered pairs (''r'', ''c'') are all the pairs (''i'', ''j'') with 1 ≤ ''i'', ''j'' ≤ ''n'', once each. The same is true of the ordered pairs (''r'', ''s'') and the ordered pairs (''c'', ''s'').
The orthogonal array representation shows that rows, columns and symbols play rather similar roles, as will be made clear below.
===Equivalence classes of Latin squares=== {{see also|Small Latin squares and quasigroups}} Many operations on a Latin square produce another Latin square (for example, turning it upside down).
If we permute the rows, permute the columns, or permute the names of the symbols of a Latin square, we obtain a new Latin square said to be ''isotopic'' to the first. Isotopism is an equivalence relation, so the set of all Latin squares is divided into subsets, called ''isotopy classes'', such that two squares in the same class are isotopic and two squares in different classes are not isotopic.
A stronger form of equivalence exists. Two Latin squares {{math|''L''<sub>1</sub>}} and {{math|''L''<sub>2</sub>}} of side {{mvar|n}} with common symbol set {{mvar|S}} that is also the index set for the rows and columns of each square are ''isomorphic'' if there is a bijection {{math|''g'': ''S'' → ''S''}} such that {{math|1=''g''(''L''<sub>1</sub>(''i'', ''j'')) = ''L''<sub>2</sub>(''g''(''i''), ''g''(''j''))}} for all {{mvar|i}}, {{mvar|j}} in {{mvar|S}}.<ref name=CD>{{harvnb|Colbourn|Dinitz|2007|p=136}}</ref> An alternate way to define isomorphic Latin squares is to say that a pair of isotopic Latin squares are isomorphic if the three bijections used to show that they are isotopic are, in fact, equal.<ref name="Denes 1974 loc=p. 24">{{harvnb|Dénes|Keedwell|1974|p=24}}</ref> Isomorphism is also an equivalence relation and its equivalence classes are called ''isomorphism classes''.
Another type of operation is easiest to explain using the orthogonal array representation of the Latin square. If we systematically and consistently reorder the three items in each triple (that is, permute the three columns in the array form), another orthogonal array (and, thus, another Latin square) is obtained. For example, we can replace each triple (''r'',''c'',''s'') by (''c'',''r'',''s'') which corresponds to transposing the square (reflecting about its main diagonal), or we could replace each triple (''r'',''c'',''s'') by (''c'',''s'',''r''), which is a more complicated operation. Altogether there are 6 possibilities including "do nothing", giving us 6 Latin squares called the conjugates (also parastrophes) of the original square.<ref name=DK126>{{harvnb|Dénes|Keedwell|1974|loc=p. 126}}</ref>
Finally, we can combine these two equivalence operations: two Latin squares are said to be ''paratopic'', also ''main class isotopic'', if one of them is isotopic to a conjugate of the other. This is again an equivalence relation, with the equivalence classes called ''main classes'', ''species'', or ''paratopy classes''.<ref name=DK126 /> Each main class contains up to six isotopy classes.
=== Number of {{math|''n'' × ''n''}} Latin squares ===
There is no known easily computable formula for the number {{math|''L<sub>n</sub>''}} of {{math|''n'' × ''n''}} Latin squares with symbols {{math|1, 2, ..., ''n''}}. The most accurate upper and lower bounds known for large {{mvar|n}} are far apart. One classic result<ref>{{harvnb|van Lint|Wilson|1992|loc=pp. 161-162}}</ref> is that <math display="block"> \prod_{k=1}^n \left(k!\right)^{n/k}\geq L_n\geq\frac{\left(n!\right)^{2n}}{n^{n^2}}.</math>
A simple and explicit formula for the number of Latin squares was published in 1992, but it is still not easily computable due to the exponential increase in the number of terms. This formula for the number {{math|''L<sub>n</sub>''}} of {{math|''n'' × ''n''}} Latin squares is <math display="block"> L_n = n! \sum_{A \in B_n}^{} (-1)^{\sigma_0 (A)} \binom{\operatorname{per} A}{n},</math> where {{math|''B''<sub>''n''</sub>}} is the set of all {{math|''n'' × ''n''}} {0, 1}-matrices, {{math|σ<sub>0</sub>(''A'')}} is the number of zero entries in matrix {{mvar|A}}, and {{math|per(''A'')}} is the permanent of matrix {{mvar|A}}.<ref>{{Cite journal|title = A formula for the number of Latin squares|journal = Discrete Mathematics|author1 = Jia-yu Shao|author2 = Wan-di Wei |volume = 110| year = 1992 |issue = 1–3| pages = 293–296|doi=10.1016/0012-365x(92)90722-r|doi-access = free}}</ref>
The table below contains all known exact values. It can be seen that the numbers grow exceedingly quickly. For each {{mvar|n}}, the number of Latin squares altogether {{OEIS|id=A002860}} is {{math|''n''! (''n'' − 1)!}} times the number of reduced Latin squares {{OEIS|id=A000315}}.
{| class="wikitable" align="center" style="text-align: right;" |+ The numbers of Latin squares of various sizes ! {{mvar|n}} ||align=right| reduced Latin squares of size {{mvar|n}}<br />{{OEIS|id=A000315}} ! align="right" | all Latin squares of size {{mvar|n}}<br />{{OEIS|id=A002860}} |- |align=right| 1 ||align=right| 1 ||align=right| 1 |- |align=right| 2 ||align=right| 1 ||align=right| 2 |- |align=right| 3 ||align=right| 1 ||align=right| 12 |- |align=right| 4 ||align=right| 4 ||align=right| 576 |- |align=right| 5 ||align=right| 56 ||align=right| 161,280 |- |align=right| 6 ||align=right| 9,408 ||align=right| 812,851,200 |- |align=right| 7 ||align=right| 16,942,080 ||align=right| 61,479,419,904,000 |- |align=right| 8 ||align=right| 535,281,401,856 ||align=right| 108,776,032,459,082,956,800 |- |align=right| 9 ||align=right| 377,597,570,964,258,816 ||align=right| 5,524,751,496,156,892,842,531,225,600 |- | 10 ||align=right| 7,580,721,483,160,132,811,489,280 ||align=right| 9,982,437,658,213,039,871,725,064,756,920,320,000 |- | 11 ||align=right| 5,363,937,773,277,371,298,119,673,540,771,840 ||align=right| 776,966,836,171,770,144,107,444,346,734,230,682,311,065,600,000 |- |12 |1.62 × 10<sup>44</sup> | |- |13 |2.51 × 10<sup>56</sup> | |- |14 |2.33 × 10<sup>70</sup> | |- |15 |1.50 × 10<sup>86</sup> | |}
For each {{mvar|n}}, each isotopy class {{OEIS|id=A040082}} contains up to {{math|(''n''!)<sup>3</sup>}} Latin squares (the exact number varies), while each main class {{OEIS|id=A003090}} contains either 1, 2, 3 or 6 isotopy classes.
{| class="wikitable" align="center" style="text-align: right;" |+ Equivalence classes of Latin squares ! {{mvar|n}} ||align=right| main classes {{OEIS|id=A003090}} ! align="right" | isotopy classes {{OEIS|id=A040082}} !structurally distinct squares {{OEIS|id=A264603}} |- |align=right| 1 ||align=right| 1 ||align=right| 1 |1 |- |align=right| 2 ||align=right| 1 ||align=right| 1 |1 |- |align=right| 3 ||align=right| 1 ||align=right| 1 |1 |- |align=right| 4 ||align=right| 2 ||align=right| 2 |12 |- |align=right| 5 ||align=right| 2 ||align=right| 2 |192 |- |align=right| 6 ||align=right| 12 ||align=right| 22 |145,164 |- |align=right| 7 ||align=right| 147 ||align=right| 564<!-- Note 564, not 563, see Talk page!--> |1,524,901,344 |- |align=right| 8 ||align=right| 283,657 ||align=right| 1,676,267 | |- |align=right| 9 ||align=right| 19,270,853,541 ||align=right| 115,618,721,533 | |- | 10 ||align=right| 34,817,397,894,749,939 ||align=right| 208,904,371,354,363,006 | |- | 11 ||align=right| 2,036,029,552,582,883,134,196,099 ||align=right| 12,216,177,315,369,229,261,482,540 | |}
The number of structurally distinct Latin squares (i.e. the squares cannot be made identical by means of rotation, reflection, and permutation of the symbols) for {{mvar|n}} = 1 up to 7 is 1, 1, 1, 12, 192, 145164, 1524901344 respectively {{OEIS| id=A264603}}.
===Examples=== {{main|Small Latin squares and quasigroups}} We give one example of a Latin square from each main class up to order five.
<div class="center"><math> \begin{bmatrix} 1 \end{bmatrix} \quad \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix} \quad \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{bmatrix} </math></div>
<div class="center"><math> \begin{bmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \end{bmatrix} \quad \begin{bmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \\ 3 & 1 & 4 & 2 \\ 4 & 3 & 2 & 1 \end{bmatrix} </math></div>
<div class="center"><math> \begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 5 & 1 & 4 \\ 3 & 5 & 4 & 2 & 1 \\ 4 & 1 & 2 & 5 & 3 \\ 5 & 4 & 1 & 3 & 2 \end{bmatrix} \quad \begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \\ 3 & 5 & 4 & 2 & 1 \\ 4 & 1 & 5 & 3 & 2 \\ 5 & 3 & 2 & 1 & 4 \end{bmatrix} </math></div>
They present, respectively, the multiplication tables of the following groups: *{0} – the trivial 1-element group *<math>\mathbb{Z}_2</math> – the binary group *<math>\mathbb{Z}_3</math> – cyclic group of order 3 *<math>\mathbb{Z}_2 \times \mathbb{Z}_2</math> – the Klein four-group *<math>\mathbb{Z}_4</math> – cyclic group of order 4 *<math>\mathbb{Z}_5</math> – cyclic group of order 5 * the last one is an example of a quasigroup, or rather a loop, which is not associative. <!--- Any comments about the last example? Ilya Schurov 10:23, 23 October 2005 (UTC) --->
===Orthogonal pairs=== {{main|Mutually orthogonal Latin squares}}
Two Latin squares of the same order ''n'' are called '''orthogonal''' if, by overlaying them, one gets every ordered pair (''a'',''b'') of symbols where ''a'' is a symbol in the first square and ''b'' is one in the second square. Orthogonal pairs and more generally sets of pairwise orthogonal Latin squares are important in design theory and finite geometry.
== Completing a partial Latin square == A Latin rectangle is an ''m''-by-''n'' rectangle, where ''m'' < ''n'', such that each number 1, ..., ''n'' appears exactly once in each row and at most once in each column. Any Latin rectangle can be completed to a Latin square by adding rows. The proof uses Hall's marriage theorem.<ref>{{Cite web |last=Hall |first=Marshall |title=Bulletin of the American Mathematical Society |url=https://pubs.ams.org/journals/bull/1945-51-06/S0002-9904-1945-08361-X |access-date=2026-05-13 |website=pubs.ams.org}}</ref>
More generally, one may consider the problem of whether a partial filling of an ''n''-by-''n'' square with numbers 1, ..., ''n'' that does not contain two equal entries in any row or column can be completed to a Latin square. If ''n'' − 1 or fewer filled cells are given, this is always possible. Various other completability questions have been considered.<ref>{{Cite journal |last=Euler |first=Reinhardt |date=2010-02-01 |title=On the completability of incomplete Latin squares |url=https://www.sciencedirect.com/science/article/pii/S0195669809000948 |journal=European Journal of Combinatorics |series=Combinatorics and Geometry |volume=31 |issue=2 |pages=535–552 |doi=10.1016/j.ejc.2009.03.036 |issn=0195-6698|url-access=subscription }}</ref>
The problem of determining if a partially filled square can be completed to form a Latin square is NP-complete.<ref>{{cite journal | author = C. Colbourn | author-link = Charles Colbourn | title = The complexity of completing partial latin squares | journal = Discrete Applied Mathematics | volume = 8 | pages = 25–30 | year = 1984 | doi = 10.1016/0166-218X(84)90075-1| doi-access = free }}</ref>
== {{Anchor|transversal}}Transversals and rainbow matchings == {{See also|Hall-type theorems for hypergraphs#More conditions from rainbow matchings}} A '''transversal''' in a Latin square is a choice of ''n'' cells, where each row contains one cell, each column contains one cell, and there is one cell containing each symbol.
One can consider a Latin square as a complete bipartite graph in which the rows are vertices of one part, the columns are vertices of the other part, each cell is an edge (between its row and its column), and the symbols are colors. The rules of the Latin squares imply that this is a proper edge coloring. With this definition, a Latin transversal is a matching in which each edge has a different color; such a matching is called a rainbow matching.
Therefore, many results on Latin squares/rectangles are contained in papers with the term "rainbow matching" in their title, and vice versa.<ref>{{cite arXiv|eprint=1208.5670|class=math. CO|first1=Andras|last1=Gyarfas|first2=Gabor N.|last2=Sarkozy|title=Rainbow matchings and partial transversals of Latin squares|year=2012}}</ref>
Some Latin squares have no transversal. For example, when ''n'' is even, an ''n''-by-''n'' Latin square in which the value of cell ''i'',''j'' is (''i''+''j'') mod ''n'' has no transversal. Here are two examples:<math display="block"> \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix} \quad \begin{bmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ 3 & 4 & 1 & 2 \\ 4 & 1 & 2 & 3 \end{bmatrix} </math>In 1967, H. J. Ryser conjectured that, when ''n'' is '''odd''', every ''n''-by-''n'' Latin square has a transversal.<ref name=":0">{{Cite journal|last1=Aharoni|first1=Ron|last2=Berger|first2=Eli|last3=Kotlar|first3=Dani|last4=Ziv|first4=Ran|date=2017-01-04|title=On a conjecture of Stein|journal=Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg|volume=87|issue=2|pages=203–211|doi=10.1007/s12188-016-0160-3|s2cid=119139740|issn=0025-5858|arxiv=1605.01982}}</ref>
In 1975, S. K. Stein and Brualdi conjectured that, when ''n'' is '''even''', every ''n''-by-''n'' Latin square has a '''partial''' transversal of size ''n''−1.<ref>{{Cite journal|last=Stein|first=Sherman|date=1975-08-01|title=Transversals of Latin squares and their generalizations| journal=Pacific Journal of Mathematics| volume=59| issue=2| pages=567–575| doi=10.2140/pjm.1975.59.567|issn=0030-8730|doi-access=free}}</ref>
A more general conjecture of Stein is that a transversal of size ''n''−1 exists not only in Latin squares but also in any ''n''-by-''n'' array of ''n'' symbols, as long as each symbol appears exactly ''n'' times.<ref name=":0" />
Some weaker versions of these conjectures have been proved:
* Every ''n''-by-''n'' Latin square has a partial transversal of size 2''n''/3.<ref>{{Cite journal|last=Koksma|first=Klaas K.| date=1969-07-01|title=A lower bound for the order of a partial transversal in a latin square|journal=Journal of Combinatorial Theory|volume=7|issue=1|pages=94–95|doi=10.1016/s0021-9800(69)80009-8|issn=0021-9800|doi-access=free}}</ref> * Every ''n''-by-''n'' Latin square has a partial transversal of size ''n'' − sqrt(''n'').<ref>{{Cite journal| last=Woolbright| first=David E|date=1978-03-01|title=An n × n Latin square has a transversal with at least n−n distinct symbols|journal=Journal of Combinatorial Theory, Series A|volume=24|issue=2|pages=235–237|doi=10.1016/0097-3165(78)90009-2|issn=0097-3165|doi-access=free}}</ref> * Every ''n''-by-''n'' Latin square has a partial transversal of size ''n'' − 11 log{{su|b=2|p=2}}(''n'').<ref>{{Cite journal|last1=Hatami|first1=Pooya|last2=Shor|first2=Peter W.|date=2008-10-01|title=A lower bound for the length of a partial transversal in a Latin square|journal=Journal of Combinatorial Theory, Series A|volume=115| issue=7| pages=1103–1113| doi=10.1016/j.jcta.2008.01.002|issn=0097-3165|doi-access=free}}</ref> * Every ''n''-by-''n'' Latin square has a partial transversal of size ''n'' − O(log n/loglog n).<ref>{{Cite journal |last1=Keevash |first1=Peter |last2=Pokrovskiy |first2=Alexey |last3=Sudakov |first3=Benny |last4=Yepremyan |first4=Liana |date=2022-04-15 |title=New bounds for Ryser's conjecture and related problems |url=https://www.ams.org/btran/2022-09-08/S2330-0000-2022-00092-3/ |journal=Transactions of the American Mathematical Society, Series B |language=en |volume=9 |issue=8 |pages=288–321 |doi=10.1090/btran/92 |issn=2330-0000|doi-access=free |hdl=20.500.11850/592212 |hdl-access=free }}</ref> * Every large enough ''n''-by-''n'' Latin square has a partial transversal of size ''n'' −1.<ref>{{Cite arXiv |last=Montgomery |first=Richard |date=2023 |title=A proof of the Ryser-Brualdi-Stein conjecture for large even ''n'' |class=math.CO |eprint=2310.19779}}</ref> (Preprint)
==Algorithms== For small squares it is possible to generate permutations and test whether the Latin square property is met. For larger squares, Jacobson and Matthews' algorithm allows sampling from a uniform distribution over the space of ''n'' × ''n'' Latin squares.<ref>{{Cite journal | doi = 10.1002/(sici)1520-6610(1996)4:6<405::aid-jcd3>3.0.co;2-j| title = Generating uniformly distributed random latin squares| journal = Journal of Combinatorial Designs| volume = 4| issue = 6| pages = 405–437| year = 1996| last1 = Jacobson | first1 = M. T. | last2 = Matthews | first2 = P. }}</ref>
==Applications==
===Statistics and mathematics=== *In the design of experiments, Latin squares are a special case of ''row-column designs'' for two blocking factors.<ref>{{cite book |author-link=Rosemary A. Bailey|first=R.A.|last=Bailey|chapter=6 Row-Column designs and 9 More about Latin squares|title=Design of Comparative Experiments|publisher=Cambridge University Press|year=2008 |isbn=978-0-521-68357-9|chapter-url=http://www.maths.qmul.ac.uk/~rab/DOEbook|mr=2422352}}</ref><ref>{{cite book |last1=Shah|first1= Kirti R.|last2=Sinha|first2= Bikas K.| chapter=4 Row-Column Designs|title=Theory of Optimal Designs |series=Lecture Notes in Statistics| volume=54 | publisher=Springer-Verlag | year=1989 | pages=66–84 |isbn=0-387-96991-8 |mr=1016151}}</ref> *In algebra, Latin squares are related to generalizations of groups; in particular, Latin squares are characterized as being the multiplication tables (Cayley tables) of quasigroups. A binary operation whose table of values forms a Latin square is said to obey the Latin square property.
===Error correcting codes=== Sets of Latin squares that are orthogonal to each other have found an application as error correcting codes in situations where communication is disturbed by more types of noise than simple white noise, such as when attempting to transmit broadband Internet over powerlines.<ref name="CKL">{{cite journal | last1 = Colbourn | first1 = C.J. | author-link = Charles Colbourn | last2 = Kløve | first2 = T. | last3 = Ling | first3 = A.C.H. | year = 2004 | title = Permutation arrays for powerline communication | journal = IEEE Trans. Inf. Theory | volume = 50 | pages = 1289–1291 | doi=10.1109/tit.2004.828150| s2cid = 15920471 }}</ref><ref name="NS">''Euler's revolution'', New Scientist, 24 March 2007, pp 48–51</ref><ref name="SH">{{cite journal | last1 = Huczynska | first1 = Sophie | year = 2006| title = Powerline communication and the 36 officers problem | journal = Philosophical Transactions of the Royal Society A | volume = 364 | issue = 1849| pages = 3199–3214 | doi=10.1098/rsta.2006.1885| pmid = 17090455 | bibcode = 2006RSPTA.364.3199H | s2cid = 17662664 }}</ref>
Firstly, the message is sent by using several frequencies, or channels, a common method that makes the signal less vulnerable to noise at any one specific frequency. A letter in the message to be sent is encoded by sending a series of signals at different frequencies at successive time intervals. In the example below, the letters A to L are encoded by sending signals at four different frequencies, in four time slots. The letter C, for instance, is encoded by first sending at frequency 3, then 4, 1 and 2.
<div class="center"><math display="block"> \begin{matrix} A\\ B\\ C\\ D\\ \end{matrix}
\begin{bmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \\ \end{bmatrix} \quad
\begin{matrix} E\\ F\\ G\\ H\\ \end{matrix}
\begin{bmatrix} 1 & 3 & 4 & 2\\ 2 & 4 & 3 & 1\\ 3 & 1 & 2 & 4\\ 4 & 2 & 1 & 3\\ \end{bmatrix} \quad \begin{matrix} I\\ J\\ K\\ L\\ \end{matrix}
\begin{bmatrix} 1 & 4 & 2 & 3\\ 2 & 3 & 1 & 4\\ 3 & 2 & 4 & 1\\ 4 & 1 & 3 & 2\\ \end{bmatrix} </math></div>
The encoding of the twelve letters are formed from three Latin squares that are orthogonal to each other. Now imagine that there's added noise in channels 1 and 2 during the whole transmission. The letter A would then be picked up as <math display="block">\begin{matrix}12 & 12 & 123 & 124\end{matrix}</math>
In other words, in the first slot we receive signals from both frequency 1 and frequency 2; while the third slot has signals from frequencies 1, 2 and 3. Because of the noise, we can no longer tell if the first two slots were 1,1 or 1,2 or 2,1 or 2,2. But the 1,2 case is the only one that yields a sequence matching a letter in the above table, the letter A. Similarly, we may imagine a burst of static over all frequencies in the third slot: <math display="block">\begin{matrix}1 & 2 & 1234 & 4\end{matrix}</math>
Again, we are able to infer from the table of encodings that it must have been the letter A being transmitted. The number of errors this code can spot is one less than the number of time slots. It has also been proven that if the number of frequencies is a prime or a power of a prime, the orthogonal Latin squares produce error detecting codes that are as efficient as possible.
===Mathematical puzzles=== [[File:Ramanujan_magic_square_construction.svg|thumb|Construction of Ramanujan's birthday magic square from a 4×4 Latin square with distinct diagonals and day (D), month (M), century (C) and year (Y) values, and Ramanujan's birthday example]]
The popular Sudoku puzzles are a special case of Latin squares; any solution to a Sudoku puzzle is a Latin square. Sudoku imposes the additional restriction that nine particular 3 × 3 adjacent subsquares must also contain the digits 1–9 (in the standard version). See also Mathematics of Sudoku.
The more recent KenKen and Strimko puzzles are also examples of Latin squares.
===Board games===
Latin squares have been used as the basis for several board games, notably the popular abstract strategy game Kamisado.
===Agronomic research===
Latin squares are used in the design of agronomic research experiments to minimise experimental errors.<ref>{{Cite web |url=http://joas.agrif.bg.ac.rs/archive/article/59 |title=The application of Latin square in agronomic research |access-date=2017-04-02 |archive-date=2017-12-15 |archive-url=https://web.archive.org/web/20171215053902/http://joas.agrif.bg.ac.rs/archive/article/59 |url-status=dead }}</ref>
==Heraldry== The Latin square also figures in the arms of the Statistical Society of Canada,<ref>{{cite web|url=http://www.ssc.ca/archive/main/about/history/arms_e.html|archive-url=https://web.archive.org/web/20130521075715/http://www.ssc.ca/archive/main/about/history/arms_e.html|url-status=dead|archive-date=2013-05-21|title=Letters Patent Confering the SSC Arms|work=ssc.ca}}</ref> being specifically mentioned in its blazon. Also, it appears in the logo of the International Biometric Society.<ref>[http://www.tibs.org The International Biometric Society<!-- Bot generated title -->] {{webarchive| url=https://web.archive.org/web/20050507083541/http://www.tibs.org/ |date=2005-05-07 }}</ref>
== Generalizations == thumb|upright=0.5|An order-4 Latin cube exploded * A Latin rectangle is a generalization of a Latin square in which there are ''n'' columns and ''n'' possible values, but the number of rows may be smaller than ''n''. Each value still appears at most once in each row and column. * A Graeco-Latin square is a pair of two Latin squares such that, when one is laid on top of the other, each ordered pair of symbols appears exactly once. * A Latin hypercube is a generalization of a Latin square from two dimensions to multiple dimensions.
==See also== *Block design *Combinatorial design *Eight queens puzzle *Futoshiki *Magic square *Problems in Latin squares *Rook's graph, a graph that has Latin squares as its colorings *Sator Square *Vedic square *Word square
==Notes== {{reflist}}
==References== * {{cite book |author-link=Rosemary A. Bailey|first=R.A.|last=Bailey|chapter=6 Row-Column designs and 9 More about Latin squares|title=Design of Comparative Experiments|publisher=Cambridge University Press|year=2008 |isbn=978-0-521-68357-9|chapter-url=http://www.maths.qmul.ac.uk/~rab/DOEbook|mr=2422352}} * {{cite book|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}} * {{cite book |author1=Shah, Kirti R.|author2=Sinha, Bikas K.| chapter=4 Row-Column Designs|title=Theory of Optimal Designs |series=Lecture Notes in Statistics| volume=54 | publisher=Springer-Verlag | year=1989 | pages=66–84 |isbn=0-387-96991-8 |mr=1016151}} *{{cite book|first1=J. H.|last1=van Lint|author2-link=Richard M. Wilson|first2=R. M.|last2=Wilson|title=A Course in Combinatorics|url=https://archive.org/details/coursecombinator00lint_417|url-access=limited|publisher=Cambridge University Press|year=1992|isbn=0-521-42260-4|page=[https://archive.org/details/coursecombinator00lint_417/page/n168 157]}}
==Further reading== * {{cite book|last1=Dénes|first1=J. H.|last2=Keedwell|first2=A. D.|title=Latin squares: New developments in the theory and applications|others=Paul Erdős (foreword)|series=Annals of Discrete Mathematics|volume=46|publisher=Academic Press |location=Amsterdam|year=1991 |mr=1096296|isbn=0-444-88899-3}} *{{cite book | last1=Hinkelmann | first1=Klaus | author-link2=Oscar Kempthorne | last2=Kempthorne | first2=Oscar | year=2008 | title=Design and Analysis of Experiments | volume=I, II |edition=Second | publisher=Wiley |url=http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0470385510.html | isbn=978-0-470-38551-7 | mr=2363107}} **{{cite book |last1=Hinkelmann | first1=Klaus | author-link2=Oscar Kempthorne | last2=Kempthorne | first2=Oscar | year=2008 | title=Design and Analysis of Experiments, Volume I: Introduction to Experimental Design | url=https://books.google.com/books?id=T3wWj2kVYZgC | edition=Second|publisher= Wiley | isbn=978-0-471-72756-9 |mr=2363107}} **{{cite book |last1=Hinkelmann | first1=Klaus | author-link2=Oscar Kempthorne | last2=Kempthorne | first2=Oscar |year=2005| title=Design and Analysis of Experiments, Volume 2: Advanced Experimental Design|url=https://books.google.com/books?id=GiYc5nRVKf8C|edition=First|publisher= Wiley |isbn=978-0-471-55177-5|mr=2129060}} * {{cite book|first=Donald|last=Knuth|author-link=Donald Knuth|title=The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1|title-link=The Art of Computer Programming|location=Reading, Massachusetts|publisher=Addison-Wesley| year=2011| isbn=978-0-201-03804-0}} * {{cite book|last1=Laywine|first1=Charles F.|last2=Mullen|first2=Gary L.| title=Discrete mathematics using Latin squares| series=Wiley-Interscience Series in Discrete Mathematics and Optimization|publisher=John Wiley & Sons, Inc.|location=New York| year=1998|isbn=0-471-24064-8|mr=1644242}} *{{cite book|author1=Shah, K. R.|author2=Sinha, Bikas K.|chapter=Row-column designs |pages=903–937 | title=Design and analysis of experiments | editor=S. Ghosh and C. R. Rao | series=Handbook of Statistics|volume=13|publisher=North-Holland Publishing Co.|location=Amsterdam|year=1996|isbn=0-444-82061-2|mr=1492586}} * {{cite book|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|mr=1102899|isbn=0-486-65685-3|url-access=registration| url=https://archive.org/details/constructionscom0000ragh|author-link=Damaraju Raghavarao}} *{{cite book|last1=Street|first1=Anne Penfold |author1-link= Anne Penfold Street |last2=Street|first2= Deborah J.|author2-link= Deborah Street |title=Combinatorics of Experimental Design|title-link= Combinatorics of Experimental Design |publisher=Oxford University Press|year=1987|location=New York|isbn=0-19-853256-3| mr=908490 }} *{{cite book |last1=Berger |first1=Paul D. |last2=Maurer |first2=Robert E. |last3=Celli |first3=Giovana B. |title=Experimental Design with Applications in Management, Engineering, and the Sciences |date=November 28, 2017 |publisher=Springer |pages=267–282 |edition=2nd edition (November 28, 2017) }}
==External links== *{{MathWorld |title=Latin Square|id=LatinSquare}} *[https://encyclopediaofmath.org/wiki/Latin_square Latin Squares] in the Encyclopaedia of Mathematics *[https://oeis.org/wiki/Index_to_OEIS:_Section_La#Latin Latin Squares] in the Online Encyclopedia of Integer Sequences {{Experimental design}} {{Magic polygons}} {{authority control}}
Category:Latin squares Category:Design of experiments Category:Non-associative algebra Category:Error detection and correction