Skip to main content

Section 16.2 Mutually orthogonal Latin squares (MOLS)

Most of design theory is concerned with creating nice structures in which different combinations of elements occur equally often. This is the general structure of all of the design theory we will be covering here, and in this context, orthogonal Latin squares are the natural thing to learn about. Before giving a formal definition, we'll explain the problem that introduced this concept.

Once again, Leonhard Euler (1707—1783) was involved in the origins of this problem. In fact, the name Latin square comes from his terminology. In \(1782\text{,}\) he posed the problem of arranging \(36\) officers into a \(6 \times 6\) square. The officers come from \(6\) different regiments (which he denoted with the Latin characters \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) \(d\text{,}\) \(e\text{,}\) and \(f\)) and each holds one of \(6\) possible ranks (which he denoted with the Greek characters \(\alpha\text{,}\) \(\beta\text{,}\) \(\gamma\text{,}\) \(\delta\text{,}\) \(\varepsilon\text{,}\) and \(\zeta\)). No two officers from the same regiment hold the same rank. The question he posed was, is it possible to organise the officers into the square so that in each row and each column, there is precisely one officer from each regiment, and precisely one officer of each rank? Since he was using Greek and Roman letters to denote the classes, he called this a “Graeco-Latin square.” He chose the first step to consist of arranging the regiments, i.e. for each regiment to set aside \(6\) positions in the square to be filled with officers from that regiment. Subsequently, he would try to assign ranks to the officers in these \(6\) positions. Since the regiments were denoted by Latin characters, he called this first step a “Latin square.” The Graeco-Latin square of his question is a pair of orthogonal Latin squares of order \(6\text{.}\) We'll explain this in more detail shortly, but the key idea is that after the second step is completed, each entry consists of a Greek letter and a Roman letter, and each Greek letter should appear exactly once with each Roman letter since there is to be one officer from each regiment who holds each of the possible ranks.

Euler could not find a solution to this problem, although he was able to produce pairs of orthogonal Latin squares for any \(n \not\equiv 2\pmod{4}\text{.}\) Since there is also no pair of orthogonal Latin squares of order \(2\) (and possibly for other reasons), he conjectured that there is no pair of orthogonal Latin squares of order \(n\) for any \(n \equiv 2\pmod{4}\text{.}\) Although Euler was correct that there is no pair of orthogonal Latin squares of order \(6\text{,}\) his conjecture was not true. In \(1959-1960\text{,}\) Raj Chandra Bose (1901—1987), Sharadchandra Shankar Shrikhande (1917—2020), and Ernest Tilden Parker (1926—1991) first found constructions for pairs of orthogonal Latin squares of orders \(22\) and \(10\text{,}\) and then found a general construction that can produce a pair of orthogonal Latin squares of order \(n\) for every \(n>6\) with \(n \equiv 2\pmod{4}\text{.}\)

Definition 16.2.1.

Two Latin squares \(S_1\) and \(S_2\) of order \(n\) are orthogonal if when we look at each position in turn and consider the ordered pair formed by the entry of \(S_1\) in that position, and the entry of \(S_2\) in that position, every possible ordered pair appears.

In the context of Euler's problem, this definition proposes that the problem be worked on slightly differently: first create a Latin square with the Roman letters (as Euler did). Then, rather than trying to assign a Greek letter to each officer (and trying to satisfy the other conditions), we try to form a second Latin square with just the Greek letters. Once we have both squares, we check to see if they are “orthogonal”. If they are, it means that if we look at each of the 36 positions in turn and write the Roman letter from that position in the first square followed by the Greek letter from that position in the second square as an ordered pair, each of the 36 possible ordered pairs occurs exactly once in our list. Translating this back into Euler's terms, each regiment will contain exactly one officer of each rank.

In our definition, we are looking at positions in Latin squares of order \(n\text{,}\) and trying to ensure that every ordered pair appears in some position. Notice that since the set \(N\) has \(n\) elements, the total number of ordered pairs possible is \(n^2\) (there are \(n\) choices for the first entry and \(n\) choices for the second entry). A Latin square of order \(n\) has \(n^2\) positions since it has \(n\) rows and \(n\) columns. Thus, if every possible ordered pair appears in some position, then each ordered pair must appear exactly once.

Here is a pair of orthogonal Latin squares of order \(3\text{:}\)

