Latin square

Last updated
Displaying a 7 x 7 Latin square, this stained glass window honors Ronald Fisher, whose Design of Experiments discussed Latin squares. Fisher-stainedglass-gonville-caius.jpg
Displaying a 7 × 7 Latin square, this stained glass window honors Ronald Fisher, whose Design of Experiments discussed Latin squares.

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

Contents

ABC
CAB
BCA

The name "Latin square" was inspired by mathematical papers by Leonhard Euler (1707–1783), who used Latin characters as symbols, [1] 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.

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. [2]

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. [3] 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:

ABC
BCA
CAB

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

123
231
312

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:

rcs
111
122
133
212
223
231
313
321
332

The definition of a Latin square can be written in terms of orthogonal arrays:

This means that the n2 ordered pairs (r, c) are all the pairs (i, j) with 1 ≤ i, jn, 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, and 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.

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. [4]

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. [4] Each main class contains up to six isotopy classes.

Number

There is no known easily computable formula for the number Ln of n×n Latin squares with symbols 1,2,...,n. The most accurate upper and lower bounds known for large n are far apart. One classic result [5] 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 Ln of n×n Latin squares is

where Bn is the set of all n × n {0, 1} matrices, σ0(A) is the number of zero entries in matrix A, and per(A) is the permanent of matrix A. [6]

The table below contains all known exact values. It can be seen that the numbers grow exceedingly quickly. For each n, the number of Latin squares altogether (sequence A002860 in the OEIS ) is n! (n-1)! times the number of reduced Latin squares (sequence A000315 in the OEIS ).

The numbers of Latin squares of various sizes
nreduced Latin squares of size n
(sequence A000315 in the OEIS )
all Latin squares of size n
(sequence A002860 in the OEIS )
111
212
3112
44576
556161,280
69,408812,851,200
716,942,08061,479,419,904,000
8535,281,401,856108,776,032,459,082,956,800
9377,597,570,964,258,8165,524,751,496,156,892,842,531,225,600
107,580,721,483,160,132,811,489,2809,982,437,658,213,039,871,725,064,756,920,320,000
115,363,937,773,277,371,298,119,673,540,771,840776,966,836,171,770,144,107,444,346,734,230,682,311,065,600,000
121.62 × 1044
132.51 × 1056
142.33 × 1070
151.50 × 1086

For each n, each isotopy class (sequence A040082 in the OEIS ) contains up to (n!)3 Latin squares (the exact number varies), while each main class (sequence A003090 in the OEIS ) contains either 1, 2, 3 or 6 isotopy classes.

Equivalence classes of Latin squares
nmain classes

(sequence A003090 in the OEIS )

isotopy classes

(sequence A040082 in the OEIS )

structurally distinct squares

(sequence A264603 in the OEIS )

1111
2111
3111
42212
522192
61222145,164
71475641,524,901,344
8283,6571,676,267
919,270,853,541115,618,721,533
1034,817,397,894,749,939208,904,371,354,363,006
112,036,029,552,582,883,134,196,09912,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, reflexion, and/or permutation of the symbols) for n = 1 up to 7 is 1, 1, 1, 12, 192, 145164, 1524901344 respectively (sequence A264603 in the OEIS ) .

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:

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

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. [8]

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. [9]

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. [8]

Some weaker versions of these conjectures have been proved:

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. [13]

Applications

Statistics and mathematics

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. [16] [17] [18]

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.

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:

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:

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

The problem of determining if a partially filled square can be completed to form a Latin square is NP-complete. [19]

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 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. [20]

Heraldry

The Latin square also figures in the arms of the Statistical Society of Canada, [21] being specifically mentioned in its blazon. Also, it appears in the logo of the International Biometric Society. [22]

Generalizations

See also

