Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $R_1,\ldots,R_n$ and $C_1,\ldots,C_n$ be sets of size n.

When does there exist an $n \times n$ matrix in which the $i$-th row is a permutation of $R_i$, for all $1 \leq i \leq n$, and the $j$-th column is a permutation of $C_j$, for all $1 \leq j \leq n$?

Easy observations:

  • A Latin square is an example when $R_1=\ldots=R_n=C_1=\ldots=C_n$. (So this is indeed a generalisation of the existence problem for Latin squares.)
  • The multiset $\cup R_i$ equals the multiset $\cup C_i$.

The motivation for this question comes from a Latin square completion problem. If we have a $2n \times 2n$ partial Latin square with the structure:

\begin{array}{|cc|} \hline A & \emptyset \\\\ \emptyset & B \\\\ \hline \end{array}

where $A$ and $B$ are $n \times n$ matrices, and $\emptyset$ represents $n \times n$ empty blocks. When does such a partial Latin square complete?

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.