16.2: Mutually Orthogonal Latin Squares (MOLS)

Last updated
Save as PDF

Page ID: 60156

Joy Morris
University of Lethbridge

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

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.

Definition: Orthogonal

Two Latin squares $S_1$ and $S_2$ 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.

So here, we are looking at positions in the structure of Latin squares, and trying to ensure that every ordered pair appears in each 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 has $n^2$ positions since it has $n$ rows and $n$ columns. Thus, if every possible ordered pair appears in each position, then each ordered pair must appear exactly once.

Once again, Euler was involved in the origins of this problem. In fact, the name Latin square comes from his terminology. In $1782$, 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$, $b$, $c$, $d$, $e$, and $f$) and each holds one of $6$ possible ranks (which he denoted with the Greek characters $α$, $β$, $γ$, $δ$, $ε$, and $ζ$). 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$, 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. 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 ≡ 2$ (mod $4$). Although Euler was correct that there is no pair of orthogonal Latin squares of order $6$, his conjecture was not true. In $1959$–$1960$, Bose, Shrikhande, and Parker first found constructions for pairs of orthogonal Latin squares of orders $22$ and $10$, and then found a general construction that can produce a pair of orthogonal Latin squares of order $n$ for every $n > 6$ with $n ≡ 2$ (mod $4$).

Example $\PageIndex{1}$

Here is a pair of orthogonal Latin squares of order $3$:

\[ 1 \; \; 2 \; \; 3 \;\;\;\;\;\;\;\;\;\;\;\; 1\;\;2\;\;3 \\ 3 \; \; 1 \; \; 2 \;\;\;\;\;\;\;\;\;\;\;\; 2\;\;3\;\;1 \\ 2 \; \; 3 \; \; 1 \;\;\;\;\;\;\;\;\;\;\;\; 3\;\;1\;\;2 \]

We see that the ordered pairs $(1, 1)$, $(2, 2)$, and $(3, 3)$ appear in the first row; the pairs $(3, 2)$, $(1, 3)$, and $(2, 1)$ appear in the second row; and the pairs $(2, 3)$, $(3, 1)$, 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$, it would give

\[ 1 \; \; 2 \; \; 3\;\;4 \;\;\;\;\;\;\;\;\;\;\;\; 1\;\;2\;\;3\;\;4 \\ 4 \; \; 1 \; \; 2\;\;3 \;\;\;\;\;\;\;\;\;\;\;\; 2\;\;3\;\;4\;\;1 \\ 3 \; \;4\;\; 1 \; \; 2 \;\;\;\;\;\;\;\;\;\;\;\; 3\;\;4\;\;1\;\;2 \\ 2 \; \; 3 \; \;4\;\; 1 \;\;\;\;\;\;\;\;\;\;\;\; 4\;\;1\;\;2\;\;3 \]

You can see that the ordered pair $(1, 1)$ occurs in two positions: row $1$, column $1$, and row $3$, column $3$. 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$:

\[ 1 \; \; 2 \; \; 3\;\;4 \;\;\;\;\;\;\;\;\;\;\;\; 1\;\;2\;\;3\;\;4 \\ 3 \; \;4\;\; 1 \; \; 2 \;\;\;\;\;\;\;\;\;\;\;\; 4 \; \;3\;\; 2 \; \; 1 \\ 4 \; \;3\;\; 2 \; \; 1 \;\;\;\;\;\;\;\;\;\;\;\; 2 \; \; 1 \; \;4\;\; 3 \\ 2 \; \; 1 \; \;4\;\; 3 \;\;\;\;\;\;\;\;\;\;\;\; 3 \; \;4\;\; 1 \; \; 2 \]

Definition: Mutually Orthogonal

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

The natural question that arises in this context 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$, and in the second square the symbol $u$ maps to the symbol $v$, 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)$, so every pair of entries must appear precisely once.

