This question is related to my previous one but different in its substance. I have a several questions that I am not able to find answers to.
My understanding of mutually orthogonal latin squares is as follows: The utility of mutually orthogonal latin squares in the context of pairwise SW testing comes from the fact that the superimposing (what about cartesian product?) of any two squares will be a set of distinct values, i.e. I will have all possible pairs covered exactly once.
- What is the rationale behind the formula? I did not find it mentioned anywhere and I would like to understand how to get it. This is said to work if n is a prime number.
For $k, i, j \in \{1,2, \cdots, n\}$ $$A_k(i, j) = [k \cdot (i-1) + (j-1)] \mod n$$ - What if n is an odd number? How to proceed then?
- I have read that for the software testing, n is determined this way: n>=m number of values) and n-1>=number of parameters. So I need a latin square of size 5 if there are 4 parameters where some have 5 values. In the algorithms I have seen so far, k had the same value as n but in the end, only n-1 squares were produced. How is k determined then?
- I understood that for n>2 and n <> 6 these MOLS always exist. But I assume that is only when n is a prime number.
For $A_k$ and $A_{k'}$ to not be orthogonal, we must have $$(A_k[i,j],A_{k'}[i,j])=(A_k[i',j'],A_{k'}[i',j'])$$ by definition. Equivalently, by definition of $A_k$, $A_{k'}$, \begin{align*} ki+j &\equiv ki'+j' \pmod n, \text{ and} \\ k'i+j &\equiv k'i'+j' \pmod n \end{align*} which is equivalent to \begin{align*} k(i-i') &\equiv j'-j \pmod n, \text{ and} \\ k'(i-i') &\equiv j'-j \pmod n. \end{align*} Subtracting these gives $(k-k')(i-i') \equiv 0 \pmod n$, and since $n$ is prime and $k \neq k'$, we must have $i \equiv i' \pmod n$, i.e., $i=i'$. Substituting $i=i'$ into the above equations implies $j=j'$. So $A_k$ and $A_{k'}$ are orthogonal.
Do we need $n$ to be prime for this to work? Not really; it's just easier if it is prime. We need $k$ and $k'$ to be coprime to $n$ (or else $A_k$ or $A_{k'}$ will not be a Latin square) and the proof above shows we need $k-k'$ to be coprime to $n$ for orthogonality. For prime $n$, this gives $n-1$ mutually orthogonal Latin squares. Here's an example for non-prime $n=9$, with $k=5$, and $k'=7$: $$ \begin{bmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 5 & 6 & 7 & 8 & 0 & 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 0 \\ 6 & 7 & 8 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 6 & 7 & 8 & 0 & 1 \\ 7 & 8 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 4 & 5 & 6 & 7 & 8 & 0 & 1 & 2 \\ 8 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 5 & 6 & 7 & 8 & 0 & 1 & 2 & 3 \\ \end{bmatrix} \qquad \begin{bmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 7 & 8 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 6 & 7 & 8 & 0 & 1 & 2 & 3 & 4 \\ 3 & 4 & 5 & 6 & 7 & 8 & 0 & 1 & 2 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 0 \\ 8 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 6 & 7 & 8 & 0 & 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 6 & 7 & 8 & 0 & 1 & 2 & 3 \\ 2 & 3 & 4 & 5 & 6 & 7 & 8 & 0 & 1 \\ \end{bmatrix} $$
It is not possible to get $n$ mutually orthogonal Latin squares or order $n \geq 2$, so $n-1$ is the theoretical maximum (but this is not always achieved, e.g. when $n=6$).
It's a famous result that pairs of orthogonal Latin squares exist for orders $n \in \{1,2,\ldots\} \setminus \{2,6\}$ and don't exist for $n \in \{2,6\}$. A random example for non-prime order $4$: $$ \begin{bmatrix} 2 & 3 & 1 & 4 \\ 1 & 4 & 2 & 3 \\ 4 & 1 & 3 & 2 \\ 3 & 2 & 4 & 1 \\ \end{bmatrix} \qquad \begin{bmatrix} 2 & 4 & 1 & 3 \\ 3 & 1 & 4 & 2 \\ 4 & 2 & 3 & 1 \\ 1 & 3 & 2 & 4 \\ \end{bmatrix} $$