\begin{equation*} \begin{matrix}1\amp 2\amp 3\\ 3\amp 1\amp 2\\ 2\amp 3\amp 1 \end{matrix} \qquad\qquad \begin{matrix}1\amp 2\amp 3\\ 2\amp 3\amp 1\\ 3\amp 1\amp 2 \end{matrix} \end{equation*}

We see that the ordered pairs \((1,1)\text{,}\) \((2,2)\) and \((3,3)\) appear in the first row; the pairs \((3,2)\text{,}\) \((1,3)\text{,}\) and \((2,1)\) appear in the second row; and the pairs \((2,3)\text{,}\) \((3,1)\text{,}\) and \((1,2)\) appear in the third row. Every possible ordered pair whose entries lie in \(\{1,2,3\}\) has appeared.

There is a nice pattern to the squares given in this example. The first follows the general construction we mentioned at the start of this chapter. For the second, each row has been shifted one place to the left (rather than to the right) from the one above it. This construction does actually work for \(n\) odd, but never for \(n\) even. For example, when \(n=4\text{,}\) it would give

\begin{equation*} \begin{matrix}1\amp 2\amp 3\amp 4\\ 4\amp 1\amp 2\amp 3\\ 3\amp 4\amp 1\amp 2\\ 2\amp 3\amp 4\amp 1 \end{matrix} \qquad\qquad \begin{matrix}1\amp 2\amp 3\amp 4\\ 2\amp 3\amp 4\amp 1\\ 3\amp 4\amp 1\amp 2\\ 4\amp 1\amp 2\amp 3 \end{matrix} \end{equation*}

You can see that the ordered pair \((1,1)\) occurs in two positions: row \(1\text{,}\) column \(1\text{,}\) and row \(3\text{,}\) column \(3\text{.}\) So this pair of Latin squares is definitely not orthogonal. In fact, the first of these squares has no Latin square that is orthogonal to it. However, there is a pair of orthogonal Latin squares of order \(4\text{:}\)

\begin{equation*} \begin{matrix}1\amp 2\amp 3\amp 4\\ 3\amp 4\amp 1\amp 2\\ 4\amp 3\amp 2\amp 1\\ 2\amp 1\amp 4\amp 3 \end{matrix} \qquad\qquad \begin{matrix}1\amp 2\amp 3\amp 4\\ 4\amp 3\amp 2\amp 1\\ 2\amp 1\amp 4\amp 3\\ 3\amp 4\amp 1\amp 2 \end{matrix} \end{equation*}
Definition 16.2.3.

A set of Latin squares is mutually orthogonal if every distinct pair of Latin squares in the set are orthogonal. We call such a set, a set of MOLS (for Mutually Orthogonal Latin Squares).

There is a very nice method of representing MOLS. The key idea is that it is not necessary to use the same set of symbols for each square. Furthermore, we can write the whole structure as one square, with an ordered pair in each position, as Euler did for his Graeco-Roman problem. So Euler might have represented our orthogonal Latin squares of order \(3\) as the single square

\begin{equation*} \begin{matrix}(a,\alpha) \amp (b, \beta) \amp (c,\gamma)\\ (c,\beta)\amp (a,\gamma)\amp (b,\alpha)\\ (b,\gamma)\amp (c,\alpha)\amp (a,\beta) \end{matrix}. \end{equation*}

But there's no reason to stick to Greek and Roman letters. Why not have colours instead of the Greek letters? If we change \(\alpha\) to red, \(\beta\) to blue, and \(\gamma\) to green, we have instead:

\begin{equation*} \begin{matrix}(a,\text{red}) \amp (b, \text{blue}) \amp (c,\text{green})\\ (c,\text{blue})\amp (a,\text{green})\amp (b,\text{red})\\ (b,\text{green})\amp (c,\text{red})\amp (a,\text{blue}) \end{matrix}. \end{equation*}

In fact, since the second entry of the ordered pair can now be thought of as another characteristic (colour), we can represent this by simply listing the first entry and varying the characteristic. So instead of \((3,\text{blue})\) we can simply show a blue \(3\text{.}\) However, varying the colours is not feasible here (since we are keeping essential elements in black-and-white for the sake of accessibility and ease of printing). Instead, let us use “tilted left” (for blue), “straight up” (for red), and “tilted right” (for green). So (for example) since in the second row, third column our square of ordered pairs had the entry \((2,\text{blue})\text{,}\) and blue corresponds to a left tilt, we place a \(2\) that is tilted to the left in that location in our new representation. Here is the complete representation:

1 2 3
3 1 2
2 3 1

