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

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.

share|improve this question
3  
Why not do this by induction on $s$? It's true if every entry is $1$, and if they are not all $1$, then you can find a set of $n$ entries, one from each row and column, which are all greater than $1$ (consider the labels of Latin squares and use pigeonhole principle). Assign the same single element to each of those, and you've reduced $s$ by $1$. –  Zack Wolske Feb 14 '13 at 1:03

2 Answers 2

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!

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.