Encyclopaedia of DesignTheory: Latin squares
|Experimental||Other designs||Math properties||Stat properties|
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.
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.
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.
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:
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:
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