How to find out if it is possible to contruct a binary matrix with given row and column sums.

Question

How to find out if it is possible to contruct a binary matrix with given row and column sums.

Input :

The first row of input contains two numbers 1≤m,n≤1000, the number of rows and columns of the matrix. The next row contains m numbers 0≤ri≤n – the sum of each row in the matrix. The third row contains n numbers 0≤cj≤m – the sum of each column in the matrix.

Output:

Output “YES” if there exists an m-by-n matrix A, with each element either being 0 or 1. Else "NO".

I tried reading about Tomography algorithms but could not figure out an answer as all the papers related to Tomography algorithm is very complicated.

Can someone please help me..

Answer 1

Look up "network flow" in a linear programming text.

Answer 2

It seems from your description that you don't need to actually compute the matrix, but just insure that the necessary and sufficient conditions exist for one to be computed. For that, I think that all you'll need is J. H. Ryser's paper, "Combinatorial properties of matrices of zeros and ones." You may also find Richard A. Brualdi's paper "Matrices of zeros and ones with fixed row and column vectors" very readable.

Applying those, we first establish some terminology. As you've already said, the matrix ${\bf A}$ is an $m \times n$ (where $m$ and $n$ are positive integers) matrix of ones and zeros. Further, we have row and column sum vectors ${\bf R} = (r_1,\dots,r_m$) and ${\bf S}=(s_1,\dots,s_n)$ which are nonnegative integral vectors. First, it's clear that if there are $\tau$ ones in the matrix ${\bf A}$, then $\displaystyle \tau = \sum_{i=0}^{m}r_i = \sum_{j=0}^{n}s_j$. If that condition fails, then obviously the answer is "no."

If that succeeds, then following Brualdi, we can define a function to help with the evaluation. First, let $I \subseteq \left\{ 1,\dots,m \right\}$ and $J \subseteq \left\{1,\dots, n \right\}$. Define $\displaystyle t(I,J) =|I||J|+\sum_{i \notin I}r_i - \sum_{j \notin J}s_j$. All that remains is to demonstrate that $t(I,J) \ge 0$ for all $I\subseteq\left\{1,\dots,m\right\}$ and $J\subseteq\left\{1,\dots,n\right\}$.