Given a square matrix of order n (no elements are defined yet), some entries are marked, so that every row and column has k (k<n) marked entries. Is it possible to define an integer from 1 to k on every marked entry so that any row or column has every number exactly once?
I cannot post images yet (my first post), so here is an written-table example with n=5 and k=3 (marked entries as underlines):
x _ _ x _
x x _ _ _
_ _ _ x x
_ x x _ _
_ _ x _ x
The solution exists in this case (there are 36, but existence of one is enough):
x 3 2 x 1
x x 3 1 2
3 2 1 x x
1 x x 2 3
2 1 x 3 x
Or, equivalently: given a table with pre-defined positions in the same quantity for any row or column, can I always find a way to put permutations in the rows and columns at the same time?
Seems to be a classic problem, but I could not find any demonstration.
This problem arises from trying to put teachers in classrooms. Many classrooms have the same teachers, so if I can only look at quantities first, then maybe the distribution becomes easier. It depends on the solution of the above table problem.
Best Answer
Yes, it is.
The marked entries correspond to edges of a bipartite graph with $n$ vertices in each part, all with degree $k$. You want to colour the edges with $k$ colours, so no edges of the same colour share a vertex.
Using Hall's marriage theorem, the graph has a perfect matching.
Colour the corresponding edges with one colour and consider the graph with those edges removed. This is now a bipartite graph of $n$ vertices, all of degree $k-1$. Use induction.