This idea that we can independently permute the symbols in each square, leads to 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, since the symbols we choose can be permuted independently to match each other. In fact, we don’t need to use symbols at all to represent some of the squares; we can vary some other characteristic. For example, to represent the two orthogonal Latin squares of order $3$ that were shown in Example 16.2.1, we can use the symbols $1$ to $3$ to represent the first square, and the colours red (for $1$), blue (for $2$) and green (for $3$) to represent the second square. However, varying the colours is not feasible in this textbook, which is printed in black-and-white. Instead, for the second square, let us use “tilted left” (for $1$), “straight up” (for $2$), and “tilted right” (for $3$). So (for example) since in the second row, third column the first square had a $2$ and the second had a $1$, we place a $2$ that is tilted to the left in that location in our new representation (tilted left because the entry of the second square was $1$; and $2$ because that was the entry of the first square). Here is the complete representation:

$clipboard_e97898ad4201b659d00544c441143a08e.png$

By the property of orthogonality, every combination of tilting and number must appear in exactly one position! Even more amazing, if we have a 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. For the two orthogonal Latin squares sought in his question, the symbols in one represent the ranks while the symbols in the other represent the regiment. In his final square, each officer could be represented by a pair of symbols indicating his rank and his regiment – or by a letter for his regiment and a colour for his rank.

Here is a partial answer to the question of how many MOLS of order $n$ there can be:

Theorem $\PageIndex{1}$

If $S$ is a set of MOLS of order $n$, then $|S| ≤ n − 1$.

Proof

We may assume that $N = \{1, . . . , n\}$. In each of the Latin squares in $S$, we can independently permute the symbols of $N$. 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, . . . , n$ in that order.

