Question

Say, we have a semimagic square $X$, that is, an $n\times n$ square matrix with entries from natural numbers, such that each row and column of it sums up to the same natural number $s$. Let $M$ be a set with $s$ elements. To each $X_{ij}$, we assign a subset $M_{ij}$ of $M$ with $X_{ij}$ elements.

Question: Is it possible to make the assignment in such a way, that for every $i$ we have $\bigcup_j M_{ij} = M$ and for every $j$ we have $\bigcup_i M_{ij} = M$, or equivalently, whenever the cells $X_{ij}$ and $X_{kl}$ lie in the same row or in the same column, then the subsets $M_{ij}$ and $M_{kl}$ are disjoint?

PS1: You may think of $s^2$ different balls, each labeled by a number from ${\left\lbrace 1,\dots,s \right\rbrace}$, such that for each label $l$, there are exactly $s$ balls having label $l$. You have to distribute the balls in the cells of $X$ in such a way, that in each cell $X_{ij}$ there are $X_{ij}$ balls and in each row and column of $X$ we have a whole set of balls labeled from $1$ to $s$.

PS2: To me, the answer to the question seems to be positive. However, the greedy construction idea does not work.

Answer 1

Here is a proof:

The idea is more or less, what Zack is describing, as far as I could understand from his comment.

Every semimagic square can be expressed as a sum of permutation matrices. (This was proven by König in 1915.) So let $P_1,\dots,P_s$ be such permutation matrices. Let $p_1, \dots, p_s$ be the corresponding permutations.

Let w.l.o.g. $M=\left\lbrace 1,\dots,s \right\rbrace$. To each cell $X_{ij}$, we assign the set $\left\lbrace t : p_t(i)=j\right\rbrace \subseteq \left\lbrace 1,\dots,s\right\rbrace$.

And we are done! Very elegant. I liked it. Thanks, Zack!

Answer 2

This is the same answer in different language. Every regular bipartite multigraph of degree $s$ has a proper edge colouring with $s$ colours. Make a bipartite multigraph with $n+n$ vertices, where $X_{ij}$ is the number of edges from vertex $i$ in the first part to vertex $j$ in the second part. This is a regular bipartite graph of degree $s$ and the edge colouring gives the necessary assignments.