- Latin square
A

**Latin square**is an "n" × "n" table filled with "n" different symbols in such a way that each symbol occurs exactly once in each row and exactly once in each column. Here is an example:

$egin\{bmatrix\}\; 1\; 2\; 3\; \backslash \; 2\; 3\; 1\; \backslash \; 3\; 1\; 2\; \backslash end\{bmatrix\}$Latin squares occur as the

multiplication table s (Cayley table s) ofquasigroup s. They have applications in thedesign of experiments and inerror correcting codes .The name Latin square originates from

Leonhard Euler , who usedLatin characters as symbols.A Latin square is said to be "reduced" (also, "normalized" or "in standard form") if its first row and first column are in natural order. For example, the Latin square above is reduced because both its first row and its first column are 1,2,3 (rather than 3,1,2 or any other order). We can make any Latin square reduced by permuting (reordering) the rows and columns.

**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"

^{2}triples called the orthogonal array representation of the square. For example, the orthogonal array representation of the first Latin square displayed above 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. The definition of a Latin square can be written in terms of orthogonal arrays as follows:

* There are "n"^{2}triples of the form ("r","c","s"), where 1 ≤ "r", "c", "s" ≤ "n".

* All of the pairs ("r","c") are different, all the pairs ("r","s") are different, and all the pairs ("c","s") are different.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, 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

parastrophe s) 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 calledmain class es, "species", or paratopy classes. Each main class contains up to 6 isotopy classes.**The number of Latin squares**There is no known easily-computable formula for the number of "n" × "n" Latin squares with symbols 1,2,...,"n". The most accurate upper and lower bounds known for large "n" are far apart. Here we will give all the known exact values. It can be seen that the numbers grow exceedingly quickly.

For each "n", the number of Latin squares altogether OEIS|id=A002860 is "n"! ("n"-1)! times the number of reduced Latin squares OEIS|id=A000315.

For each "n", each isotopy class OEIS|id=A040082 contains up to ("n"!)

^{3}Latin squares (the exact number varies), while each main class OEIS|id=A003090 contains either 1, 2, 3 or 6 isotopy classes.**Examples**We give one example of a Latin square from each main class up to order 5.

$egin\{bmatrix\}\; 1end\{bmatrix\}quadegin\{bmatrix\}\; 1\; 2\; \backslash \; 2\; 1end\{bmatrix\}quadegin\{bmatrix\}\; 1\; 2\; 3\; \backslash \; 2\; 3\; 1\; \backslash \; 3\; 1\; 2end\{bmatrix\}$

$egin\{bmatrix\}\; 1\; 2\; 3\; 4\; \backslash \; 2\; 1\; 4\; 3\; \backslash \; 3\; 4\; 1\; 2\; \backslash \; 4\; 3\; 2\; 1\; end\{bmatrix\}quadegin\{bmatrix\}\; 1\; 2\; 3\; 4\; \backslash \; 2\; 4\; 1\; 3\; \backslash \; 3\; 1\; 4\; 2\; \backslash \; 4\; 3\; 2\; 1\; end\{bmatrix\}$

$egin\{bmatrix\}\; 1\; 2\; 3\; 4\; 5\; \backslash \; 2\; 3\; 5\; 1\; 4\; \backslash \; 3\; 5\; 4\; 2\; 1\; \backslash \; 4\; 1\; 2\; 5\; 3\; \backslash \; 5\; 4\; 1\; 3\; 2\; end\{bmatrix\}quadegin\{bmatrix\}\; 1\; 2\; 3\; 4\; 5\; \backslash \; 2\; 4\; 1\; 5\; 3\; \backslash \; 3\; 5\; 4\; 2\; 1\; \backslash \; 4\; 1\; 5\; 3\; 2\; \backslash \; 5\; 3\; 2\; 1\; 4end\{bmatrix\}$They present, respectively, the multiplication tables of the following groups:

*{0} - the trivial 1-element group

*$mathbb\{Z\}\_2$ - the binary group

*$mathbb\{Z\}\_3$ -cyclic group of order 3

*$mathbb\{Z\}\_2\; imes\; mathbb\{Z\}\_2$ - the Klein four-group

*$mathbb\{Z\}\_4$ - cyclic group of order 4

*$mathbb\{Z\}\_5$ - cyclic group of order 5

* the last one is an example of aquasigroup , or rather a loop, which is not associative**Latin squares and 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 simplewhite noise , such as when attempting to transmit broadband internet over powerlines. C.J. Colbourn, T. Kløve, and A.C.H. Ling, "Permutation arrays for powerline communication",IEEE Trans. Inform. Theory, vol. 50, pp. 1289-1291, 2004.] "Euler's revolution",New Scientist, 24th of March 2007, pp 48-51] Sophie Huczynska, "Powerline communication and the 36 officers problem",Philosophical Transactions of the Royal Society A, vol 364, p 3199.]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.

$egin\{matrix\}A\backslash B\backslash C\backslash D\backslash end\{matrix\}$egin{bmatrix} 1 & 2 & 3 & 4 \ 2 & 1 & 4 & 3 \ 3 & 4 & 1 & 2 \ 4 & 3 & 2 & 1 \ end{bmatrix}quad

egin{matrix}E\F\G\H\end{matrix}

egin{bmatrix}1 & 3 & 4 & 2\2 & 4 & 3 & 1\3 & 1 & 2 & 4\4 & 2 & 1 & 3\end{bmatrix}quadegin{matrix}I\J\K\L\end{matrix}

egin{bmatrix}1 & 4 & 2 & 3\2 & 3 & 1 & 4\3 & 2 & 4 & 1\4 & 1 & 3 & 2\end{bmatrix}

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:

$egin\{matrix\}12\; 12\; 123\; 124\backslash end\{matrix\}$

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:

$egin\{matrix\}1\; 2\; 1234\; 4\backslash end\{matrix\}$

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 proved 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.

**Latin squares and mathematical puzzles**The problem of determining if a partially filled square can be completed to form a Latin square is

NP-complete . [*cite journal | author = C. 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*]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 3×3 subgroups must also contain the digits 1–9 (in the standard version).

Heraldry The Latin square also figures in the blazon of the arms of the

Statistical Society of Canada . [*http://www.ssc.ca/main/about/history/arms_e.html*] Also, it appears in the logo of theInternational Biometric Society . [*http://www.tibs.org*]**ee also***

Latin hypercube sampling

*Graeco-Latin square

*Magic Square

*Problems in Latin squares

*Small Latin squares and quasigroups

*Sudoku

*Futoshiki

*Rook's graph , a graph that has Latin squares as its colorings.

*Eight queens puzzle **References****External links*** [

*http://www.cut-the-knot.org/Curriculum/Algebra/Latin.shtml Latin Squares in Java*] atcut-the-knot

* [*http://www.cut-the-knot.org/Curriculum/Combinatorics/InfiniteLatinSquare.shtml Infinite Latin Square (Java)*] atcut-the-knot

* [*http://www.muljadi.org/MagicSudoku.htm Magic Square in Latin Square*]

*Wikimedia Foundation.
2010.*