Covering pairs with permutations
Consider an $n \times n$ matrix $M_n$ with the following properties:
- Each row is a permutation of $A_n \equiv \{1, 2, ..., n\}$.
- Every ordered pair $(i,j)$, $i,j \in A_n$, $i \neq j$, appears as a horizontally adjacent pair in $M_n$ exactly once (which works out since there are $n(n-1)$ such pairs).
Together with user Sp3000 we've ran some automated search for these matrices. It seems that solutions are not possible for all $n$. Here are some working cases (of course, these are not unique):
$$ M_1 = \left(\begin{array}{c} 1 \end{array}\right) \\ M_2 = \left(\begin{array}{cc} 1 & 2 \\ 2 & 1 \end{array}\right) \\ M_4 = \left(\begin{array}{cccc} 1&2&3&4\\2&4&1&3\\3&1&4&2\\4&3&2&1\end{array}\right) \\ M_6 = \left(\begin{array}{cccc} 1&2&3&4&5&6\\2&1&3&6&5&4\\3&1&4&6&2&5\\4&2&6&1&5&3\\5&1&6&4&3&2\\6&3&5&2&4&1\end{array}\right) $$
We also have solutions for all further $n$ up to and including $26$. However, we've verified that no solutions exist for $n = 3$ and $n = 5$. So the interesting question is: for which values $n$ does at least one $M_n$ exist? Are $3$ and $5$ the only exceptions? When solutions do exist, can one of them be constructed from some obvious pattern or do they always have to be searched for?
A few additional observations on our part:
- This problem has an equivalent formulation in graph theory. For the complete digraph $K_n$ can you find a set of $n$ (edge disjoint) Hamiltonian paths whose union covers all edges?
- The first and last column of the matrix are necessarily permutations of $A_n$ as well.
- If we remove the constraint that the individual rows are permutations, then $n = 3$ has solutions, e.g. $(121, 232, 313)$, as does $n = 5$.
Final note: I actually have an application for this problem. I came across this question while trying to devise test cases for a programming challenge where I wanted to cover all possible cases in as few lists as possible (with $n$ lists of length $n$ being the minimum).
A square with the given properties is called a Tuscan square (because of the similarity to the more well-known Latin squares. A Tuscan square is also known as a row-complete Latin square, and one whose transpose is also Tuscan is a complete Latin square).
A Tuscan square for even $n$ can be found by taking an decomposition of the complete undirected graph $K_n$ into $n/2$ Hamilton paths and then reading each path forwards and backwards. A suitable construction dates to the 19th century and is credited to Walecki.
The case of odd $n$ was settled in 1980 by Tillson in A Hamiltonian decomposition of $K_{2m}*$, $2m \ge 8$, J. Combinatorial Theory, Series B, 29.1. (If the title doesn't seem to match the claim, note that a decomposition of a graph of size $n$ into Hamiltonian paths and a decomposition of a graph of size $n+1$ into Hamiltonian cycles are equivalent, and the latter is what is meant by a Hamiltonian decomposition).
So the short answer is: 3 and 5 are the only exceptions.
There are many constructions, often based around group theory. Ollis, Sequenceable Groups and Related Topics, Electronic J. Combinatorics 20.2 (2013) would be a good starting point if you want to read more broadly than just the Walecki and Tillson constructions.