Admin: Created page with " In combinatorics and in experimental design, a '''Latin square''' is an&nb..."

2019-06-08T13:52:46Z

Created page with "<amp/> In combinatorics and in experimental design, a '''Latin square''' is an&nb..."

New page

<amp/>
In [[combinatorics]] and in [[design of experiments|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 3x3 Latin square is:

{| class="wikitable" style="margin-left:auto;margin-right:auto;text-align:center;width:6em;height:6em;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, 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.

== 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 [[Permute|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:6em;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 following Latin square is:

{| class="wikitable" style="margin-left:auto;margin-right:auto;text-align:center;width:6em;height:6em;table-layout:fixed;"
|-
| 1|| 2 || 3
|-
| 2 || 3 || 1
|-
| 3 || 1 || 2
|}

: { (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:
* A Latin square is the set of all 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.

For any Latin square, there are ''n''<sup>2</sup> triples since choosing any two uniquely determines the third. (Otherwise, an ordered pair would appear more than once in the Latin square.)

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 ''[[Quasigroup#Homotopy and isotopy|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 [[paratopy|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 class]]es, ''species'', or [[paratopy|paratopy classes]]. Each main class contains up to 6 isotopy classes.

===Number===

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
:<math> \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 of Latin squares is,

<math> L_n = n! \sum_{A \in B_n}^{} (-1)^{\sigma_0 (A)} (^{per A} _{\ \ n}),</math>

where is the set of all {0,1} matrices, is the number of zero entries in matrix , and per() 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 .

{| border="1" cellpadding="5" cellspacing="0" align="center" class="wikitable"
|+ The numbers of Latin squares of various sizes
! ||align=right| reduced Latin squares of size ||align=right| all Latin squares of size
|-
|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
|}

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.

{| border="1" cellpadding="5" cellspacing="0" align="center" class="wikitable"
|+ Equivalence classes of Latin squares
! ||align=right| main classes ||align=right| isotopy classes
|-
|align=right| 1 ||align=right| 1 ||align=right| 1
|-
|align=right| 2 ||align=right| 1 ||align=right| 1
|-
|align=right| 3 ||align=right| 1 ||align=right| 1
|-
|align=right| 4 ||align=right| 2 ||align=right| 2
|-
|align=right| 5 ||align=right| 2 ||align=right| 2
|-
|align=right| 6 ||align=right| 12 ||align=right| 22
|-
|align=right| 7 ||align=right| 147 ||align=right| 564
|-
|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, reflexion, and/or permutation of the symbols) for = 1 up to 6 is 1, 1, 1, 12, 192, 145164 respectively .

===Examples===
We give one example of a Latin square from each main class up to order 5.

<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></center>

<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></center>

<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></center>

They present, respectively, the multiplication tables of the following groups:
*{0} – the trivial 1-element group
*<math>\mathbb{Z}_2</math> – the [[Binary numeral system|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 (algebra)|loop]], which is not associative.


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

==Applications==

===Statistics and mathematics===
*In the [[design of experiments]], Latin squares are a special case of '''''row-column''''' '''designs''' for two [[blocking (statistics)|blocking factors]]: Many row-column designs are constructed by concatenating Latin squares.
*In [[algebra]], Latin squares are generalizations of [[group theory|groups]]; in fact, Latin squares are characterized as being the [[multiplication table]]s ([[Cayley table]]s) of [[quasigroup]]s. 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.

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.

<center><math>
\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></center>

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>\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>\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===

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

The popular [[Mathematics of Sudoku|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). 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

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

==Source==

[http://wikipedia.org/ http://wikipedia.org/]

[[Category:Error-correcting codes]]
==See Also on BitcoinWiki==
* [[Depository Network]]
* [[Yumerium]]
* [[Ink Labs Foundation]]
* [[IZX]]
* [[Let It Play]]

Latin square - Revision history

Admin: Created page with " In combinatorics and in experimental design, a '''Latin square''' is an&nb..."