Notes

  1. Wallis, W. D.; George, J. C. (2011), Introduction to Combinatorics, CRC Press, p. 212, ISBN   978-1-4398-0623-4
  2. Colbourn, Charles J.; Dinitz, Jeffrey H. (2 November 2006). Handbook of Combinatorial Designs (2nd ed.). CRC Press. p. 12. ISBN   9781420010541 . Retrieved 28 March 2017.
  3. Dénes & Keedwell 1974 , p. 128
  4. 1 2 Dénes & Keedwell 1974 , p. 126
  5. van Lint & Wilson 1992 , pp. 161-162
  6. Jia-yu Shao; Wan-di Wei (1992). "A formula for the number of Latin squares". Discrete Mathematics . 110 (1–3): 293–296. doi:10.1016/0012-365x(92)90722-r.
  7. Gyarfas, Andras; Sarkozy, Gabor N. (2012). "Rainbow matchings and partial transversals of Latin squares". arXiv: 1208.5670 [CO math. CO].
  8. 1 2 Aharoni, Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran (2017-01-04). "On a conjecture of Stein". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 87 (2): 203–211. doi:10.1007/s12188-016-0160-3. ISSN   0025-5858. S2CID   119139740.
  9. Stein, Sherman (1975-08-01). "Transversals of Latin squares and their generalizations". Pacific Journal of Mathematics. 59 (2): 567–575. doi: 10.2140/pjm.1975.59.567 . ISSN   0030-8730.
  10. Koksma, Klaas K. (1969-07-01). "A lower bound for the order of a partial transversal in a latin square". Journal of Combinatorial Theory. 7 (1): 94–95. doi: 10.1016/s0021-9800(69)80009-8 . ISSN   0021-9800.
  11. Woolbright, David E (1978-03-01). "An n × n Latin square has a transversal with at least n−n distinct symbols". Journal of Combinatorial Theory, Series A. 24 (2): 235–237. doi:10.1016/0097-3165(78)90009-2. ISSN   0097-3165.
  12. Hatami, Pooya; Shor, Peter W. (2008-10-01). "A lower bound for the length of a partial transversal in a Latin square". Journal of Combinatorial Theory, Series A. 115 (7): 1103–1113. doi:10.1016/j.jcta.2008.01.002. ISSN   0097-3165.
  13. Jacobson, M. T.; Matthews, P. (1996). "Generating uniformly distributed random latin squares". Journal of Combinatorial Designs. 4 (6): 405–437. doi:10.1002/(sici)1520-6610(1996)4:6<405::aid-jcd3>3.0.co;2-j.
  14. Bailey, R.A. (2008), "6 Row-Column designs and 9 More about Latin squares", Design of Comparative Experiments, Cambridge University Press, ISBN   978-0-521-68357-9, MR   2422352
  15. Shah, Kirti R.; Sinha, Bikas K. (1989), "4 Row-Column Designs", Theory of Optimal Designs, Lecture Notes in Statistics, 54, Springer-Verlag, pp. 66–84, ISBN   0-387-96991-8, MR   1016151
  16. Colbourn, C.J.; Kløve, T.; Ling, A.C.H. (2004). "Permutation arrays for powerline communication". IEEE Trans. Inf. Theory. 50: 1289–1291. doi:10.1109/tit.2004.828150. S2CID   15920471.
  17. Euler's revolution, New Scientist, 24 March 2007, pp 48–51
  18. Huczynska, Sophie (2006). "Powerline communication and the 36 officers problem". Philosophical Transactions of the Royal Society A. 364 (1849): 3199–3214. doi:10.1098/rsta.2006.1885. PMID   17090455. S2CID   17662664.
  19. C. Colbourn (1984). "The complexity of completing partial latin squares". Discrete Applied Mathematics. 8: 25–30. doi:10.1016/0166-218X(84)90075-1.
  20. http://joas.agrif.bg.ac.rs/archive/article/59 | The application of Latin square in agronomic research
  21. "Letters Patent Confering the SSC Arms". ssc.ca. Archived from the original on 2013-05-21.
  22. The International Biometric Society Archived 2005-05-07 at the Wayback Machine

Related Research Articles

In linear algebra, the determinant is a scalar value that can be computed from the elements of a square matrix and encodes certain properties of the linear transformation described by the matrix. The determinant of a matrix A is denoted det(A), det A, or |A|.

In linear algebra, the rank of a matrix A is the dimension of the vector space generated by its columns. This corresponds to the maximal number of linearly independent columns of A. This, in turn, is identical to the dimension of the vector space spanned by its rows. Rank is thus a measure of the "nondegenerateness" of the system of linear equations and linear transformation encoded by A. There are multiple equivalent definitions of rank. A matrix's rank is one of its most fundamental characteristics.

Row and column spaces

In linear algebra, the column space of a matrix A is the span of its column vectors. The column space of a matrix is the image or range of the corresponding matrix transformation.

In linear algebra, an orthogonal matrix, or orthonormal matrix, is a real square matrix whose columns and rows are orthonormal vectors.

Square matrix

In mathematics, a square matrix is a matrix with the same number of rows and columns. An n-by-n matrix is known as a square matrix of order . Any two square matrices of the same order can be added and multiplied.

Transpose

In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal; that is, it switches the row and column indices of the matrix A by producing another matrix, often denoted by AT.

In mathematics, especially in applications of linear algebra to physics, the Einstein notation or Einstein summation convention is a notational convention that implies summation over a set of indexed terms in a formula, thus achieving notational brevity. As part of mathematics it is a notational subset of Ricci calculus; however, it is often used in applications in physics that do not distinguish between tangent and cotangent spaces. It was introduced to physics by Albert Einstein in 1916.

In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say P, represents a permutation of m elements and, when used to multiply another matrix, say A, results in permuting the rows or columns of the matrix A.