By the property of orthogonality, every combination of tilting and number must appear in exactly one position! Even more amazing, if we have a larger set of MOLS and vary different parameters for each of the squares, the fact that the squares are all mutually orthogonal will mean that every combination of the parameters appears in exactly one position. For example, if we have a set of five MOLS, we could place a coloured shape behind each coloured symbol, and have different numbers of copies of the symbol. For any possible colour of any possible shape appearing behind any possible number of any possible colour of any possible symbol, you would be able to find a position in which that combination appears!

This approach to MOLS is essentially the context in which they first arose, as we can see from Euler's example of the officers.

A natural question that arises in the context of the concepts we have been introducing in this section is, how many Latin squares can there be in a set of MOLS?

Before we attempt to answer this question, notice that if we have a pair of orthogonal Latin squares and we permute the symbols used in the set \(N\) independently for each of the squares (resulting in new Latin squares that are nonetheless essentially the same, as discussed in Section 16.1), the resulting pair of Latin squares will still be orthogonal. If in the first square the symbol \(x\) maps to the symbol \(y\text{,}\) and in the second square the symbol \(u\) maps to the symbol \(v\text{,}\) then in the new pair of Latin squares the ordered pair \((y,v)\) will appear precisely once, since the ordered pair \((x,u)\) appeared precisely once in the original pair of Latin squares. This is true for any pair of entries \((y,v)\text{,}\) so every pair of entries must appear precisely once. Now we are ready to partially answer the question of how many MOLS of order \(n\) there can be:

We may assume that \(N=\{1, \ldots, n\}\text{.}\) In each of the Latin squares in \(S\text{,}\) we can independently permute the symbols of \(N\text{.}\) As was noted above, the result will still be a set of MOLS. We permute the symbols so that the first row of each of the Latin squares has the entries \(1, 2, \ldots, n\) in that order.

Now, if we take any \(i \in N\) and consider any pair of the Latin squares, the ordered pair \((i,i)\) appears somewhere in the first row. Consider the first entry of the second row in each square of \(S\text{.}\) None of these entries can be 1, since 1 has already appeared in the first column of each of the Latin squares. No two of the Latin squares can have the same entry \(j\) in this position, since the ordered pair \((j,j)\) has already appeared in the \(j\)th position of the first row of this pair of squares, so can't appear again in the first position of the second row. So there cannot be more squares in \(S\text{,}\) than the \(n-1\) distinct entries from \(N\setminus\{1\}\) that could go into this position. Thus, \(|S|\le n-1\text{,}\) as claimed.

⬛

The next natural question is, is it possible to achieve \(n-1\) MOLS of order \(n\text{?}\) We have already seen that the answer is yes in one very small case, since we found \(2\) MOLS of order \(3\text{.}\) In fact, there are infinitely many values of \(n\) for which there are \(n-1\) MOLS of order \(n\text{.}\)

The following result can be generalised to prime powers using some basic field theory that you should understand if you have taken a course that includes any field theory. However, for the purposes of this course, we will avoid the explicit field theory and prove the result only for primes.

We do require a bit of modular arithmetic for this result. As modular arithmetic will also be useful for some of our later results, here is a quick review of some key points.

Definition 16.2.5.

Performing calculations modulo \(n\) means replacing the result with the remainder you would get upon dividing that result by \(n\text{.}\) In other words, if the result of a computation is \(n\) or larger, replace the result by its remainder upon division by \(n\text{.}\)

Notation 16.2.6.

If \(a\) and \(b\) have the same remainder upon division by \(n\text{,}\) then we write \(a \equiv b \pmod{n}\).

There are two key facts from modular arithmetic that we will require. The first is that if \(a \equiv b \pmod{n}\) and \(0 \le a, b \lt n\text{,}\) then we must have \(a=b\text{.}\)

The other is that if \(qa \equiv qb \pmod{n}\) and \(n\) and \(q\) have a greatest common divisor of \(1\text{,}\) then \(a \equiv b \pmod{n}\text{.}\) In the special case where \(n\) is prime, as long as \(q\) is not a multiple of \(n\) then \(n\) and \(q\) will always have a greatest common divisor of \(1\text{.}\)

We will use \(N=\{0,\ldots, p-1\}\text{.}\) In order to ensure that the results of our computations will be in \(N\text{,}\) all of the calculations given in this result should be taken modulo \(p\text{.}\)

The squares will be \(\{S_1, \ldots, S_{p-1}\}\text{.}\) For \(k \in \{1,\ldots, p\}\text{,}\)

