Finding invariant elements of binary matrix from row and column sums

Question

Consider a m-by-n binary matrix A. Given only an m-dimensional vector of its row sums (R) and an n-dimensional vector of its column sums (C), is there an efficient (ie. polynomial time) algorithm that determines which elements of A must be 1 and which elements of A must be 0?

A trivial example: if R = {2,1,2} and C = {1,1,3}, then

$$ A = \begin{bmatrix} ? & ? & 1 \\ 0 & 0 & 1 \\ ? & ? & 1 \\ \end{bmatrix} $$

Answer 1

The answer is yes. The basic idea is to determine whether there is a matrix $A$ with $A_{i, j} = 0$ and one with $A_{i, j} = 1$. If both answers are yes, then $A_{i, j}$ cannot be determined. otherwise you will know what it is.

1. Consider such a problem: Given $r$ (row sum) and $c$ (column sum), how to determine whether there is a solution or not?

This problem can be solved by network flow algorithm. Imagine a bipartite graph $G$ whose two disjoint vertex sets are $S$ and $T$. Each vertex in $S$ corresponds to a row in $A$ (so $|S| = n$), and each vertex in $T$ corresponds to a column in $A$ (so $|T| = m$). The network $N$ can be constructed as follows:

• Add edge between source and each $s_i$ in $S$ with capacity $r_i$.
• Add edge $E_{i, j}$ between each node $s_i$ in $S$ and $t_j$ in $T$ with capacity $1$.
• Add edge between each $t_j$ in $T$ and sink with capacity $c_j$.

Find the maxflow in $N$. All edges form source are full iff there is a binary matrix A whose row sum is $r$ and column sum is $c$. And flow in $E_{i, j}$ equals to the value of $A_{i, j}$. It can be found in poly time.

1. Consider how to find the answer when some $A_{i, j}$ is determined.

We can also construct a network $N$ as above and change the upper and lower bound of corresponding $E_{i, j}$. If you want to find whether there is solution with $A_{i, j} = v$, you can change the upper and lower bound to $v$. You should run this algorithm $2nm$ times to find whether each $A_{i, j}$ can be $0$ or $1$.

PS: The first problem can also be solved by a theorem called "Gale-Ryser Theorem". But I've no idea how to modify it to solve the second one.