Take any $n\times n$ Latin square, $L_n$, and count the number of swaps needed to order each row, and sum them together to get $S_n$. By number of swaps, I refer to this algorithm or similar. Question: What is the minimum and maximum value of $S_n$ for a given $n$?
My intuition says that the minimum is when the main diagonal is all $1$, and one row contains the ordered permutation $1\,2\,3\,…\,n$. But how can we get an exact number? And I'm unsure about the maximum.
Best Answer
Let $m(n)$ be the minimum number of swaps, and $M(n)$ be the maximum. Here is what I know:
$M(n)=(n-1)^2$.
$m(n)\ge n(n-1)/2$.
$m(n)=n(n-1)/2$ when $n=2^k$ for some $k\in \mathbb N$.
Proof of $M(n)=(n-1)^2$.
$(n-1)^2$ swaps are necessary for the Latin square whose $i^{th}$ row, for $i\in \{1,\dots,n\}$, is $$\begin{bmatrix}i&i+1&\dots&n&1&\dots&i-1\end{bmatrix}$$
To see this many swaps always suffice, suppose that row number $i$ has $k_i$ elements in their correct places, for $i\in \{1,\dots,n\}$. Then the number of swaps it takes to sort the $i^{th}$ row is at most $n-k_i-1$, except when $k_i=n$, where the number is $n-k_i=0$. This is because each swap can always put at least one more entry in its correct spot, and the last swap always swaps two entries to their correct places.
Furthermore, we have that $\sum_{k=1}^n k_i=n$, since there is exactly one correctly placed number in each column of the initial Latin square. Therefore, $$ \sum_{k=1}^n (n-k_i-1)=n(n-1)-\sum_{i=1}^nk_i=n(n-1)-n=n^2-2n, $$ except if one of the $k_i$ is equal to $n$, in which case we must add an extra $1$ to account for the exception, resulting in $$ n^2-2n+1=(n-1)^2. $$
Proof of $m(n)\ge n(n-1)/2$.
As argued previously, the initial latin square has exactly $n$ entries in their correct positions. Since each swap puts at most $n-2$ entries in their correct positions, it follows that at least $n(n-1)/2$ swaps are necessary.
Furthermore, when $n=2^k$ is a power of $2$, this minimum is attainable. Identify $\{1,\dots,n\}$ with the group elements of $(\mathbb Z/2\mathbb Z)^k$. The Cayley table of this group is a Latin square which achieves this number of swaps. Indeed, the row corresponding to the identity is already sorted, while the other rows break into $n/2$ pairs of swapped entries, so can each be sorted with $n/2$ swaps.