Given a row sum vector and a column sum vector, determine if they can form a boolean matrix

Question

For example, for a boolean matrix of size $3x4$, the column sum vector $C = (3, 3, 0, 0)$ and the row sum vector $R = (2, 2, 2)$ form a match because I can construct the boolean matrix:

$$ \begin{matrix} & \begin{bmatrix} 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0 \end{bmatrix} & \begin{pmatrix} 2\\2\\2 \end{pmatrix} = R \\ C = &\begin{pmatrix} 3 & 3 & 0 & 0 \end{pmatrix} \end{matrix} $$

However, the row sum vector $R' = (4, 1, 1)$ doesn't form a match with $C$.

So given two vectors whose values are sorted in a non-increasing order $C_w$ and $R_h$, and whose accumulated sum is the same, $T = \sum_jc_j = \sum_ir_i$, how can I polynomically check if $C$ and $R$ form a matching because I can form a matrix $M_{h,w}$ having $C$ and $R$ as colum and row sum vectors respectively?

More specifically, in case it can help to make the check algorithm faster, in my specific case, C and R has the following properties:

• $h \leq w$
• The number of positive values of $R$ and $C$ is $> w$. For example, $C$, in the example, has two positive values and $R$ has three positive values, and it happens that $2 + 3 > w = 4$.

Answer 1

This problem is known as discrete tomography, and in your case two-dimensional discrete tomography. A nice approachable introduction is written Arjen Pieter Stolk's thesis Discrete tomography for integer-valued functions in Chapter 1. It gives a simple greedy algorithm for solving this problem:

While the proof of theorem (1.1.13) is somewhat involved, the reconstruction algorithm that comes out of it is actually quite easy. It proceeds one column at a time, starting with a column whose sum is the highest and working in order down to the lowest column sum. In each column, we place the 1’s in those rows where with the largest number of 1-positions left, that is, such that the row sum minus the number of 1’s already filled in is the largest.

Answer 2

Based on the, apparently famous paper on the field, Ryser 56, and the thesis recommended by @orlp, the test to know if a row and column sum vectors forms a match, e.g., a matrix $M_{h,w}$ exists having these row and column sum vectors, is the following one:

• Let $R_h$ be a vector of $h$ elements sorted in a non-increasing order ($r_1\geq r_2\geq\ldots\geq r_h$).
• Let $C_w$ be a vector of $w$ elements sorted in a non-increasing order ($c_1\geq c_2\geq\ldots \geq c_w$).

Is there exists a matrix $M_{h,w}$ with $h$ rows and $w$ columns having $R$ and $C$ as row sum and column sum vectors respectively? We say that $R$ and $C$ form a match if such $M$ exists (this definition of matching is mine because it helps me explaining).

[Note: The restriction of $R$ and $C$ being sorted is to simplify the test. If $R$ and $C$ are not sorted, but their sorted versions forms a match because they can form a matrix $M$, then $R$ and $C$ form a match because you can always reorder the rows and columns of $M$ so their column and row sum vectors equals $R$ and $C$. $-$ end note]

Given ($\#$ means size of the set, in case you don't know, because I didn't):

$$ \tag{1} \begin{matrix} C^* = \begin{bmatrix}c^*_1&\ldots&c^*_w\end{bmatrix}, & c_j^* = \#\{\ i\ |\ r_i\geq j\} & \forall j\in[1, w] \end{matrix} $$

The conditions for $M_{h,w}$ to exists are:

$$ \tag{2} \sum_{i=1}^hr_i = \sum_{j=1}^wc_j $$

$$ \tag{3} \forall i\in [1,h], r_i \leq w $$

$$ \tag{4} \forall j\in[1, w], c_j \leq h $$

$$ \tag{5} C\prec C^* $$

• Equation $(2)$ means that $R$ and $C$ must both count the number of $1$s in the to-be-determined matrix $M$, and so both sums must match. Otherwise $M$ doesn't exist.

• Equation $(3)$ and $(4)$ combined means that both $R$ and $C$ must reflect the fact that no row or column of $M$ can have more $1$s than the width or height of $M$ respectively. Otherwise $M$ doesn't exist.

• Equation $(5)$ is the core of the test. Let's me explain it step by step. In his paper, Ryser starts by creating a "maximal form of $M$", which is an intermediary matrix $M^*_{h,w}$ where each row $i$ has, starting from the beginning of the row, as many contiguous $1$s as indicated by $r_i$. Once that has been done, $C^*$ is just the column sum vector of $M^*$. For example, for a $3\times 4$ matrix $M$ with $R = (3, 3, 1)$, the maximal form of $M$ would be:

$$ \begin{matrix} & M^* = &\begin{bmatrix} 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 0\\ 1 & 0 & 0 & 0 \end{bmatrix} & \begin{pmatrix} 3\\3\\1 \end{pmatrix} = R \\ &C^* = &\begin{pmatrix} 3 & 2 & 2 & 0 \end{pmatrix} \end{matrix} $$

Afterwards, he proves that he can construct $M$ from $M^*$ by moving $1$s around only within their own rows (to don't alter $R$) to make $C^*$ become $C$, provided that $C^*$ majorizes $C$, which is precisely the equation $(5)$. Otherwise $M$ doesn't exist. Notice that, if $R$ and $C$ forms a match, there could exist more than one matrix having $R$ and $C$ as sum vectors.

The equation $(1)$ seems to have been originally introduced by Arjen Stolk in the thesis given above, and it's just a direct way of getting $C^*$ without having to construct $M^*$.

Equation $(1)$ simply means, counting, per column $j$, how many rows of $M$ have same or more $1$s than the column index itself (how many $r_i\geq j$). Notice that $C^*$ is already sorted, otherwise majorization woudn't be defined (actually, before proving that $C\prec C^*$ is all you need, Ryser first prove, because of the way $M^*$ is defined, that $C^*$ is already sorted in a non-decreasing fashion).