Overlaying Latin squares of order 4

1,111

Solution 1

You’re asking about mutually orthogonal Latin squares. The answer to the specific question is that yes, it is possible to find three mutually orthogonal Latin squares of order $4$, and that is the maximum. You’ll find a little more information and a few references at OEIS A001438.

Solution 2

The classification of pairs of orthogonal Latin squares was completed by Bose, Shrikhande and Parker in:

Bose, R. C.; Shrikhande, S. S.; Parker, E. T. Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler's conjecture. Canad. J. Math. 12 1960 189–203.

It turns out that pairs of orthogonal Latin squares exist for all orders except 2 and 6. (So, to begin with, there are no triples of mutually orthogonal Latin squares of orders 2 and 6.)

As for triples of mutually orthogonal Latin squares, a complete solution is not known. For example, it is not known whether or not there exists 3-MOLS(10) (a set of 3 mutually orthogonal Latin squares of order 10). As far as I know, this is the most up-to-date attempt at a search for a 3-MOLS(10):

McKay, Brendan D.; Meynert, Alison; Myrvold, Wendy. Small Latin squares, quasigroups, and loops. J. Combin. Des. 15 (2007), no. 2, 98–119. (pdf)

However, there are collections of known constructions of 3-MOLS(n), too many for me to survey here.

I will, however, point out one important construction. It is known that, for prime n, there exists a (n-1)-MOLS(n). Given an orthomorphism $\varphi$ of the cyclic group $\mathbb{Z}_n$, we can define a diagonally cyclic Latin square as follows:

  • In cells $(0,j)$ we put the symbol $\varphi(j)$,
  • In cells $(i,j)$, with $i>0$, we put the symbol in cell $(i-1,j-1)$ plus one (in the group $\mathbb{Z}_n$).

The properties of the orthomorphism ensure that we obtain a Latin square. For example:

0 2 4 1 3
4 1 3 0 2
3 0 2 4 1
2 4 1 3 0
1 3 0 2 4

is a diagonally cyclic Latin square derived from the orthomorphism defined by its first row. Such a Latin square will always be orthogonal to a circulant Latin square:

0 1 2 3 4
4 0 1 2 3
3 4 0 1 2
2 3 4 0 1
1 2 3 4 0

When n is prime, we can construct orthomorphisms with $i \mapsto ai$ for all $a \in \{2,3,\ldots,n-1\}$ (the $i \mapsto 2i$, $n=5$ case is above). Moreover, for two diagonally cyclic Latin squares constructed this way, they will be orthogonal (each broken diagonal accounts for the pairs of symbols that differ by some fixed amount).

The other ones for n=5 are:

0 3 1 4 2    0 4 3 2 1
3 1 4 2 0    2 1 0 4 3
1 4 2 0 3    4 3 2 1 0
4 2 0 3 1    1 0 4 3 2
2 0 3 1 4    3 2 1 0 4

This is how we can construct a set of n-1 mutually orthogonal Latin squares of order n.

This is actually the theoretical maximum size of a set of MOLS (Proof: Assume a set of n-MOLS(n) exists. Permute the symbols of each Latin square so that the symbol 0 appears in the top left corner. In the n Latin squares, there are $n(n-1)$ copies of the symbol 0 not in the top row nor left-most column in each Latin square. But these 0's must be in distinct cells, otherwise we get two copies of the pair (0,0) between two Latin squares. Since there's not enough cells to accommodate the $n(n-1)$ copies of the symbol 0, we get a contradiction.)

Share:
1,111

Related videos on Youtube

Aria Fitzpatrick
Author by

Aria Fitzpatrick

Updated on August 01, 2022

Comments

  • Aria Fitzpatrick
    Aria Fitzpatrick over 1 year

    Here are two latin squares overlayed upon each other to make one latin square, if you will. One "sub-latin" square is labeled with $1,2,3,4$ while the other is represented with $a,b,c,d$. There must be an $a$ corresponding to each of $1,2,3,4$ as you will see(and so on) and there must be $1$ corresponding to each $a,b,c,d$ as well and so on.

                         (1,a)  (2,d)  (3,b)  (4,c)
                         (2,c)  (1,b)  (4,d)  (3,a)
                         (4,b)  (3,c)  (2,a)  (1,d)
                         (3,d)  (4,a)  (1,c)  (2,b)
    

    Can we find three latin squares of order four such that any two of them will overlie on each other perfectly? How many different such Latin squares can we have?

    EDIT:
    Is there a method to creating mutually orthogonal squares to any extent?

  • Aria Fitzpatrick
    Aria Fitzpatrick over 11 years
    Is there a method to creating mutually orthogonal squares to any extent?
  • Brian M. Scott
    Brian M. Scott over 11 years
    @Aria: I honestly don’t know; my knowledge of them is minimal. This paper might give you a starting point, if you have access to it.
  • Gerry Myerson
    Gerry Myerson over 11 years
    Indeed, when $n$ is a prime power, there are $n-1$ mutually orthogonal Latin squares of order $n$, if I'm not mistaken.
  • Aria Fitzpatrick
    Aria Fitzpatrick over 11 years
    @Douglas for the final proof by contradiction, must the order of the square be prime? If so would you be able to show why?
  • Douglas S. Stones
    Douglas S. Stones over 11 years
    No, there's no restriction on n being prime in that proof (it's valid for all n).
  • jd123
    jd123 about 4 years
    Take a Circulant Latin Square, (take top row {0,1,2,...,n-1} and shifting it by 1 to the right in each subsequent row. Isomorpic to Zn) Make another Circulant latin Square with top row (n-1,n-2,...,1,0). In n is odd then these two Latin Squares are mutually orthogonal.