# Does there exist a Latin square of order 16 that admits a specific automorphism?

One of the perks of my research topic (Latin squares) is that it's somewhat possible to explain what I do to those with a fairly minimal mathematics background. I'll pose a typical question that comes up in one of my main research topics as a problem here -- I'm hoping that this will whet the appetite of someone considering doing postgrad mathematics.

A Latin square is an $n \times n$ matrix with symbols from $[n]:=\{1,2,\ldots,n\}$ such that each row and each column contains every symbol.

Let $L=(l_{ij})$ be a Latin square. For any row $i$ and column $j$, We say $(i,j,l_{ij})$ is a entry of $L$. The set of entries $O=\{(i,j,l_{ij}):i \in [n], j \in [n]\}$ is called the orthogonal array of $L$.

An automorphism of $L$ is a permutation $\alpha$ of $\{1,2,\ldots,n\}$ such that $O$ is preserved under $(i,j,l_{ij}) \mapsto (\alpha(i),\alpha(j),\alpha(l_{ij}))$.

This definition might seem a little complicated, but we can view this property reasonably easily. Here's an example for order 15:

$\left(\begin{array}{cccccccccccc|ccc} 13 & 8 & 14 & 9 & 15 & \mathbf{10} & 4 & 11 & 5 & 12 & 6 & 1 & 7 & 3 & 2 \\ 2 & 14 & 9 & 15 & 10 & 13 & \mathbf{11} & 5 & 12 & 6 & 1 & 7 & 3 & 8 & 4 \\ 8 & 3 & 15 & 10 & 13 & 11 & 14 & \mathbf{12} & 6 & 1 & 7 & 2 & 5 & 4 & 9 \\ 3 & 9 & 4 & 13 & 11 & 14 & 12 & 15 & \mathbf{1} & 7 & 2 & 8 & 10 & 6 & 5 \\ 9 & 4 & 10 & 5 & 14 & 12 & 15 & 1 & 13 & \mathbf{2} & 8 & 3 & 6 & 11 & 7 \\ 4 & 10 & 5 & 11 & 6 & 15 & 1 & 13 & 2 & 14 & \mathbf{3} & 9 & 8 & 7 & 12 \\ 10 & 5 & 11 & 6 & 12 & 7 & 13 & 2 & 14 & 3 & 15 & \mathbf{4} & 1 & 9 & 8 \\ \mathbf{5} & 11 & 6 & 12 & 7 & 1 & 8 & 14 & 3 & 15 & 4 & 13 & 9 & 2 & 10 \\ 14 & \mathbf{6} & 12 & 7 & 1 & 8 & 2 & 9 & 15 & 4 & 13 & 5 & 11 & 10 & 3 \\ 6 & 15 & \mathbf{7} & 1 & 8 & 2 & 9 & 3 & 10 & 13 & 5 & 14 & 4 & 12 & 11 \\ 15 & 7 & 13 & \mathbf{8} & 2 & 9 & 3 & 10 & 4 & 11 & 14 & 6 & 12 & 5 & 1 \\ 7 & 13 & 8 & 14 & \mathbf{9} & 3 & 10 & 4 & 11 & 5 & 12 & 15 & 2 & 1 & 6 \\ \hline 12 & 2 & 1 & 3 & 5 & 4 & 6 & 8 & 7 & 9 & 11 & 10 & 15 & 14 & 13 \\ 11 & 1 & 3 & 2 & 4 & 6 & 5 & 7 & 9 & 8 & 10 & 12 & 14 & 13 & 15 \\ 1 & 12 & 2 & 4 & 3 & 5 & 7 & 6 & 8 & 10 & 9 & 11 & 13 & 15 & 14 \\ \end{array}\right)$