In linear algebra, a square matrix  is called diagonalizable or non-defective if it is similar to a diagonal matrix, i.e., if there exists an invertible matrix  and a diagonal matrix such that , or equivalently . For a finite-dimensional vector space , a linear map  is called diagonalizable if there exists an ordered basis of  consisting of eigenvectors of . These definitions are equivalent: if  has a matrix representation as above, then the column vectors of  form a basis of eigenvectors of , and the diagonal entries of  are the corresponding eigenvalues of ; with respect to this eigenvector basis,  is represented by . Diagonalization is the process of finding the above  and .

In combinatorics, two Latin squares of the same size (order) are said to be orthogonal if when superimposed the ordered paired entries in the positions are all distinct. A set of Latin squares, all of the same order, all pairs of which are orthogonal is called a set of mutually orthogonal Latin squares. This concept of orthogonality in combinatorics is strongly related to the concept of blocking in statistics, which ensures that independent variables are truly independent with no hidden confounding correlations. "Orthogonal" is thus synonymous with "independent" in that knowing one variable's value gives no further information about another variable's likely value.

In mathematics, a Hadamard matrix, named after the French mathematician Jacques Hadamard, is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal. In geometric terms, this means that each pair of rows in a Hadamard matrix represents two perpendicular vectors, while in combinatorial terms, it means that each pair of rows has matching entries in exactly half of their columns and mismatched entries in the remaining columns. It is a consequence of this definition that the corresponding properties hold for columns as well as rows. The n-dimensional parallelotope spanned by the rows of an n×n Hadamard matrix has the maximum possible n-dimensional volume among parallelotopes spanned by vectors whose entries are bounded in absolute value by 1. Equivalently, a Hadamard matrix has maximal determinant among matrices with entries of absolute value less than or equal to 1 and so is an extremal solution of Hadamard's maximal determinant problem.

In mathematics, the kernel of a linear map, also known as the null space or nullspace, is the linear subspace of the domain of the map which is mapped to the zero vector. That is, given a linear map L : VW between two vector spaces V and W, the kernel of L is the vector space of all elements v of V such that L(v) = 0, where 0 denotes the zero vector in W, or more symbolically:

Combinatorial design theory is the part of combinatorial mathematics that deals with the existence, construction and properties of systems of finite sets whose arrangements satisfy generalized concepts of balance and/or symmetry. These concepts are not made precise so that a wide range of objects can be thought of as being under the same umbrella. At times this might involve the numerical sizes of set intersections as in block designs, while at other times it could involve the spatial arrangement of entries in an array as in sudoku grids.

Latin squares and quasigroups are equivalent mathematical objects, although the former has a combinatorial nature while the latter is more algebraic. The listing below will consider the examples of some very small orders, which is the side length of the square, or the number of elements in the equivalent quasigroup.

In mathematics, Bondy's theorem is a bound on the number of elements needed to distinguish the sets in a family of sets from each other. It belongs to the field of combinatorics, and is named after John Adrian Bondy, who published it in 1972.

In mathematics, an orthostochastic matrix is a doubly stochastic matrix whose entries are the squares of the absolute values of the entries of some orthogonal matrix.

In mathematics, an orthogonal array is a "table" (array) whose entries come from a fixed finite set of symbols, arranged in such a way that there is an integer t so that for every selection of t columns of the table, all ordered t-tuples of the symbols, formed by taking the entries in each row restricted to these columns, appear the same number of times. The number t is called the strength of the orthogonal array. Here is a simple example of an orthogonal array with symbol set {1,2} and strength 2:

Matrix (mathematics) Two-dimensional array of numbers with specific operations

In mathematics, a matrix is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns. For example, the dimension of the matrix below is 2 × 3, because there are two rows and three columns:

In combinatorial mathematics, a Latin rectangle is an r × n matrix, using n symbols, usually the numbers 1, 2, 3, ..., n or 0, 1, ..., n − 1 as its entries, with no number occurring more than once in any row or column.

Hadamard's maximal determinant problem, named after Jacques Hadamard, asks for the largest determinant of a matrix with elements equal to 1 or −1. The analogous question for matrices with elements equal to 0 or 1 is equivalent since, as will be shown below, the maximal determinant of a {1,−1} matrix of size n is 2n−1 times the maximal determinant of a {0,1} matrix of size n−1. The problem was posed by Hadamard in the 1893 paper in which he presented his famous determinant bound and remains unsolved for matrices of general size. Hadamard's bound implies that {1, −1}-matrices of size n have determinant at most nn/2. Hadamard observed that a construction of Sylvester produces examples of matrices that attain the bound when n is a power of 2, and produced examples of his own of sizes 12 and 20. He also showed that the bound is only attainable when n is equal to 1, 2, or a multiple of 4. Additional examples were later constructed by Scarpis and Paley and subsequently by many other authors. Such matrices are now known as Hadamard matrices. They have received intensive study.

References

Further reading