Prove there is only one main class latin square of order 4.

66 Views Asked by At

I'm learning about latin squares and orthogonal latin squares. My question is how can I prove there's only one main class latin square of order 4? I did this one

$$\array{0&1&2&3\\1&2&3&0\\2&3&0&1\\3&0&1&2}$$

which is the normalized one and there's shouldn't be any other latin square orthogonal to this one but I don't get how to formally prove it. Thanks for the help.

1

There are 1 best solutions below

0
On

I think you've written the wrong thing in the title. There are two main classes of Latin square of order $4$: $$\begin{array}{|cccc|} \hline 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \\ \hline \end{array} \qquad \begin{array}{|cccc|} \hline 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ 3 & 4 & 1 & 2 \\ 2 & 3 & 4 & 1 \\ \hline \end{array}$$ You can prove they're not in the same main class by counting $2 \times 2$ subsquares (intercalates): the one on the left has $12$ intercalates, and the one on the right has $4$ intercalates.

As we'll see below, there is:

  • one main class of sets of 2 orthogonal Latin squares of order $4$ (2-MOLS(4)), and
  • one main class of sets of 3 orthogonal Latin squares of order $4$ (3-MOLS(4)).

The Latin square on the left above belongs to a set of 3 mutually orthogonal Latin squares (or as in PM 2Ring's comment). We can prove the one on the right has no orthogonal mate (it's the answer to this question), so it doesn't belong to any sets of orthogonal Latin squares.

Since the Latin squares are small, we can find the orthogonal mates of the Latin square on the left manually. Since we can permute the symbols in an orthogonal mate to obtain another orthogonal mate, we can assume the first row is $(1,2,3,4)$. Afterwards, the cell $(2,1)$ can be filled in $2$ ways without violating the Latin property nor the orthogonal property. Once this decision is made, the remainder of the Latin square is determined (from the Latin property or the orthogonal property)---you can fill it in like a sudoku. $$\begin{array}{|cccc|} \hline 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \\ \hline \end{array} \qquad \begin{array}{|cccc|} \hline \bf 1 & \bf 2 & \bf 3 & \bf 4 \\ \bf \color{blue} 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \\ 2 & 1 & 4 & 3 \\ \hline \end{array} \qquad \begin{array}{|cccc|} \hline \bf 1 & \bf 2 & \bf 3 & \bf 4 \\ \bf \color{blue} 4 & 3 & 2 & 1 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ \hline \end{array} $$ So there is only one main class of sets of 3 orthogonal Latin squares.

To check there is only one main class of sets of 2 orthogonal Latin squares, we need to check the two we incidentally found above are in the same main class: $$\left\{\begin{array}{|cccc|} \hline 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \\ \hline \end{array}, \qquad \begin{array}{|cccc|} \hline \bf 1 & \bf 2 & \bf 3 & \bf 4 \\ \bf \color{blue} 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \\ 2 & 1 & 4 & 3 \\ \hline \end{array}\right\} $$

$$\left\{\begin{array}{|cccc|} \hline 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \\ \hline \end{array}, \qquad \begin{array}{|cccc|} \hline \bf 1 & \bf 2 & \bf 3 & \bf 4 \\ \bf \color{blue} 4 & 3 & 2 & 1 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ \hline \end{array}\right\} $$

To check this, we take the first pair and swap the rows 3 and 4, then swap the columns 3 and 4, then swap the symbols 3 and 4, which gives the second pair above.