Let $\{v_j\}_j$ be a collection of $n$ column vectors $v_j \in \mathbb{F}_2^{r}$ s.t. the matrix built from those has no zero rows.
Now we play a game: You have 3 options:
- You may drop any column vectors if the resulting matrix still has no zero rows
- You may drop any number of column vectors if their 'ones' are disjoint and replace them by their sum, that is you may drop the columns $$ \begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} \quad \text{ and replace them by } \quad \begin{pmatrix} 1 \\ 1 \\ 0 \\ 1 \\ 1 \end{pmatrix}. $$
- You may also add columns whose ones are not disjoint and append the set of column vectors by the result. But the resulting vector has (by definition!) the entry "$\square$" at every row where you added two (or more) ones and you are not allowed to use a $\square$ to deduce that a row is not a zero row. For instance, you may add the column vectors $$ \begin{pmatrix} 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \end{pmatrix} \quad \text{ and append the result } \quad \begin{pmatrix} \square \\ 1 \\ 1 \\ \square \\ \square \end{pmatrix} $$ which my not be convinient. But consider the case $$ \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 0\\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} \quad \text{ where adding the last four vectors results in } \quad \begin{pmatrix} \square \\ 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} $$ and then you may take as a result the first vector and the resulting one.
The aim is to produce a new collection such that the corresponding matrix has no zero rows, and, of course, to do this in a way ending up with at least as possible vectors.
My questions:
- What is the minimal number of columns (in dependence on $r$ and $m$) you are able to produce playing this game for arbitrary $\{v_j\}_j$?
- Are you able to come up with a matrix/collection which proves that there is a worst (bas) case (implying that there is an upper bound for the minimal number for the general case)?
If you are able to prove that there is always a way to produce a column vector with more ones than anything else, then you can choose that vector and only consider the submatrix given by the row indices of it not containing a one. This matrix has less than half the number of rows of the original one. This should end up in a logarithmic dependence on the number of rows.
Edit:
If we are able to prove that there is always a way to construct a column with at least $\lceil r/2 \rceil$ many 1, then we can delete the rows where the considered column has a 1 and then continue with the rest of the matrix. This will then definitely end up with a logarithmic (in dependence on $r$) number of column vectors!