We have two vectors: $(a_1,...,a_n),(b_1,...,b_m)$.
We want to know if there is a matrix $M_{nm}$ that all its elements are from $\left\{0,1\right\}$ with this condition:
The sum of all the elements at the the $j$-row is $b_j$ and the sum of all the elements at the $i$-column is $a_i$.
Now, the question is: what is the algorithm that returns true if there is a matrix describe above - otherwise the algorithm return false...
I think that the problem can be solve by a bipartite graph, and by a flow network...
I'd like to get any help!
Thank you!
edit:
I think I got an idea:
It's possible only if $$\sum_{i=1}^n a_i = \sum_{j=1}^m b_j$$
I'm right? Because otherwise it impossible to build the bipartite graph (with the rank of each vertex...).
And, if we counting the number of the 1's by row or by column it should be the same number...
(If it's true i'd like to get help with the proof...)
It seems to me that by interchanging the columns of $M$ we can assume $0 \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq m $. Then by interchanging the rows we can assume also $n \geq b_1 \geq b_2 \geq \cdots \geq b_m \geq 0$. So if I am not wrong we have two partitions of the number $N = \sum_i a_i = \sum_j b_j$ and this two partitions are so called conjugated or dual partitions see http://en.wikipedia.org/wiki/Partition_%28number_theory%29#Ferrers_diagram
So if I am not doing a silly mistake the necessary and sufficient conditions on the ordered sequences $(a_1,\cdots,a_n),(b_1,\cdots,b_m)$ for the existence of such matrix $M$ are:
1) $\sum_i a_i = \sum_j b_j = N$
2) the ordered sequences must satisfies the inequalities $n \geq b_1 \geq b_2 \geq \cdots \geq b_m \geq 0$ and $0 \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq m $
3) the ordered sequences must be conjugated partitions.