2
$\begingroup$

I have a Boolean matrix (entries are "0" or "1"), which is not square. The sum over each row and each column is constant (but they can be two different values). I would like to find the minimum number of rows such that the sum over each column of the new submatrix is positive (even if is not constant)

I call Aj the j-th row of the matrix A. For example I set the problem for a Boolean matrix A with 6 rows and 4 columns.

$$A=\pmatrix{1&1&0&0\cr1&0&1&0\cr0&1&1&0\cr1&0&0&1\cr0&1&0&1\cr0&0&1&1\cr}$$

The sum of the entries in each column is 3 (the same if we sum over the rows). If we delete the first three rows we get a submatrix such that the sum of the elements of each column is the vector {1,1,1,3}, and if we delete one of the three remaining rows (row 4,5 or 6) there will be at least a column where the sum is 0. For this reason, the sub matrix composed by the rows [A4;A5;A6] is a candidate to solve the problem. However, the submatrix composed by the two rows [A2,A5] is the optimal solution of the problem in this case. I would like to find a rule (or an algorithm ) to find the minimum number of rows in the general case.

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ Hi, if you consider each row to be a set of indices (indices of non zero entries) then I think your problem is a set cover problem which is NP complete for the general case. en.wikipedia.org/wiki/Set_cover_problem There should be heuristic approaches which might help you. $\endgroup$
    – nahila
    Commented Dec 29, 2021 at 13:12
  • 1
    $\begingroup$ The case of this problem when the matrix is not square reduces to the case when the matrix is square. If $A$ is an $m\times n$-matrix where each entry is $0$ or $1$, then let $N_{n,m}$ be the $n\times m$-matrix where each entry is $1$. Then the tensor product $A\otimes N_{n,m}$ will be an $mn\times mn$-matrix where each entry is $0$ or $1$ and where the minimum number of rows needed for each column to have a positive sum is the same for both $A$ and $A\otimes N_{n,m}$. $\endgroup$
    – Joseph Van Name
    Commented Dec 29, 2021 at 16:04
  • 1
    $\begingroup$ The case when the matrix $A$ is square and the sum of each row and column is 2 is solvable. Write $A=\rho(f)+\rho(g)$ where $f,g$ are permutations and $\rho(f),\rho(g)$ are their corresponding permutation matrices. Then $fg^{-1}$ has no fixed point. Suppose that $fg^{-1}$ has cycles of lengths $n_{1},\dots,n_{r}$. Then one will need precisely $\sum_{k=1}^{r}2\lceil n_{k}/2\rceil$ many rows in the submatrix in order for the sums of the columns in the submatrix to all be positive. $\endgroup$
    – Joseph Van Name
    Commented Dec 29, 2021 at 16:13
  • 1
    $\begingroup$ Let's use probabilistic methods to compute upper bounds for the number of rows that you need. Suppose that $A$ is an $m\times n$-matrix where each entry is $0$ or $1$, the sum of each column is $\frac{d}{n}$ and the sum of each row is $\frac{d}{m}$. Then there are $d$ non-zero entries. Choose $r$ rows at random and independently (by independence the rows can be the same). Then the probability that column $i$ in the submatrix has sum $0$ is $(1-\frac{d}{nm})^{r}$. $\endgroup$
    – Joseph Van Name
    Commented Dec 29, 2021 at 19:27
  • 1
    $\begingroup$ Therefore, the probability that there exists a column in the submatrix with sum $0$ is at most $n(1-\frac{d}{nm})^{r}$. If $n(1-\frac{d}{nm})^{r}<1$, then we know that each column in the submatrix has sum at least $1$. By solving for $r$, we know that if $r>\frac{\ln(n)}{\ln(mn)-\ln(mn-d)}$, then there is a submatrix obtained by taking $r$ rows where the sum of each column in this submatrix is greater than $0$. $\endgroup$
    – Joseph Van Name
    Commented Dec 29, 2021 at 19:28

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .