Timeline for How to delete the maximum number of rows of a Boolean matrix by maintaining the sum greater than zero in each column
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 29, 2021 at 19:28 | comment | added | Joseph Van Name | 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$. | |
| Dec 29, 2021 at 19:27 | comment | added | Joseph Van Name | 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}$. | |
| Dec 29, 2021 at 16:13 | comment | added | Joseph Van Name | 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. | |
| Dec 29, 2021 at 16:04 | comment | added | Joseph Van Name | 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}$. | |
| Dec 29, 2021 at 14:29 | comment | added | Gerry Myerson | $A_2,A_5$ is an optimal solution, not the optimal solution – $A_1,A_6$ is just as good, as is $A_3,A_4$. | |
| Dec 29, 2021 at 14:27 | history | edited | Gerry Myerson | CC BY-SA 4.0 |
formatting
|
| Dec 29, 2021 at 13:12 | comment | added | nahila | 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. | |
| S Dec 29, 2021 at 11:17 | review | First questions | |||
| Dec 29, 2021 at 11:29 | |||||
| S Dec 29, 2021 at 11:17 | history | asked | Andrea | CC BY-SA 4.0 |