\begin{equation*} S_k=\left[\begin{matrix}0\amp 1\amp \ldots \amp p-1\\ k\amp k+1 \amp \ldots \amp k+(p-1)\\ 2k\amp 2k+1 \amp \ldots \amp 2k+(p-1)\\ \vdots\amp \vdots \amp \amp \vdots\\ (p-1)k\amp (p-1)k+1\amp \ldots \amp (p-1)k+(p-1) \end{matrix} \right] \end{equation*}

We first verify that each \(S_k\) is a Latin square. The entries in each row are easily seen to be distinct. If the entries in the first column are distinct, then we can see that the entries in every other column will be distinct. Suppose that \(0 \le i,j \le p-1\) and that \(ik\equiv jk\pmod{p}\text{.}\) Then since every \(k\in \{1, \ldots, p-1\}\) has a greatest common divisor of \(1\) with \(p\text{,}\) we see that \(i\equiv j\pmod{p}\text{.}\) Since \(0 \le i,j\le p-1\text{,}\) this forces \(i=j\text{.}\) So the entries in the first column of \(S_k\) are all distinct. Thus, every \(S_k\) is a Latin square.

Now we verify that any two squares \(S_i\) and \(S_j\) are orthogonal. We will do this by taking an arbitrary pair of squares \(S_i\) and \(S_j\) with \(i \neq j\text{,}\) and supposing that the ordered pair that arises from the entries in position \((k_1,m_1)\) of these two squares is the same as the ordered pair that arises from the entries in position \((k_2,m_2)\text{.}\) If this can happen, then unless the two positions are actually the same, the squares would not be orthogonal. So our goal will be to deduce that in fact the two positions are the same: that is, \(k_1=k_2\) and \(m_1=m_2\text{.}\)

Suppose that for some \(1 \le i,j \le p-1\text{,}\) the squares \(S_i\) and \(S_j\) have the same ordered pair in two positions: row \(k_1\text{,}\) column \(m_1\text{,}\) and row \(k_2\text{,}\) column \(m_2\text{.}\) Then by the formulas given for the entries of each Latin square, we must have

\begin{align*} (k_1-1)i+m_1-1\amp \equiv (k_2-1)i+m_2-1\pmod{p},\\ \text{ and } (k_1-1)j+m_1-1 \equiv\amp (k_2-1)j+m_2-1\pmod{p}.\\ \text{ Thus, } k_1i+m_1\amp \equiv k_2i+m_2\pmod{p},\\ \text{ and } k_1j+m_1\amp \equiv k_2j+m_2\pmod{p}.\\ \text{ Therefore, } m_2-m_1\equiv k_2i-k_1i\amp= (k_2-k_1)i\equiv k_2j-k_1j=(k_2-k_1)j\pmod{p}\text{.} \end{align*}

Since \((k_2-k_1)i\equiv (k_2-k_1)j\pmod{p}\text{,}\) and \(1\le i,j\le p-1\text{,}\) and we are assuming \(i\neq j\text{,}\) we must have \(k_2-k_1\equiv 0 \pmod{p}\text{.}\) Since \(k_1\) and \(k_2\) are row numbers, they are between 1 and \(p\) so this forces \(k_1=k_2\text{.}\) Furthermore, in this case we must also have \(m_2-m_1\equiv 0\pmod{p}\text{,}\) and we see that this also forces \(m_1=m_2\text{.}\) This is what we wanted to show.

This shows that \(\{S_k \mid 1\le k \le p-1\}\) is indeed a set of \(p-1\) MOLS.

⬛

Here are the first \(8\) of the \(10\) MOLS of order \(11\text{,}\) found using the formula given in the proof above.

