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 3ドルx4$, 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$.

• orlp: You wrote $R = (2\ 2\ 0\ 0)$ in your big equation. Typo?

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.

• ABu: I don't actually want to reconstruct the matrix. Actually, there could be multiple matrices with same row and column sum vectors, even non-isomorphic under row and column swappings. I only want to know whether "they match" without having to reconstruct a matrix and see whether the algorithm doesn't fail.
• orlp: @Peregring-lk Read Chapter 1.1 of the thesis. It covers all your questions.
• ABu: Thank you very much. Using that I have write my own answer (although I believe the proof given in the thesis have a typo or something because something didn't make sense to me).

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).