Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

If I understood your requirement correctly, then the following should fit the bill. Please check! My checking was done while constructing it, so consists mostly of staring at the laptop screen.

The Latin square with this kind of symmetry is determined, if we know all of the rows 1 and 7, and essential parts of rows 13 and 15 (=entries 1,2,7,8,13,14,15 and 16). I wrote a Mathematica snippet to fill in the blanks. The construction was basically trial and error, so a lot of randomness in the first row. The rest was educated guessing observing the obvious constraints about placing the entries of the size 2 orbits, and trying to mix the rest of them as evenly between the orbits as possible. Hopefully there is a more elegant way of doing this :-)

If this is no longer of interest to you, don't worry! I had fun for 2 hours :-) If you find an error, I apologiz for wasting your time.

$$ \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). $$

share|improve this answer
    
Looks good to me. Actually, I find myself constructing them the same way (there are many easy cases, this one was a bit tricky). I'd be very interested in finding better ways to answer this type of question. –  Douglas S. Stones Jun 14 '11 at 8:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.