# Maximum number of mutually orthogonal latin square pairs (definition provided)

An $n\times n$ matrix is defined to be a "latin square" if each row and column is a permutation of the first $n$ natural numbers. Two squares of same order are orthogonal if the $n^2$ pairs $(x_{ij},y_{ij})$ are "all distinct".

Proof is required that the maximal number of mutually orthogonal pairs of latin squares is $n-1$.

I have put "all distinct" in quotes, because if interpreted one way this would be easier than the book projects it to be (my intuition is usually wrong in these cases) If we fix an element $x_{ij}$ then there are $n-1$ choices for $y_{ij}$ so there can be atmost $n-1$ mutually orthogonal latin squares. I suspect this is incorrect. If so, any insight would be appreciated. This is incorrect.

For $n=1$ no pairs possible. For $n=2$ the possible latin squares are

$$\begin{pmatrix} 1 & 2\\ 2 & 1 \end{pmatrix}\qquad \mbox{and}\qquad \begin{pmatrix} 2 & 1\\ 1 & 2 \end{pmatrix}$$

By my assumed definition the above squares would be orthogonal but clearly I am asked to look at all $n^2$ pairs so my reasoning is false. There are no mutually orthogonal pairs for $n=2$ either. I would appreciate any help/pointers/hints.

-

The following is a standard proof for this fact. I outline the logic with a series of questions.

If $A$ is a latin square, you get another one by the process of renaming the entries. In this way you can put $A$ into a kind of a standard form $A_{st}$ that has $(1,2,\ldots,n)$ as its first row.

For example if

$$A=\left(\begin{array}{ccc} 2&1&3\\3&2&1\\1&3&2\end{array}\right),$$ then we can put this into standard form by putting a '1' wherever there is a '2' and a '2' wherever there is a '1' and get $$A_{st}=\left(\begin{array}{ccc} 1&2&3\\3&1&2\\2&3&1\end{array}\right)$$

Lemma: If $A$ and $B$ are orthogonal latin squares, then so are $A_{st}$ and $B_{st}$.

You prove this! It is not difficult. Let me illustrate with an example. The above LS $A$ is orthogonal to the Latin square $$B=\left(\begin{array}{ccc} 2&3&1\\3&1&2\\1&2&3\end{array}\right),$$ because the pairs of entries are (2,2),(1,3),(3,1) on the first row, (3,3),(2,1),(1,2) on the second and (1,1),(3,2),(2,3) on the last. The standard form of $B$ is (check this as a way of understanding what standard form means) $$B_{st}=\left(\begin{array}{ccc} 1&2&3\\2&3&1\\3&1&2\end{array}\right).$$ As a check that you understand orthogonality I invite you to verify that $A_{st}$ and $B_{st}$ are, indeed, orthogonal.

So if $A^{(1)}, A^{(2)},\ldots A^{(k)}$ are mutually orthogonal latin squares, then by the lemma we can assume that they all are in the standard form. Therefore the first rows contain the pairs $(i,i),i=1,2,\ldots,n$ for all the pairs of latin squares. Let us then look at the position of 2 on the first column of $A^{(1)}$. Let's say that this happens on row $j$, so $A^{(1)}_{j1}=2$.

Question #1: Why is it illegal to have $A^{(i)}_{j1}=2$ for any $i=2,3,\ldots,k$?

Question #2: Why is it illegal to have $A^{(i)}_{j1}=1$ for any $i=2,3,\ldots,k$?

Question #3: Why is it illegal to have $A^{(i)}_{j1}=A^{(\ell)}_{j1}$ for any two indices $i$ and $\ell$ such that $2\le i<\ell\le k$?

Question #4: Why do the answers to the previous questions imply $k<n$?

Prove the lemma (unless it is done in the book) and answer the questions! Good luck!

-
It took some time, but finally I was able to do your exercises. Thanks, this should be cited as a model answer. – kuch nahi Jun 18 '11 at 7:35
That wasn't my question, but it helped me solve something else with the standard form hint! Thanks! – Patrick Da Silva Sep 8 '13 at 17:08
Glad to hear that, @Patrick! – Jyrki Lahtonen Sep 8 '13 at 18:17

Your statement is equivalent to the proposition that you may construct an $n\times n \times n$ "Latin cube" because the condition of "all numbers are different from each other" along the third dimension is exactly the same as for the two original dimensions of the square.

I don't know whether the result about the non-existence of the Latin cube holds for $n\geq 3$ but it surely fails in general because it fails for $n=2$: $((1,2),(2,1))$ and $((2,1),(1,2))$ are two mutually orthogonal Latin squares. Their number exceeds $n-2=1$.

Maybe you wanted to add a condition that $n\geq 3$ and/or some extra conditions for the diagonal sums.

-
Another comment: I misread you second paragraph initially. It is wrong. There are no mutually orthogonal latin squares for the case $n=2$. So it does not "surely fail in general" because even with these cases, the maximal number is at most $n−1$. My upvote remains for thinking of the cube though. – kuch nahi Jun 14 '11 at 5:18
For your two squares, the pairs you get are $(1,2)$ (upper left corner), $(2,1)$ (upper right corner), $(1,2)$ (bottom right corner) and $(2,1)$ (bottom left corner), which are not all distinct; so the two don't satisfy the definition of "mutually orthogonal latin squares" that is given. – Arturo Magidin Jun 14 '11 at 5:22
I may have misunderstood what it means for "all pairs to be distinct". I thought it meant that $x_{ij}\neq y_{ij}$ for all choices of $ij$. If it means something completely different, like that the same doublet $(x_{ij},y_{ij})$ can't occur for two choices of $ij$, then of course my comment is totally irrelevant. – Luboš Motl Jun 14 '11 at 6:02