Latin square

An example of a 3×3 Latin square is The name "Latin square" was inspired by mathematical papers by Leonhard Euler (1707–1783), who used Latin characters as symbols,[2] 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.

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.

[4] 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: This Latin square is reduced; both its first row and its first column are alphabetically ordered A, B, C. 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.

The orthogonal array representation shows that rows, columns and symbols play rather similar roles, as will be made clear below.

Another type of operation is easiest to explain using the orthogonal array representation of the Latin square.

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.

For each n, the number of Latin squares altogether (sequence A002860 in the OEIS) is n!

times the number of reduced Latin squares (sequence A000315 in the OEIS).

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

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.

Therefore, many results on Latin squares/rectangles are contained in papers with the term "rainbow matching" in their title, and vice versa.

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.

In 1967, H. J. Ryser conjectured that, when n is odd, every n-by-n Latin square has a transversal.

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

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

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

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.

Similarly, we may imagine a burst of static over all frequencies in the third slot:

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.

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 and Strimko puzzles are also examples of Latin squares.

Latin squares are used in the design of agronomic research experiments to minimise experimental errors.

[23] The Latin square also figures in the arms of the Statistical Society of Canada,[24] being specifically mentioned in its blazon.