Latin square

A Latin square is a square pattern with n rows and n columns, where each field is assigned a different n symbols so that each symbol in each row and each column in each case occurs exactly once. The natural number n is called the order of the Latin square.

As symbols, the numbers from 1 to n, n different letters or n different colors are often used. The mathematician Leonhard Euler worked intensively with such squares; as a set of symbols he used the Latin alphabet. The name Latin square goes back to it.

In modern combinatorial and discrete mathematics as symbol set mainly by the numbers from 1 to n, the numbers from 0 to less frequently used, and the pattern is seen as a specific matrix.

Each Latin square can be interpreted as a truth table ( Cailey panel ) of a finite quasigroup, conversely determined every finite quasigroup an equivalence class of Latin squares.

Two different Latin squares of the same order n can be orthogonal to each other. In the synthetic geometry of certain quantities of pairwise orthogonal Latin squares of order n finite affine planes are assigned. As a result there is a necessary and sufficient combinatorial condition for the existence of levels of order n: such a level exists if and only if there is a complete list of mutually orthogonal squares of order n.

Outside mathematics in the strict sense Latin squares are employed inter alia in the statistical design of experiments.

2.1 Algebra: Latin squares and linking tables
2.2 Geometry: Orthogonal Latin squares and finite levels 2.2.1 Construction of orthogonal Latin squares of Ternärkörpern

3.1 Parastrophie
3.2 isotopy
3.3 Main classes

Preparation, properties, and concepts

View as matrix

A Latin square of order n is a square matrix, whose entries are all natural numbers from 1 to n, in such a way that, in each row and each column of the matrix, each of the numbers occurs once. This property can be in a matrix (for example, a computer algebra system like Maple ) test as follows: For the entries of the matrix M, the following equations must be satisfied:

Needs and for each row
Must apply for each column.

Tripeldarstellung: OAR

A Latin square of order n can also be represented as a set of different triples. Where r is the number of a row ( "row" ) in the Latin square, s. For the number of a column and z for there standing in the square number The rule for Latin squares is exactly fulfilled if no two of the triples match in two entries. This representation is called the orthogonal array representation ( OAR ) of the Latin square.

The OAR suggests a geometric interpretation of a Latin square: one, the number in a cell of the Latin square interpreted as height of a cuboid, which is to be built on this cell as a base. This is from the Latin square a spatial column chart - compare the picture to the example below!

In the picture also a related interpretation of the Latin square of order n to realize: If you fill from the columns in the column chart in each case only the cube at the top, then one a three dimensional image of axis-parallel unit cubes obtained in a larger axis-parallel cube with an edge length n. the partial cubes with the grid coordinates is exactly then " filled " when one of the OAR of the Latin square. An array of sub- cubes in such a cube of side length n if and only belongs to a Latin square of order n if the cubes considered in the three axis-parallel directions through the partial cube is opaque, so filled gaps when projecting in an axial direction appears.

This interpretation makes clear that the OAR of a Latin square, not only in interchanging the row with the column numbers ( a transposition in the matrix representation ) for OAR of a Latin square is, but even if all the characters numbers are swapped with the row numbers or column numbers!

The example in the figure to the right shows the first Latin square C below, the second, D, arises from the fact by the r- swapped with the z- axis. If the S- exchanged with the first square of the z-axis, C, D is also formed the square, because the matrix is symmetrical.

The loud Tripeldarstellungen

Number of Latin squares

The numbers of Latin squares of order, form sequence A002860 in OEIS. There is no known easy to calculate the formula for the sequence. The best known lower and upper bounds for large orders n are far apart. A classical estimate is:

Reduced Latin squares

A Latin square is called reduced or normalized when standing in the first row and the first column of n different symbols in their "natural order ". In the Tripeldarstellung with numbers as symbols that means for the first row and the first column. Normalizing any Latin square can always be achieved by permutations of columns and rows. The square of order 3 in the examples below is normalized by swapping the second to the third line, the square of order 4 is already reduced.

The numbers of reduced Latin squares of order form sequence A000315 in OEIS. For the total number of Latin squares

Examples

Latin squares of order 3 or 4 in the matrix representation:

