# Given a row sum vector and a column sum vector, determine if they can form a boolean matrix For example, for a boolean matrix of size $$3×4$$, the row sum vector $$R = (3, 3, 0, 0)$$ and the column sum vector $$C = (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} = C \ R = &\begin{pmatrix} 2 & 2 & 0 & 0 \end{pmatrix} \end{matrix}$$

However, the column vector $$C’ = (4, 1, 1)$$ doesn’t form a match with $$R$$.

So given two vectors whose values are sorted in descending order $$R_{1, w}$$ and $$C_{h, 1}$$, and whose accumulated sum is the same, $$T = \sum_jR[1, j] = \sum_iC[i, 1]$$, how can I polynomically check if $$R$$ and $$C$$ form a matching because I can form a matrix $$M_{h,w}$$ having $$R$$ and $$C$$ as row and column sum vectors?

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

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