Equivalence between Latin squares

74 Views Asked by At

I have two Latin squares of order 6. Is there any way to check whether they are isomorphic? I mean any program or online tool?

$ L_1= \left[ {\begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 4 & 5 & 1 & 6 & 3 \\ 3 & 1 & 2 & 6 & 4 & 5\\ 4 & 5 & 6 & 2 & 3 & 1\\ 5 & 6 & 4 & 3 & 1 & 2\\ 6 & 3 & 1 & 5 & 2 & 4 \end{array} } \right] $ $ L_2= \left[ {\begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 3 & 1 & 5 & 6 & 4 \\ 3 & 4 & 5 & 6 & 1 & 2\\ 4 & 5 & 6 & 1 & 2 & 3\\ 5 & 6 & 4 & 2 & 3 & 1\\ 6 & 1 & 2 & 3 & 4 & 5 \end{array} } \right] $

1

There are 1 best solutions below

0
On

The standard way of doing this is described in McKay, Meynert, and Myrvold, 2006 (link). Essentially this method is: convert the two Latin squares to graphs, and compare the canonical labels of the graphs computed e.g. using Nauty. Exactly which graphs to convert to depends on the equivalence type; "isotopism", "isomorphism", and "paratopism", and they're described in the above paper. (Note: this method works more generally than for Latin squares.)

Recently, we came up with a canonical labelling method via partial Latin squares for isotopism equivalence:

  • Fang, Stones, Marbach, Wang, Liu, Towards a Latin-square search engine. To appear in Proc. IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA 2019).

For small Latin squares, we find it's faster than proceeding via Nauty (which incurs conversion overhead), but Nauty is far better for larger Latin squares.

See also Computing autotopism groups of partial Latin rectangles: a pilot study; arXiv. While the focus there is computing autotopism groups, the methods can also be used for canonical labelling. The graphs described by McKay, Meynert, and Myrvold above are not the only possibility, but they are a good choice. (Down the line, we expect to publish a short version and a long version of this paper; we do a lot of experimentation in the longer one; see also my talk slides.)