<p>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.</p>

<ol>
<li>Consider such a problem: Given $r$ (row sum) and $c$ (column sum), how to determine whether there is a solution or not?</li>
</ol>

<p>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:</p>

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

<p>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.</p>

<ol>
<li>Consider how to find the answer when some $A_{i, j}$ is determined.</li>
</ol>

<p>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$. </p>

<p>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.</p>

CC BY-SA 3.0
2012-04-30T05:36:46.913Z
Great explanation. This is a great starting point. Now I can focus on improving the time complexity. Thanks for your help.
Special Touch
CC BY-SA 3.0
2012-04-27T18:35:32.230Z
2012-04-27T18:35:32.230Z
Wu Yin
<p>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?</p>

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

<p>$$
 A =
 \begin{bmatrix}
  ? &amp; ? &amp; 1 \\
  0 &amp; 0 &amp; 1 \\
  ? &amp; ? &amp; 1 \\
 \end{bmatrix}
$$</p>

CC BY-SA 3.0
2012-04-26T13:42:26.177Z
Yes: Sort vectors, put ones in left-up corner, unshuffle. Unknowns come from repetitions (and hence multiple ways of unshuffling).
Radu GRIGore
CC BY-SA 3.0
2012-04-26T16:49:46.350Z
Could you elaborate? What's the mechanism for placing ones and for unshuffling? And what about zeros?
Special Touch
<ds.algorithms><co.combinatorics>
Finding invariant elements of binary matrix from row and column sums
Special Touch
# Finding invariant elements of binary matrix from row and column sums

(Asked by: username_0 on 2012-04-26)

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}
$$

**Tags:** ds.algorithms, co.combinatorics
> **Comments:**
> **username_1**: Yes: Sort vectors, put ones in left-up corner, unshuffle. Unknowns come from repetitions (and hence multiple ways of unshuffling).  
> **username_0**: Could you elaborate? What's the mechanism for placing ones and for unshuffling? And what about zeros?  

---

## 1 answers

### Answer by username_2 on 2012-04-27. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: Great explanation. This is a great starting point. Now I can focus on improving the time complexity. Thanks for your help.  

---

