E    
  D  
    T

Encyclopaedia of DesignTheory: Latin squares

General Partition Incidence Array
Experimental Other designs Math properties Stat properties
Server External Bibliography Miscellanea

Mathematical properties of Latin squares

Classification

The classification of Latin squares up to isomorphism depends on the definition of isomorphism that we use. We assume below that the set of symbols is the same as the set of row and column indices, that is, {1,2,...,n}.

Two Latin squares are said to be isotopic if one can be obtained from the other by permuting rows, columns and symbols. The equivalence classes of this relation are called isotopy classes.

Given a Latin square, we obtain five other Latin squares from it by permuting the roles of rows, columns, and symbols. More precisely, represent the square by a n2 × 3 orthogonal array, which has a row (i,j,k) if the symbol in row i and column j of the square is k. The other five squares correspond to the arrays obtained by permuting the columns of this one. The equivalence classes of this relation are called the main classes.

There are several other notions of equivalence of Latin squares: see the topic essay for further discussion.

Brendan McKay has lists of representatives of the isotopy classes and main classes of Latin squares of order up to 8. Subsequently, McKay, Meynert and Myrvold computed the numbers up to 10; their results are in the following table.

Order2345 678 910
Isotopy classes1122 225641676267 115618721533208904371354363006
Main classes1122 12147283657 1927085354134817397894749939

The number of Latin squares of order n is roughly (cn)n². This number is of a greater order of magnitude than the number of isomorphisms, so the estimate is little affected by counting up to some notion of isomorphism.

Automorphisms

An automorphism is an isomorphism from a Latin square to itself. The automorphisms of a Latin square form a group.

Of course, the question "what is an automorphism" cannot be answered until we say when we are regarding two Latin squares as being equivalent; the aforementioned topic essay addresses this point. In what follows here, an automorphism is a main class equivalence from a Latin square to itself.

McKay and Wanless have shown that, for almost all Latin squares, the automorphism group consists only of the identity map.

On the other hand, Latin squares with the highest degree of symmetry have been determined by Bailey.

Partial Latin squares

A partial Latin square of order n is an n × n array in which each cell either contains a symbol from the set {1,2,...,n} or is blank, so that each symbol occurs at most once in each row or column. It can be completed to a Latin square if it is possible to place symbols in the blank cells so as to produce a Latin square.

A Latin rectangle is a partial Latin square whose non-blank cells are those in the first k rows, for some k.

The main results are:

  1. Any Latin rectangle can be completed. (This is a simple deduction from Hall's marriage theorem.)
  2. (Ryser) Any partial Latin square of order n, all of whose non-blank cells lie in some set of s rows and t columns, where s+t <= n, can be completed.
  3. (Smetaniuk; Andersen and Hilton) Any partial Latin square of order n with at most n-1 non-blank cells can be completed. (This establishes the Evans conjecture.)

Transversals

A transversal to a Latin square of order n is a set of n cells with the property that one cell lies in each row, one in each column, and one contains each symbol.

A Latin square has an orthogonal mate if and only if it possesses a set of n transversals which partition the n2 cells of the square. (If such a set of transversals exist, associate one new symbol with each transversal in the set and place it in the cells belonging to that transversal; the result is a Latin square orthogonal to the original one.)

A partial transversal is a set of cells with at most one in each row or column or containing any symbol.

Two important conjectures about transversals which are still open are:

Permutations

The rows of a Latin square of ordern can be regarded as a set of n permutations of {1,...,n}. This set is sharply transitive; that is, given any two symbols i and j, there is a unique permutation in the set carrying i to j. Conversely, any sharply transitive set of permutations is the set of rows of a Latin square.

Any two of these permutations agree in no positions. The maximum size of a set of permutations with this property is n, and equality is attained precisely by the set of rows of a Latin square.

Because of this, Latin squares played an important role in the characterisation of sets of permutations with the property that any two agree in at least one position, which attain the upper bound (n-1)! for the cardinality of such sets, by Cameron and Ku.

The property can also be expressed group-theoretically. A set of permutations forms the set of rows of a Latin square if and only if it is simultaneously a transversal for the right cosets (and for the left cosets) of each point stabiliser in the symmetric group.

In connection with this, we mention a theorem of Philip Hall. If H is a subgroup of a finite group G, then there is a set of elements which is a transversal for the right cosets of H, and also for the left cosets of H. The proof was the first application of his famous marriage theorem.

Table of contents | Glossary | Topics | Bibliography | History

Peter J. Cameron
5 July 2006