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