4
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ You wrote $R = (2\ 2\ 0\ 0)$ in your big equation. Typo? $\endgroup$ – orlp Sep 15 at 21:25
  • $\begingroup$ @orlp Yes thanks. $\endgroup$ – Peregring-lk Sep 15 at 21:36
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Peregring-lk Sep 16 at 10:00
  • 1
    $\begingroup$ @Peregring-lk Read Chapter 1.1 of the thesis. It covers all your questions. $\endgroup$ – orlp Sep 16 at 10:22
  • $\begingroup$ 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). $\endgroup$ – Peregring-lk Sep 18 at 18:05
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.