\begin{equation*} \begin{matrix}\begin{matrix}0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\\ 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\\ 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\\ 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\\ 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\\ 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\\ 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\\ 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\\ 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\\ 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\\ 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9 \end{matrix} \amp \qquad\amp \begin{matrix}0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\\ 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\\ 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\\ 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\\ 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\\ 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\\ 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\\ 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\\ 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\\ 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\\ 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8 \end{matrix} \end{matrix} \end{equation*}
\begin{equation*} \begin{matrix}\begin{matrix}0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\\ 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\\ 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\\ 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\\ 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\\ 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\\ 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\\ 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\\ 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\\ 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\\ 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7 \end{matrix} \amp \qquad\amp \begin{matrix}0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\\ 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\\ 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\\ 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\\ 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\\ 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\\ 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\\ 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\\ 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\\ 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\\ 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6 \end{matrix} \end{matrix} \end{equation*}
\begin{equation*} \begin{matrix}\begin{matrix}0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\\ 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\\ 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\\ 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\\ 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\\ 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\\ 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\\ 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\\ 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\\ 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\\ 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5 \end{matrix} \amp \qquad\amp \begin{matrix}0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\\ 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\\ 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\\ 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\\ 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\\ 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\\ 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\\ 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\\ 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\\ 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\\ 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4 \end{matrix} \end{matrix} \end{equation*}
\begin{equation*} \begin{matrix}\begin{matrix}0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\\ 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\\ 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\\ 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\\ 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\\ 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\\ 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\\ 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\\ 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\\ 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\\ 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3 \end{matrix} \amp \qquad\amp \begin{matrix}0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\\ 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\\ 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\\ 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\\ 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\\ 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\\ 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\\ 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\\ 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\\ 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2\amp 3\amp 4\amp 5\\ 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 0\amp 1\amp 2 \end{matrix} \end{matrix} \end{equation*}

We've now seen that it is possible to find \(p-1\) MOLS of order \(p\) for any prime \(p\text{,}\) and have noted that the proof can be generalised to prime powers. However, as we've already discussed in relation to Euler's original problem, there are orders for which the bound of \(n-1\) MOLS of order \(n\) cannot be attained: in fact, for order \(6\) it is not possible even to find a pair of orthogonal Latin squares.

If you are interested in or familiar with some finite geometry, the existence of \(n-1\) MOLS of order \(n\) is equivalent to the existence of a projective plane of order \(n\text{.}\) Projective planes, in turn, are a special kind of design. For an interesting article about some of these relationships, see https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Lam305-318.pdf. This article is by Clement Wing Hong Lam (1949—), who (with coauthors Larry Henry Thiel (1945—) and Stan Swiercz (1955—)) in 1989 used a computer to prove that there is no projective plane of order \(10\) (and equivalently, that there are not \(9\) MOLS\((10)\)). There is also some information about affine planes, projective planes, and their existence in Sections 18.3 and 18.4. Whether or not a projective plane of order \(12\) exists is unknown. The nonexistence of a plane of order \(10\) was independently verified in \(2011\) and again in \(2020\) using a different (but still computer-based) approach.

  1. Find the two MOLS of order \(11\) that are not included in Example 16.2.8, but are orthogonal to each other and to the squares listed there.

  2. Find a third Latin square of order \(4\) that is orthogonal to both of the orthogonal Latin squares of order \(4\) that were given earlier in this section.

  3. Here is a Latin square of order \(8\text{,}\) and some entries for a second Latin square of order \(8\text{.}\) Complete the second square so as to obtain a pair of orthogonal Latin squares.

    \begin{equation*} \begin{matrix}1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\\ 2\amp 1\amp 4\amp 3\amp 6\amp 5\amp 8\amp 7\\ 3\amp 4\amp 1\amp 2\amp 7\amp 8\amp 5\amp 6\\ 4\amp 3\amp 2\amp 1\amp 8\amp 7\amp 6\amp 5\\ 5\amp 6\amp 7\amp 8\amp 1\amp 2\amp 3\amp 4\\ 6\amp 5\amp 8\amp 7\amp 2\amp 1\amp 4\amp 3\\ 7\amp 8\amp 5\amp 6\amp 3\amp 4\amp 1\amp 2\\ 8\amp 7\amp 6\amp 5\amp 4\amp 3\amp 2\amp 1 \end{matrix} \qquad \begin{matrix}1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\\ 3\amp 4\amp -\amp -\amp -\amp 8\amp 5\amp 6\\ 5\amp -\amp 7\amp -\amp -\amp 2\amp 3\amp -\\ 7\amp -\amp -\amp 6\amp -\amp -\amp -\amp -\\ 4\amp -\amp -\amp 1\amp 8\amp -\amp -\amp -\\ 2\amp -\amp -\amp -\amp -\amp 5\amp -\amp -\\ 8\amp -\amp -\amp -\amp -\amp -\amp -\amp 1\\ 6\amp -\amp -\amp 7\amp -\amp -\amp -\amp 3 \end{matrix} \end{equation*}

  4. Write down the six mutually orthogonal Latin squares \(S_1,\ldots,S_6\) of order \(7\) that are constructed by letting \(p = 7\) in the proof of Theorem 16.2.7.