Disjoint perfect matchings in complete bipartite graph Let $K_{n,n}$ be a complete bipartite graph with two parts $\{u_1,u_2,\ldots,u_n\}$ and $\{v_1,v_2,\ldots,v_n\}$, and let $K^-_{n,n}$ be the graph derived from $K_{n,n}$ by delete a perfect matching $\{u_1v_1,u_2v_2,\ldots,u_nv_n\}$.
Since $K^-_{n,n}$ is now $(n-1)$-regular, it has $n-1$ disjoint perfect matchings. My question is whether the edges of $K^-_{n,n}$ with $n\geq 4$ can be decomposed into $n-1$ disjoint perfect matchings in such a way that in each matching $M$, if $u_iv_j\in E(M)$ then $v_iu_j\not\in E(M)$.
 A: The answer is that this is possible for all $n>4$.
Your question is equivalent to asking whether there exists a unipotent Latin square $L$ of order $n$ with $L_{ij}\ne L_{ji}$ for $i\ne j$. The equivalence is obtained by using $L_{ij}$ to record the index of the matching that contains the edge $u_i v_j$ (and putting $L_{ii}=n$ for each $i$).
The existence of such a Latin square follows from a stronger property. It is a theorem (collectively due to the work of Kotzig, McLeish, Turgeon and others) that for all $n\notin\{2,4\}$ there exists a Latin square of order $n$ that has no intercalates (an intercalate is a $2\times2$ submatrix that is itself a Latin square). This property of Latin squares is called $N_2$ in the literature.
If you permute the rows of any $N_2$ Latin square you can make every symbol on the main diagonal equal to $n$. You then have what you need.
A: For fixed $n$, you can solve the problem via integer linear programming as follows.  For edge $(i,j)\in E$ and matching $k\in\{1,\dots,n-1\}$, let binary decision variable $x_{i,j,k}$ indicate whether edge $(i,j)$ appears in matching $k$.  The constraints are
\begin{align}
\sum_k x_{i,j,k} &= 1 &&\text{for all $(i,j)$} \tag1\\
\sum_{(i,j)\in E} x_{i,j,k} &= 1 &&\text{for all $i$ and $k$} \tag2\\
\sum_{(i,j)\in E} x_{i,j,k} &= 1 &&\text{for all $j$ and $k$} \tag3\\
x_{i,j,k} + x_{j,i,k} &\le 1 &&\text{for all $(i,j)$ and $k$} \tag4\\
x_{1,j,j-1} &= 1 &&\text{for $j\in\{2,\dots,n\}$} \tag5
\end{align}
Constraint $(1)$ enforces one matching per edge.
Constraint $(2)$ enforces one edge per left node and matching.
Constraint $(3)$ enforces one edge per right node and matching.
Constraint $(4)$ prevents edges $(i,j)$ and $(j,i)$ from appearing in the same matching.
Constraint $(5)$ is optional and breaks symmetry.
The problem is infeasible for $n\in\{2,4\}$ and feasible for $n\in\{1,\dots,40\}\setminus\{2,4\}$.
