Small Latin squares and quasigroups

From HandWiki

Latin squares and quasigroups are equivalent mathematical objects, although the former has a combinatorial nature while the latter is more algebraic. The listing below will consider the examples of some very small orders, which is the side length of the square, or the number of elements in the equivalent quasigroup.

The equivalence

Given a quasigroup Q with n elements, its Cayley table (almost universally called its multiplication table) is an (n + 1) × (n + 1) table that includes borders; a top row of column headers and a left column of row headers. Removing the borders leaves an n × n array that is a Latin square. This process can be reversed, starting with a Latin square, introduce a bordering row and column to obtain the multiplication table of a quasigroup. While there is complete arbitrariness in how this bordering is done, the quasigroups obtained by different choices are sometimes equivalent in the sense given below.

Isotopy and isomorphism

Two Latin squares, L1 and L2 of size n are isotopic if there are three bijections from the rows, columns and symbols of L1 onto the rows, columns and symbols of L2, respectively, that map L1 to L2.[1] Isotopy is an equivalence relation and the equivalence classes are called isotopy classes.

A stronger form of equivalence exists. Two Latin squares, L1 and L2 of side n with common symbol set S that is also the index set for the rows and columns of each square, are isomorphic if there is a bijection g:S → S such that g(L1(i, j)) = L2(g(i), g(j)) for all i, j in S.[1] An alternate way to define isomorphic Latin squares is to say that a pair of isotopic Latin squares are isomorphic if the three bijections used to show that they are isotopic are, in fact, equal.[2] Isomorphism is also an equivalence relation and its equivalence classes are called isomorphism classes.

An alternate representation of a Latin square is given by an orthogonal array. For a Latin square of order n this is an n2 × 3 matrix with columns labeled r, c and s and whose rows correspond to a single position of the Latin square, namely, the row of the position, the column of the position and the symbol in the position. Thus for the order three Latin square,

1 2 3
2 3 1
3 1 2

the orthogonal array is given by:

r c s
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

The condition for an appropriately sized matrix to represent a Latin square is that for any two columns the n2 ordered pairs determined by the rows in those columns are all the pairs (i, j) with 1 ≤ i, j ≤ n, once each.

This property is not lost by permuting the three columns (but not the labels), so another orthogonal array (and thus, another Latin square) is obtained. For example, by permuting the first two columns, which corresponds to transposing the square (reflecting about its main diagonal) gives another Latin square, which may or may not be isotopic to the original. In this case, if the quasigroup corresponding to this Latin square satisfies the commutative law, the new Latin square is the same as the original one. Altogether there are six possibilities including "do nothing", giving at most six Latin squares called the conjugates (also parastrophes) of the original square.[3]

Two Latin squares are said to be paratopic, also main class isotopic, if one of them is isotopic to a conjugate of the other. This is also an equivalence relation, with the equivalence classes called main classes, species, or paratopy classes.[3] Each main class contains up to six isotopy classes.

A main class is a disjoint union of isotopy classes and an isotopy class is a disjoint union of isomorphism classes.[4]

Isotopic quasigroups

Let (Q,∘) and (R,∗) be two quasigroups. An ordered triple (f,g,h) of bijections from Q onto R is called an isotopism of (Q,∘) onto (R,∗) if f(x) ∗ g(y) = h(x ∘ y) for all x, y in G. Such quasigroups are said to be isotopic.[5]

If in the above definition f = g = h then the quasigroups are said to be isomorphic.[2]

Unlike the situation with Latin squares, when two isotopic quasigroups are represented by Cayley tables (bordered Latin squares), the permutations f and g operate only on the border headings and do not move columns and rows, while h operates on the body of the table.[5]

Permuting the rows and columns of a Cayley table (including the headings) does not change the quasigroup it defines, however, the Latin square associated with this table will be permuted to an isotopic Latin square. Thus, normalizing a Cayley table (putting the border headings in some fixed predetermined order by permuting rows and columns including the headings) preserves the isotopy class of the associated Latin square. Furthermore, if two normalized Cayley tables represent isomorphic quasigroups then their associated Latin squares are also isomorphic. Hence, the number of distinct quasigroups of a given order is the number of isomorphism classes of Latin squares of that order.[6]

