1
$\begingroup$

Let $M$ be an $n\times m$ matrix. For a subset $S$ of $\{1,\ldots,n\}$ let $M(S)$ be the submatrix of $M$ with row indices in $S$.

I would like to find an $S$ of smallest size such that $M(S)$ has the same number of distinct columns as $M$. Can anyone suggest a good approach to this problem? Does the problem have a name? Has it been considered somewhere?

Specifically I have a $431\times 2977$ matrix $M$ with 270 distinct rows and 2926 distinct columns. I have been able to find 40 rows such that the submatrix with those rows also has 2926 columns. Is there a smaller set of rows?

The matrix can be found at

http://shell.cas.usf.edu/~saito/QuandleColor/rig_1to35_maple_matrix_april7.txt

in case anyone wants to take up the challenge to do better than 40.

  • 0
    You are right. I thought my algorithm is able to find out the optimal solution, but actually it cannot.2011-08-02

0 Answers 0