which admits the automorphism $\alpha=(1,2,3,4,5,6,7,8,9,10,11,12)(13,14,15)$. The horizontal and vertical lines indicate where the cycles "break" in $\alpha$. I highlight an orbit of an entry [i.e. starting with the entry (1,6,10), we apply $\alpha$ repeatedly] -- it traces out a broken diagonal of the upper-left block, and the symbol "increases by one, wrapping around after 12".

So, here's a sample question from my research:

Question: Let $\alpha=(1,2,3,4,5,6)(7,8,9,10,11,12)(13,14)(15,16)$. Is $\alpha$ an automorphism of some Latin square of order $16$?

This is a question that has come up in my research, and the more general question "Given $\alpha$, is $\alpha$ an automorphism of some Latin square of order $n$?" is one of my main research topics.

-
I'm a little bit curious. Have you gotten general results about the possible cycle structure of automorphism of Latin squares of a prescribed size? –  Jyrki Lahtonen Jun 14 '11 at 8:46
We've (along with Ian Wanless and Petr Vojtechovsky) obtained a few general results, e.g. we classified which isomorphisms are automorphisms when they have <=3 non-trivial cycles or when all cycles have the same length. We've also found a bunch of necessary conditions. But we've so far been unable to completely classify these things. It appears to be a very difficult problem. –  Douglas S. Stones Jun 14 '11 at 22:02

$$\left( \begin{array}{cccccccccccccccc} 14 & 16 & 1 & 3 & 7 & 9 & 8 & 11 & 13 & 15 & 4 & 6 & 2 & 10 & 5 & 12\\ 10 & 13 & 15 & 2 & 4 & 8 & 1 & 9 & 12 & 14 & 16 & 5 & 11 & 3 & 7 & 6\\ 9 & 11 & 14 & 16 & 3 & 5 & 6 & 2 & 10 & 7 & 13 & 15 & 4 & 12 & 1 & 8\\ 6 & 10 & 12 & 13 & 15 & 4 & 16 & 1 & 3 & 11 & 8 & 14 & 7 & 5 & 9 & 2\\ 5 & 1 & 11 & 7 & 14 & 16 & 13 & 15 & 2 & 4 & 12 & 9 & 6 & 8 & 3 & 10\\ 15 & 6 & 2 & 12 & 8 & 13 & 10 & 14 & 16 & 3 & 5 & 7 & 9 & 1 & 11 & 4\\ 3 & 15 & 13 & 8 & 5 & 11 & 14 & 16 & 4 & 6 & 10 & 12 & 1 & 7 & 2 & 9\\ 12 & 4 & 16 & 14 & 9 & 6 & 7 & 13 & 15 & 5 & 1 & 11 & 8 & 2 & 10 & 3\\ 1 & 7 & 5 & 15 & 13 & 10 & 12 & 8 & 14 & 16 & 6 & 2 & 3 & 9 & 4 & 11\\ 11 & 2 & 8 & 6 & 16 & 14 & 3 & 7 & 9 & 13 & 15 & 1 & 10 & 4 & 12 & 5\\ 13 & 12 & 3 & 9 & 1 & 15 & 2 & 4 & 8 & 10 & 14 & 16 & 5 & 11 & 6 & 7\\ 16 & 14 & 7 & 4 & 10 & 2 & 15 & 3 & 5 & 9 & 11 & 13 & 12 & 6 & 8 & 1\\ 2 & 9 & 4 & 11 & 6 & 7 & 5 & 10 & 1 & 12 & 3 & 8 & 14 & 15 & 16 & 13\\ 8 & 3 & 10 & 5 & 12 & 1 & 9 & 6 & 11 & 2 & 7 & 4 & 16 & 13 & 14 & 15\\ 7 & 5 & 9 & 1 & 11 & 3 & 4 & 12 & 6 & 8 & 2 & 10 & 13 & 16 & 15 & 14\\ 4 & 8 & 6 & 10 & 2 & 12 & 11 & 5 & 7 & 1 & 9 & 3 & 15 & 14 & 13 & 16 \end{array}\right).$$