Notation

The set of symbols used in a Latin square (or quasigroup) is arbitrary and individual symbols carry no meaning, even if they may have a meaning in other contexts. Thus, since it is most common to see the symbol sets {1,2, ... , n} or {0,1, ... , n − 1} used, one must remember that these symbols carry no numerical meaning. To stress this point, small Latin squares sometimes use letters of the alphabet as a symbol set.

Counting Latin squares

As a Latin square is a combinatorial object, the symbol set used to write the square is immaterial. Thus, as Latin squares, these should be considered the same:

[math]\displaystyle{ \begin{matrix} a & b \\ b & a \end{matrix} }[/math]   and   [math]\displaystyle{ \begin{matrix} 1 & 2 \\ 2 &1 \end{matrix}. }[/math]

Similarly, and for the same reason,

[math]\displaystyle{ \begin{matrix} b & a \\ a & b \end{matrix} }[/math]   and   [math]\displaystyle{ \begin{matrix} 1 & 2 \\ 2 &1 \end{matrix} }[/math]

should be thought of as the same. Thus,

[math]\displaystyle{ \begin{matrix} a & b \\ b & a \end{matrix} }[/math]   and   [math]\displaystyle{ \begin{matrix} b & a \\ a &b \end{matrix} }[/math]

can not be thought of as different Latin squares.

This intuitive argument can be made more precise. The Latin squares

[math]\displaystyle{ \begin{matrix} a & b \\ b & a \end{matrix} }[/math]   and   [math]\displaystyle{ \begin{matrix} b & a \\ a &b \end{matrix}, }[/math]

are isotopic, in several ways. Let (a,b) be the involutorial permutation on the set S = {a,b}, sending a to b and b to a. Then the isotopy {(a,b), id, id} will interchange the two rows of the first square to give the second square (id is the identity permutation). But, {id, (a,b), id} which interchanges the two columns is also an isotopy, as is {id, id, (a,b)} which interchanges the two symbols. However, {(a,b), (a,b), (a,b)} is also an isotopy between the two squares, and so, this pair of squares are isomorphic.

Reduced squares

Finding a given Latin square's isomorphism class can be a difficult computational problem for squares of large order. To reduce the problem somewhat, a Latin square can always be put into a standard form known as a reduced square. A reduced square has its top row elements written in some natural order for the symbol set (for example, integers in increasing order or letters in alphabetical order). The left column entries are put in the same order. As this can be done by row and column permutations, every Latin square is isotopic to a reduced square. Thus, every isotopy class must contain a reduced Latin square, however, a Latin square may have more than one reduced square that is isotopic to it. In fact, there may be more than one reduced square in a given isomorphism class.[7]

For example, the reduced Latin squares of order four,

[math]\displaystyle{ \begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \\ 3 & 1 &4&2\\4&3&2&1 \end{matrix} }[/math]   and   [math]\displaystyle{ \begin{matrix} 1 & 2 &3&4\\ 2 &1&4&3\\3&4&2&1\\4&3&1&2 \end{matrix} }[/math]

are both in the isomorphism class that also contains the reduced square

[math]\displaystyle{ \begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ 3 & 4 &1&2\\4&1&2&3 \end{matrix}. }[/math]

This can be shown by the isomorphisms {(3,4), (3,4), (3,4)} and {(2,3), (2,3), (2,3)} respectively.[8]

Since isotopy classes are disjoint, the number of reduced Latin squares gives an upper bound on the number of isotopy classes. Also, the total number of Latin squares is n!(n − 1)! times the number of reduced squares.[9]

One can normalize a Cayley table of a quasigroup in the same manner as a reduced Latin square. Then the quasigroup associated to a reduced Latin square has a (two sided) identity element (namely, the first element among the row headers). A quasigroup with a two sided identity is called a loop. Some, but not all, loops are groups. To be a group, the associative law must also hold.

Isotopy invariants