The Tripeldarstellung of the left square is:. If you were to swap there in the first line the numbers 1 and 2, the triple ( first row, first column contains 2) would and the triple ( 3rd row, 1st column contains 2) at two locations (column and mark ) match and the square would not be a Latin square more.

It can easily be a Latin square for any given order specify: These distributed to different symbols anywhere on the first row of the square. The following rows of successively filling now, by adopting shifted by one to the right, the respective preceding row. The rightmost symbol of the previous row would thereby fall out of the square; Instead, you wear it in the new series very left.

The example of the order 3 is constructed in this way, in the example of order 4, instead of the shift to the right cyclically permuted left in each row. If you start in this construction, as in the example shown with a sorted first line with the numbers, then one always obtains a reduced Latin square, which can be interpreted as linking Table of the residue class group. For this, the registered numbers must all be reduced by 1.

Orthogonal Latin squares and MOLS

Two Latin squares and are called orthogonal if no two match of the pairs that arise when one writes the entries to and from each side by side in a new square pattern. In matrix representation:

The combined here with the matrix and Latin squares are orthogonal. In this case we call the square represented by a Greek- Latin square. The numbers of pairs of orthogonal Latin squares of order form sequence A072377 in OEIS.

For use in geometry, the following sentence is important:

A list of pairwise orthogonal Latin squares of order n is said to be complete. The result of the maximum numbers of pairwise orthogonal Latin squares ( MOLS = mutually orthogonal Latin squares ) of order n is A001438 in OEIS sequence, what is known about the values to the table on the right shows the values for 0 and 1 are convention. The following applies:

If and, then, for a list of pairwise orthogonal Latin squares can always complete.
For is, for
If p is a prime and, then.
It is still not known whether there exists a natural number n which is not a prime power and applies.
For sufficiently large n, so is.
It is forever, for n from a list of t MOLS of order and a list of t MOLS of order m can be prepared a list of t MOLS of order always. The method is demonstrated here on a trivial example:

Magic Squares

After its construction, the order are in a Greco-Latin square n if you recoded the pairs of numbers in an appropriate manner bijective to consecutive natural numbers - for example - all row sums and row sums equal to, for example, can be the square S as the square

Assign, in which each row and each column has the magic sum.

If in such a square in addition, the sum of the two diagonals is equal to the row and column sum, then one speaks of a magic square.

Applications

Algebra: Latin squares and linking tables

The first figure on the left shows the complete truth table of the group:

In the middle matrix were the row and column headings, ie with " " associated group elements are omitted, thus, this matrix is a Latin square with the symbol set that is common for residue classes, dar. If we add to each entry 1, the result is a Latin square with the default symbol set. Here this Latin square is normalized because the group members of the group for the link table in their "natural order" were arranged as multiples of the generating element 1 and this group is cyclic.

It must be noted that, for the elements of a group or quasi- group is generally no specific arrangement can be distinguished: If the symmetric group on n elements, then by a permutation, the succession to the rows and columns of the join table (including its ranks - or column headings ) is applied, from the original table (left) another valid link table the same group, while also associated with the group Latin square changes (right).

Formal and generally applies: If a Latin square of order n in the matrix representation, then there exists a quasigroup with n elements - the matrix has as its content link table - with a suitable arrangement and numbering of its elements. Exactly the Latin squares that emerge through a similar row and column permutation and a " renumbering " for which so applies, can be considered as a shortcut tables in this quasigroup.

If you choose the arrangement of the elements of a finite loop, that is a quasigroup with both left -and right- neutral element, so that the first element occurs in the truth table and assigns the elements in their otherwise arbitrary arrangement of the order, the numbers, then is the content of their truth table, written with the associated natural numbers, a reduced Latin square of order. ( The number represents the number of elements ).
A quasigroup which has the Latin square of order n as the content of its truth table is exactly then commutative, if the matrix is symmetric, ie, if applies. In a commutative quasigroup can always be chosen a numbering of the elements through which the contents of the multiplication table is a reduced Latin square. It should be noted that here only the first line of the square can be brought into conformity with the column headings of the truth table - and thus also the first column containing the row headers - if the quasigroup is a loop.

