# Find if there is matrix that satisfying the following conditions

Given a matrix $$A_{n\times n} = \{a_{ij}\}$$ such that $$a_{ij}$$ is a non-negative number and given 2 vectors $$(r_1,r_2,...,r_n)$$ , $$(c_1,c_2,...,c_n)$$ such that $$r_i,c_i\in \mathbb{Z}$$ define an efficient algorithm that will determine if there's a matrix $$B_{n\times n} = \{b_{ij}\}$$ , $$b_{ij} \in \mathbb{Z}$$ and

for every $$1\leq i \leq n \sum b_{ij} = r_i$$

for every $$1\leq j \leq n \sum b_{ij} = c_j$$

and

$$0 \leq b_{ij} \leq a_{ij}$$

Thought something with dynamic programming but didn't manage to solve it.

• $b_{ij} \leq a_{ij}$ is where they are used. Since your constraints are all linear, do you mean an algorithm more efficient than linear programming? – Seb Destercke Jan 10 at 6:53
• Linear programming does not help a lot here since you are looking for integers. Unless you can prove that the polytope of this problem is integral.. – narek Bojikian Jan 10 at 6:56
• However, total unimodularity of the constraint matrix can be doable. I did not say it is not the case. Write down the LP formulation and look-up the proof of unimodularity of the incidence matrix of bipartite graphs. This should be a similar proof (if it was unimodular) – narek Bojikian Jan 10 at 7:08
• Such matrices are known as contingency tables, and even when $a_{ij} = \infty$, counting them is #P-hard, even for only two rows! – Yuval Filmus Jan 10 at 10:53
• @narekBojikian Same issue as with perfect matchings (which is a special case). Counting is hard, determining if any exists is easy. – Yuval Filmus Jan 10 at 11:23

Imagine $$r_i$$ units of flow entering the $$i$$th row, and $$c_j$$ units of flow leaving the $$j$$th column. Does that give you any hints how to set up the graph for a network flow problem?