The counts of various substructures in a Latin square can be useful in distinguishing them from one another. Some of these counts are the same for every isotope of a Latin square and are referred to as isotopy invariants. One such invariant is the number of 2 × 2 subsquares, called intercalates. Another is the total number of transversals, a set of n positions in a Latin square of order n, one in each row and one in each column, that contain no element twice. Latin squares with different values for these counts must lie in different isotopy classes. The number of intercalates is also a main class invariant.

Order 1

For order one there is only one Latin square with symbol 1 and one quasigroup with underlying set {1}; it is a group, the trivial group.

Order 2

There is only one reduced Latin square of order two (and only two in total), namely

[math]\displaystyle{ \begin{matrix} 1 & 2 \\ 2 & 1 \end{matrix}. }[/math]

Since there is only one reduced square of this order, there is only one isotopy class. In fact, this isotopy class is also an isomorphism class (shown above).[8][1]

As there is only one isomorphism class of Latin squares, there is only one quasigroup of order two (up to isomorphism) and it is the group usually denoted by ℤ/2ℤ, the cyclic group of order two.

Order 3

There is also only one reduced Latin square of order three (out of 12),

[math]\displaystyle{ \begin{matrix} 1 & 2 & 3 \\ 2 & 3 &1 \\3&1&2 \end{matrix}. }[/math]

Thus, there is only one isotopy class.[8] However, this isotopy class is the union of five isomorphism classes.[1]

Three of the five isomorphism classes contain three Latin squares each, one contains two and one contains just one. The reduced square is in an isomorphism class with three elements and so the corresponding quasigroup is a loop, in fact it is a group, ℤ/3ℤ, the cyclic group of order three. A Latin square representative of each of these isomorphism classes is given by (the number below each is the number of squares in the corresponding isomorphism class):

[math]\displaystyle{ \begin{matrix} 1 & 2 & 3 \\ 2 & 3 &1 \\3&1&2 \\ &(3)& \end{matrix}\qquad\qquad\begin{matrix} 2 & 3 & 1 \\ 1 & 2 &3 \\3&1&2\\ &(3)& \end{matrix}\qquad\qquad\begin{matrix} 2 & 1 & 3 \\ 3 & 2 &1 \\1&3&2\\ &(3) \end{matrix}\qquad\qquad\begin{matrix} 3 & 2 & 1 \\ 2 & 1 &3 \\1&3&2 \\ &(2)& \end{matrix}\qquad\qquad\begin{matrix} 1 & 3 & 2 \\ 3 & 2 &1 \\2&1&3\\ &(1)& \end{matrix}. }[/math]

Order 4

There are four reduced Latin squares of order four (out of 576 squares). These are:

[math]\displaystyle{ \begin{matrix} 1 & 2 & 3 &4 \\ 2 & 1 &4 &3\\3&4&1&2 \\ 4&3&2&1 \end{matrix}\qquad\begin{matrix} 1 & 2 &3&4\\ 2 &1&4&3\\3&4&2&1\\4&3&1&2 \end{matrix}\qquad\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ 3 & 4 &1&2\\4&1&2&3 \end{matrix}\qquad\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \\ 3 & 1 &4&2\\4&3&2&1 \end{matrix}. }[/math]

The last three of these are isomorphic (see above). There are two main classes, two isotopy classes and 35 isomorphism classes. Among the 35 quasigroups, only two are loops, and they are in fact groups. Corresponding to the first square above is the Klein four group, while corresponding to any of other three squares is the cyclic group ℤ/4ℤ. The first square has eight transversals and 12 intercalates, while each of the others have no transversals and four intercalates.

The isomorphism class of the Klein four group has four members, while the isomorphism class of the cyclic group has 12 members. Of the 576 Latin squares, 288 are solutions of the 4×4 version of Sudoku, sometimes called Shi Doku [1].

Order 5

Of the 161,280 Latin squares of order five, there are 56 reduced squares. There are two main classes and only two isotopy classes, but 1,411 isomorphism classes. There are six isomorphism classes that contain reduced squares, that is, there are six loops, only one of which is a group, the cyclic group of order five.[1]