Geometry: Orthogonal Latin squares and finite levels

For a complete list of pairwise orthogonal Latin squares of order n is a finite affine plane of order n can be constructed and vice versa. This procedure is followed:

The set of points is comprised of the pairs of natural numbers from 1 to n:

Each Latin square determines a parallel class level:
The parallel class consists of the straight line

There are also two " axis directions ", and with the straight line

The line set is the union of the so-defined parallel multitudes.

Conversely, it is in a finite affine plane of order n choose an affine coordinate system and the points on the first axis, ie the Ternärkörperelementen a - down to the archetype n the origin O any - assign bijection numbers as " combinatorial coordinates " so that

This one has a unique pair of numbers for each point in the plane of the point related to the base coordinate representation. Each of the parallel hosts in addition to the two groups in parallel to the axes so determined as described above, a Latin square, and the squares are thus determined pairwise orthogonal. In terms of the - also by the orthogonal Latin squares certain list - Ternärverknüpfung T are straight lines then the linear equations:

Because every finite affine plane of order has a projective plane of the same order as the projective completion and every finite projective plane can be slotted so that a finite affine plane of the same order is created, the following applies:

When carrying out the construction of a non-exhaustive list of m MOLS described herein, to obtain a structure with n incidence points on each straight line and parallel flocking, ie a so-called network.

Construction of orthogonal Latin squares of Ternärkörpern

Is a finite Ternärkörper, then K is for each by linking to a quasigroup. With the same arrangement of the elements of K for the multiplication tables, the Latin squares are two such linkages at different factors always orthogonal to each other. Thus obtained by a Ternärkörper of order n always a complete list of pairwise orthogonal Latin squares.

The residue field is a Ternärkörper. The contents of the multiplication tables for the quasigroup links described above - since K is a body that applies here - are:

It must be replaced by 0 5 For the standard notation, one has thus generates a set of four mutually orthogonal Latin squares. Analog can be determined always mutually orthogonal Latin squares for each prime power over the corresponding quasigroup links in the finite field.

Each of these Latin squares then describes the incidence relation in one of the parallel bands of the affine plane as shown in the previous section.

Mathematical Puzzles

The question of whether a partially filled square can be completed to a Latin square design, is an NP -complete problem in the language of complexity theory.
A Latin square of order 9 with the additional condition that all symbols occur in each of the division into nine squares in each of these squares exactly once, leading to the number puzzle Sudoku.

Equivalence classes of Latin squares

Through many different transformations that can be applied to a Latin square, one obtains a new Latin square:

The transformations mentioned in 4 are special cases of the row and column permutations.

For the application important and useful for counting the possible Latin squares of a fixed order, the amounts of transformations described below, through which a respective Äquivalenklasseneinteilung on the set of Latin squares of order n is introduced ( with symbols from ).

Parastrophie

Two Latin squares are called to each other parastroph when they emerge in the OAR than triples by a permutation apart when so true. For example, exchanging the row number and the column number, and thus corresponds to the matrix representation of the transposition. Each class of each para disasters Latin squares containing 1,2,3 or 6 different Latin squares, this is a consequence of the path formula. See also quasigroup # Parastrophien.

Isotopy

Two Latin squares are called isotopic to each other when they emerge apart by a combination of row, column permutations and bijective renaming the entries. The numbers of Isotopieklassen of Latin squares of order n form sequence A040082 in OEIS. See also quasigroup # morphisms.

Main classes

By combining the equivalence relations Parastrophie and isotopy, one arrives at a new equivalence class division, the division into the main classes called. Two Latin squares belong to the same main class if they can be transformed by a combination of Parastrophie and Isotopieoperationen each other. In each major class contained 1,2,3 or 6 Isotopieklassen. The numbers of the main classes of Latin squares of order n form sequence A003090 in OEIS.

Affine plane (incidence geometry) Graeco-Latin square Cyclic group Symmetric matrix Charles Colbourn Digital Object Identifier Jack van Lint Donald Knuth Wolfram Research Michiel Hazewinkel Encyclopedia of Mathematics

500356