Upper bound on number of pairwise 'coupled' 'full' matrices of order $n$

Question

Let us define a 'full' matrix of order $n$ as a square array of numbers such that each row and column contains all the numbers from 1 to $n$. Given such a matrix $A$ we indicate the element in the $i^{th}$ row and $j^{th}$ column as $a_{ij}$. Furthermore, we say two such matrices $A, B$ of order $n \geq 3$ are 'coupled' if all the pairs $(a_{ij}, b_{ij})$ are distinct for all $1\leq i, j \leq n$. For example, taking $n=3$, the following two matrices are 'coupled' \begin{bmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \\ 2 & 3 & 1 \end{bmatrix}
as the generated pairs are respectively $(1, 1), (2, 2), (3, 3), (2, 3), (3, 1), (1, 2), (3, 2), (1, 3), (2, 1)$. The question is to find an upper bound $c(n)$ for the number of 'full' matrices of order $n$ that are pairwise 'coupled'. By testing small $n$ by hand I have come to the conjecture that $c(n) = n-1$, but I am not able to prove it. Does anyone have any ideas?

Answer 1

You are correct that $n-1$ is an upper bound. Here is an outline of a proof, with gaps for you to fill in.

1. Given a full matrix $A$, and a permutation $\pi$ of $\{1,\dots,n\}$, you can form a new full matrix $\pi(A)$ by applying $\pi$ to each entry of $A$. First, you should prove that if $A$ and $B$ are coupled, then $\pi(A)$ and $B$ are coupled as well.

2. Secondly, use the previous step to show that every family of pairwise coupled full matrices can be put in "standard form," meaning the first row of each matrix is $[1,2,\dots,n]$ in that order.

3. Once the family $A_1,A_2,\dots,A_k$ is in standard form, let $x_i$ denote the entry in the second row, first column of $A_i$. Every matrix in the family looks like this: $$ A_i=\begin{bmatrix} 1&2&3&\cdots&n\\ x_i &&&\dots\\ \vdots&&&\ddots \end{bmatrix} $$ What must be true about the numbers $x_1,x_2,\dots,x_k$? Use this to conclude $k\le n-1$.

Furthermore, you can show that this upper bound cab ne obtained whenever $n$ is a prime power. If $n$ is prime, this is not too hard to do using matrices defined with arithmetic modulo that prime. When $n$ is a prime power, you instead have to use finite field arithmetic.

---

In case you are not aware, a "full matrix" is usually called a Latin square, "coupled" matrices are usually called orthongal, and a family of pairwise coupled full matrix is called an MOLS, short for mutually orthogonal Latin squares.