Below are two reduced Latin squares of order five, one from each isotopy class.[10]

[math]\displaystyle{ \begin{matrix} 0&1&2&3&4 \\1&2&3&4&0\\2&3&4&0&1 \\ 3&4&0&1&2 \\4&0&1&2&3 \end{matrix}\qquad\qquad\begin{matrix} 0&1&2&3&4\\ 1&0&3&4&2\\2&3&4&0&1\\3&4&1&2&0 \\4&2&0&1&3 \end{matrix} }[/math]

The first square has 15 transversals, no intercalates and is the unbordered Cayley table of the cyclic group ℤ/5ℤ. The second square has three transversals and four intercalates. It represents a loop that is not a group, since, for instance, 2 + (3 + 4) = 2 + 0 = 2, while (2 + 3) + 4 = 0 + 4 = 4, so the associative law does not hold.

Orders 6 to 10

The number of Latin squares, as the order increases, exhibits the phenomenon known as combinatorial explosion; for even small increases in size there correspond huge increases in varieties. The basic counts are given in the next two tables,[1] and not much beyond what is presented here is known with exactness.

Number of isotopy classes of Latin squares and Quasigroups (isomorphism classes)
n main classes isotopy classes isomorphism classes
6 12 22 1,130,531
7 147 564 12,198,455,835
8 283,657 1,676,267 2,697,818,331,680,661
9 19,270,853,541 115,618,721,533 15,224,734,061,438,247,321,497
10 34,817,397,894,749,939 208,904,371,354,363,006 2,750,892,211,809,150,446,995,735,533,513
The numbers of reduced Latin squares and loops of various sizes
n reduced Latin squares of size n loops of size n
6 9,408 109
7 16,942,080 23,746
8 535,281,401,856 106,228,849
9 377,597,570,964,258,816 9,365,022,303,540
10 7,580,721,483,160,132,811,489,280 20,890,436,195,945,769,617

History

This account follows (McKay Meynert).

The counting of Latin squares has a long history, but the published accounts contain many errors. Euler in 1782,[11] and Cayley in 1890,[12] both knew the number of reduced Latin squares up to order five. In 1915, MacMahon[13] approached the problem in a different way, but initially obtained the wrong value for order five. M.Frolov in 1890,[14] and Tarry in 1901,[15][16] found the number of reduced squares of order six. M. Frolov gave an incorrect count of reduced squares of order seven. R.A. Fisher and F. Yates,[17] unaware of earlier work of E. Schönhardt,[18] gave the number of isotopy classes of orders up to six. In 1939, H. W. Norton found 562 isotopy classes of order seven,[19] but acknowledged that his method was incomplete. A. Sade, in 1951,[20] but privately published earlier in 1948, and P. N. Saxena[21] found more classes and, in 1966, D. A. Preece noted that this corrected Norton's result to 564 isotopy classes.[22] However, in 1968, J. W. Brown announced an incorrect value of 563,[23] which has often been repeated. He also gave the wrong number of isotopy classes of order eight. The correct number of reduced squares of order eight had already been found by M. B. Wells in 1967,[24] and the numbers of isotopy classes, in 1990, by G. Kolesova, C.W.H. Lam and L. Thiel.[25] The number of reduced squares for order nine was obtained by S. E. Bammel and J. Rothstein,[26] for order 10 by B. D. McKay and E. Rogoyski,[27] and for order 11 by B. D. McKay and I. M. Wanless.[28]

See also

