In combinatorics and in experimental design, 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 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,(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, ...") 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. (Note: Euler first presented this memoir to the Imperial Academy of Sciences of St. Petersburg, Russia on 8 March 1779.)
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.
Counting This account follows .
The counting of Latin squares has a long history, but the published accounts contain many errors. Euler in 1782, and Cayley in 1890, both knew the number of reduced Latin squares up to order five. In 1915, MacMahon approached the problem in a different way, but initially obtained the wrong value for order five. M.Frolov in 1890, and Tarry in 1901, 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, unaware of earlier work of E. Schönhardt, gave the number of isotopy classes of orders up to six. In 1939, H. W. Norton found 562 isotopy classes of order seven, but acknowledged that his method was incomplete. A. Sade, in 1951, but privately published earlier in 1948, and P. N. Saxena found more classes and, in 1966, D. A. Preece noted that this corrected Norton's result to 564 isotopy classes. However, in 1968, J. W. Brown announced an incorrect value of 563, 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, and the numbers of isotopy classes, in 1990, by G. Kolesova, C.W.H. Lam and L. Thiel. The number of reduced squares for order nine was obtained by S. E. Bammel and J. Rothstein, for order 10 by B. D. McKay and E. Rogoyski, and for order 11 by B. D. McKay and I. M. Wanless.
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. 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:
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 n2 triples called the orthogonal array representation of the square. For example, the orthogonal array representation of the Latin square
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 rcs1111221332 1 2223231313321332
The definition of a Latin square can be written in terms of orthogonal arrays: A Latin square is a set of n2 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 n2 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
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 and of side with common symbol set that is also the index set for the rows and columns of each square are isomorphic if there is a bijection such that for all , in . 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. 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.
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. Each main class contains up to six isotopy classes.
Number of Latin squares
There is no known easily computable formula for the number of Latin squares with symbols . The most accurate upper and lower bounds known for large are far apart. One classic result is that
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 of Latin squares is
where is the set of all {0, 1}-matrices, is the number of zero entries in matrix , and is the permanent of matrix .
The table below contains all known exact values. It can be seen that the numbers grow exceedingly quickly. For each , the number of Latin squares altogether is times the number of reduced Latin squares .
+ The numbers of Latin squares of various sizes reduced Latin squares of size all Latin squares of size 1 1 1 2 1 2 3 1 12 4 4 576 5 56 161,280 6 9,408 812,851,200 7 16,942,080 61,479,419,904,000 8 535,281,401,856 108,776,032,459,082,956,800 9 377,597,570,964,258,816 5,524,751,496,156,892,842,531,225,600 10 7,580,721,483,160,132,811,489,280 9,982,437,658,213,039,871,725,064,756,920,320,000 11 5,363,937,773,277,371,298,119,673,540,771,840 776,966,836,171,770,144,107,444,346,734,230,682,311,065,600,000 121.62 × 1044132.51 × 1056142.33 × 1070151.50 × 1086
For each , each isotopy class contains up to Latin squares (the exact number varies), while each main class contains either 1, 2, 3 or 6 isotopy classes.
+ Equivalence classes of Latin squares main classes isotopy classesstructurally distinct squares 1 1 1 1 2 1 1 1 3 1 1 1 4 2 2 12 5 2 2 192 6 12 22 145,164 7 147 564 1,524,901,344 8 283,657 1,676,267 337,227,973,870,688 9 19,270,853,541 115,618,721,533 1,903,091,757,869,061,874,944 10 34,817,397,894,749,939 208,904,371,354,363,006343,861,526,476,243,186,839,288,010,752 11 2,036,029,552,582,883,134,196,099 12,216,177,315,369,229,261,482,5402,433,082,173,958,615,621,272,808,456,621,110,067,200
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 = 1 up to 7 is 1, 1, 1, 12, 192, 145164, 1524901344 respectively .
Examples
We give one example of a Latin square from each main class up to order five.
They present, respectively, the multiplication tables of the following groups: {0} – the trivial 1-element group – the binary group – cyclic group of order 3 – the Klein four-group – cyclic group of order 4 – cyclic group of order 5 the last one is an example of a quasigroup, or rather a loop, which is not associative.
Orthogonal pairs
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.
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.
The problem of determining if a partially filled square can be completed to form a Latin square is NP-complete.
A critical set in a Latin square is a partial Latin square that has a unique completion, but for which no proper subset has a unique completion. The notations scs(n) and lcs(n) denote, respectively, the smallest and largest possible size of a critical set in any Latin square of order n. The exact values of scs(n) are known for n ≤ 8, and those of lcs(n) for n ≤ 7: + Sizes of critical sets n 12345678 scs(n) 0124691216 lcs(n) 0137111825—
Transversals and 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.
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:In 1967, H. J. Ryser conjectured that, when n is odd, every n-by-n Latin square has a transversal.