Now, if we take any $i ∈ 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$. 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^{\text{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$, than the $n − 1$ distinct entries from $N \setminus \{1\}$ that could go into this position. Thus, $|S| ≤ n − 1$, as claimed.

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

The following result can be generalised to prime powers using some basic field theory that you should understand if you have taken Math $3400$. 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: Modulo $n$

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

Notation

If $a$ and $b$ have the same remainder upon division by $n$, then we write $a ≡ b$ (mod $n$).

There are two key facts from modular arithmetic that we will require. The first is that if $a ≡ b$ (mod $n$) and $0 ≤ a$, $b < n$, then we must have $a = b$.

The other is that if $qa ≡ qb$ (mod $n$) and $n$ and $q$ have a greatest common divisor of $1$, then $a ≡ b$ (mod $n$). 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$.

Theorem $\PageIndex{2}$

For any prime $p$, there are $p − 1$ MOLS of order $p$.

Proof

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

The squares will be $\{S_1, . . . , S_{p−1}\}$. For $k ∈ \{1, . . . , p\}$,

\[S_k=\left[ \begin{array}{ll} 0 & 1 & ... &p-1\\ k & k+1 & ... &k + (p − 1)\\ 2k & 2k+1 & ... &2k + (p − 1)\\ ... & ... & ... &...\\ (p − 1)k & (p − 1)k + 1 & ... &(p − 1)k + (p − 1)\\ \end{array} \right] \]

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 ≤ i$, $j ≤ p − 1$ and that $ik ≡ jk$ (mod $p$). Then since every $k ∈ \{1, . . . , p − 1\}$ has a greatest common divisor of $1$ with $p$, we see that $i ≡ j$ (mod $p$). Since $0 ≤ i$, $j ≤ p − 1$, this forces $i = j$. So the entries in the first column of $S_k$ are all distinct. Thus, every $S_k$ is a Latin square.

Suppose that for some $1 ≤ i$, $j ≤ p − 1$, the squares $S_i$ and $S_j$ have the same ordered pair in two positions: row $k_1$, column $m_1$, and row $k_2$, column $m_2$. Then by the formulas given for the entries of each Latin square, we must have

\[ \begin{equation} \begin{split} (k_1 − 1)i + m_1 − 1 &≡ (k_2 − 1)i + m_2 − 1 (\text{mod } p), \\ \text{and } (k_1 − 1)j + m_1 − 1 &≡ (k_2 − 1)j + m_2 − 1 (\text{mod } p), \\ \text{Thus, } k_1i + m_1 &≡ k_2i + m_2 (\text{mod } p), \\ \text{and } k_1j + m_1 &≡ k_2j + m_2 (\text{mod } p), \\ \text{Therefore, } m_2 − m_1 ≡ k_2i − k_1i &= (k_2 − k_1)i ≡ k_2j − k_1j = (k_2 − k_1)j \;(\text{mod } p). \end{split} \end{equation} \]

Since $(k_2 − k_1)i ≡ (k_2 − k_1)j$ (mod $p$), and $1 ≤ i$, $j ≤ p − 1$, either $i = j$ (so we chose the same Latin square twice instead of choosing a pair of distinct Latin squares), or $k_2 −k_1 ≡ 0$ (mod $p$). Since $k_1$ and $k_2$ are row numbers, they are between $1$ and $p$ so this forces $k_1 = k_2$. Furthermore, in this case we must also have $m_2 − m_1 ≡ 0$ (mod $p$), and we see that this also forces $m_1 = m_2$. Thus, the two positions in which the same ordered pair appeared, were actually the same position chosen twice.

This shows that $\{S_k | 1 ≤ k ≤ p − 1\}$ is indeed a set of $p − 1$ MOLS.

Example $\PageIndex{2}$

Here are the first $8$ of the $10$ MOLS of order $11$, found using the formula given in the proof above.

\[ 0\; \; 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10 \;\;\;\;\;\;\;\;\;\; 0\; \; 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10 \\ 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0 \;\;\;\;\;\;\;\;\;\; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \\ 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;\;\;\;\;\;\;\;\; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1\;\;2\;\;3 \\ 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \; \;2 \;\;\;\;\;\;\;\;\;\; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5 \\ 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1\;\;2\;\;3 \;\;\;\;\;\;\;\;\;\; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;7 \\ 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \; \; 2\; \; 3\; \; 4 \;\;\;\;\;\;\;\;\;\; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\; 7\; \; 8\; \; 9 \\ 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5 \;\;\;\;\;\;\;\;\;\; 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0 \\ 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;\;\;\;\;\;\;\;\; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \; \;2 \\ 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;7 \;\;\;\;\;\;\;\;\;\; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \; \; 2\; \; 3\; \; 4 \\ 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;7\; \; 8 \;\;\;\;\;\;\;\;\;\; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \\ 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\; 7\; \; 8\; \; 9 \;\;\;\;\;\;\;\;\;\; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;7\; \; 8 \\[0.5in] 0\; \; 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10 \;\;\;\;\;\;\;\;\;\; 0\; \; 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10 \\ 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \; \;2 \;\;\;\;\;\;\;\;\;\; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1\;\;2\;\;3 \\ 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5 \;\;\;\;\;\;\;\;\;\; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;7 \\ 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;7\; \; 8 \;\;\;\;\;\;\;\;\;\; 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\\ 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0 \;\;\;\;\;\;\;\;\;\; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \; \; 2\; \; 3\; \; 4 \\ 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1\;\;2\;\;3 \;\;\;\;\;\;\;\;\;\; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;7\; \; 8 \\ 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;\;\;\;\;\;\;\;\; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \\ 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\; 7\; \; 8\; \; 9 \;\;\;\;\;\;\;\;\;\; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5 \\ 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;\;\;\;\;\;\;\;\; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\; 7\; \; 8\; \; 9 \\ 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \; \; 2\; \; 3\; \; 4 \;\;\;\;\;\;\;\;\;\; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \; \;2 \\ 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;7 \;\;\;\;\;\;\;\;\;\; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \\[0.5in] 0\; \; 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10 \;\;\;\;\;\;\;\;\;\; 0\; \; 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10 \\ 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \; \; 2\; \; 3\; \; 4 \;\;\;\;\;\;\;\;\;\; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5 \\ 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\; 7\; \; 8\; \; 9 \;\;\;\;\;\;\;\;\;\; 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0 \\ 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1\;\;2\;\;3 \;\;\;\;\;\;\;\;\;\; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \\ 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;7\; \; 8 \;\;\;\;\;\;\;\;\;\; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1\\ 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \; \;2 \;\;\;\;\;\;\;\;\;\; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;7 \\ 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;7 \;\;\;\;\;\;\;\;\;\; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \; \;2 \\ 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;\;\;\;\;\;\;\;\; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;7\; \; 8 \\ 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;\;\;\;\;\;\;\;\; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1\;\;2\;\;3 \\ 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0 \;\;\;\;\;\;\;\;\;\; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\; 7\; \; 8\; \; 9 \\ 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5 \;\;\;\;\;\;\;\;\;\; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \; \; 2\; \; 3\; \; 4 \\[0.5in] 0\; \; 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10 \;\;\;\;\;\;\;\;\;\; 0\; \; 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10 \\ 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;\;\;\;\;\;\;\;\; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;7 \\ 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \; \;2 \;\;\;\;\;\;\;\;\;\; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \; \; 2\; \; 3\; \; 4 \\ 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\; 7\; \; 8\; \; 9 \;\;\;\;\;\;\;\;\;\; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \\ 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5 \;\;\;\;\;\;\;\;\;\; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\; 7\; \; 8\; \; 9 \\ 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;\;\;\;\;\;\;\;\; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \\ 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;7\; \; 8 \;\;\;\;\;\;\;\;\;\; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1\;\;2\;\;3 \\ 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \; \; 2\; \; 3\; \; 4 \;\;\;\;\;\;\;\;\;\; 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0 \\ 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0 \;\;\;\;\;\;\;\;\;\; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;7\; \; 8 \\ 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5\; \; 6 \;\;7 \;\;\;\;\;\;\;\;\;\; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \;\;2\; \; 3\; \; 4\; \; 5 \\ 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1\;\;2\;\;3 \;\;\;\;\;\;\;\;\;\; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8\; \; 9\; \; 10\;\; 0\;\; 1 \; \;2 \\ \]

We’ve now seen that it is possible to find $p − 1$ MOLS of order $p$ for any prime $p$, and 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$. 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. There is also some information about this in Sections 18.3 and 18.4.

Exercise $\PageIndex{1}$

1) Find the two MOLS of order $11$ that are not included in Example 16.2.2, 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$, and some entries for a second Latin square of order $8$. Complete the second square so as to obtain a pair of orthogonal Latin squares.

\[ 1\; \; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8 \;\;\;\;\;\;\;\;\;\; 1\;\; 2\; \; 3\; \; 4\; \; 5\; \; 6\; \; 7\; \; 8 \\ 2\; \; 1\; \; 4\; \; 3\; \; 6\; \; 5\; \; 8\; \; 7 \;\;\;\;\;\;\;\;\;\; 3\; \; 4\; \; \_\; \; \_\; \; \_\; \; 8\; \; 5\;\; 6 \\ 3\; \; 4\; \; 1\; \; 2\; \; 7\; \; 8\; \; 5\; \; 6 \;\;\;\;\;\;\;\;\;\; 5\; \; \_\; \; 7\; \; \_\; \; \_\;\; 2\;\; 3 \;\;\_ \\ 4\; \; 3\; \; 2\; \; 1\; \; 8\; \; 7\; \; 6\;\; 5 \;\;\;\;\;\;\;\;\;\; 7\; \; \_\; \; \_\;\; 6\;\; \_ \;\;\_\; \; \_\; \; \_ \\ 5\; \; 6\; \; 7\; \; 8\; \; 1\; \; 2\;\; 3\;\; 4 \;\;\;\;\;\;\;\;\;\; 4\;\; \_\;\; \_ \;\;1\; \; 8\; \; \_\; \; \_\; \; \_ \\ 6\; \; 5\; \; 8\; \; 7\; \; 2\;\; 1\;\; 4 \;\;3 \;\;\;\;\;\;\;\;\;\; 2\; \; \_\; \; \_\; \; \_\; \; \_\; \; 5\; \; \_\; \; \_ \\ 7\; \; 8\; \; 5\; \; 6\;\; 3\;\; 4 \;\;1\; \; 2 \;\;\;\;\;\;\;\;\;\; 8\; \; \_\; \; \_\; \; \_\; \; \_\; \; \_\; \; \_\; \; 1\\ 8\; \; 7\; \; 6\;\; 5\;\; 4 \;\;3\; \; 2\; \; 1 \;\;\;\;\;\;\;\;\;\; 6\; \; \_\; \; \_\; \; 7\; \; \_\; \; \_\;\; \_\;\; 3\\ \]

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