Notes

  1. ↑ 1.0 1.1 1.2 1.3 1.4 1.5 Colbourn & Dinitz 2007, p. 136
  2. ↑ 2.0 2.1 Dénes & Keedwell 1974, p. 24
  3. ↑ 3.0 3.1 Dénes & Keedwell 1974, p. 126
  4. ↑ Dénes & Keedwell 1974, pp. 127-8
  5. ↑ 5.0 5.1 Dénes & Keedwell 1974, p. 23
  6. ↑ McKay, Meynert & Myrvold 2007, p. 105
  7. ↑ Dénes & Keedwell 1974, p. 128
  8. ↑ 8.0 8.1 8.2 Dénes & Keedwell 1974, p. 129
  9. ↑ McKay, Meynert & Myrvold 2007, p. 100
  10. ↑ Colbourn & Dinitz 2007, p. 137
  11. ↑ Euler, L. (1782), "Recherches sur une nouvelle espèce de quarrés magiques", Verhandelingen/Uitgegeven Door Het Zeeuwsch Genootschap der Wetenschappen te Vlissingen (9): 85–239 
  12. ↑ Cayley, A. (1890), "On Latin Squares", Oxford Camb. Dublin Messenger of Math. 19: 85–239 
  13. ↑ MacMahon, P.A. (1915), Combinatory Analysis, Cambridge University Press, pp. 300 
  14. ↑ Frolov, M. (1890), "Sur les permutations carrées", J. De Math. Spéc. IV: 8–11, 25–30 
  15. ↑ Tarry, Gaston (1900). "Le Probléme de 36 Officiers". Compte Rendu de l'Association Française pour l'Avancement des Sciences (Secrétariat de l'Association) 1: 122–123. 
  16. ↑ Tarry, Gaston (1901). "Le Probléme de 36 Officiers". Compte Rendu de l'Association Française pour l'Avancement des Sciences (Secrétariat de l'Association) 2: 170–203. 
  17. ↑ Fisher, R.A.; Yates, F. (1934), "The 6 × 6 Latin squares", Proc. Cambridge Philos. Soc. 30 (4): 492–507, doi:10.1017/S0305004100012731, Bibcode: 1934PCPS...30..492F 
  18. ↑ Schönhardt, E. (1930), "Über lateinische Quadrate und Unionen", J. Reine Angew. Math. 1930 (163): 183–230, doi:10.1515/crll.1930.163.183 
  19. ↑ Norton, H.W. (1939), "The 7 × 7 squares", Annals of Eugenics 9 (3): 269–307, doi:10.1111/j.1469-1809.1939.tb02214.x 
  20. ↑ Sade, A. (1951), "An omission in Norton's list of 7 × 7 squares", Ann. Math. Stat. 22 (2): 306–307, doi:10.1214/aoms/1177729654 
  21. ↑ Saxena, P.N. (1951), "A simplified method of enumerating Latin squares by MacMahon's differential operators; II. The 7 × 7 Latin squares", J. Indian Soc. Agric. Statistics 3: 24–79 
  22. ↑ Preece, D.A. (1966), "Classifying Youden rectangles", J. Roy. Statist. Soc. Ser. B 28: 118–130 
  23. ↑ Brown, J.W. (1968), "Enumeration of Latin squares with application to order 8", Journal of Combinatorial Theory 5 (2): 177–184, doi:10.1016/S0021-9800(68)80053-5 
  24. ↑ Wells, M.B. (1967), "The number of Latin squares of order eight", Journal of Combinatorial Theory 3: 98–99, doi:10.1016/S0021-9800(67)80021-8 
  25. ↑ Kolesova, G.; Lam, C.W.H.; Thiel, L. (1990), "On the number of 8 × 8 Latin squares", Journal of Combinatorial Theory, Series A 54: 143–148, doi:10.1016/0097-3165(90)90015-O 
  26. ↑ Bammel, S.E.; Rothstein, J. (1975), "The number of 9 × 9 Latin squares", Discrete Mathematics 11: 93–95, doi:10.1016/0012-365X(75)90108-9 
  27. ↑ McKay, B.D.; Rogoyski, E. (1995), "Latin squares of order ten", Electronic Journal of Combinatorics 2: 4, doi:10.37236/1222 
  28. ↑ McKay, B.D.; Wanless, I.M. (2005), "On the number of Latin squares", Ann. Combin. 9 (3): 335–344, doi:10.1007/s00026-005-0261-7 

References



Retrieved from "https://handwiki.org/wiki/index.php?title=Small_Latin_squares_and_quasigroups&oldid=2996389"