# Minimize submatrix having the same number of distinct columns as given matrix

Let M be an n by m matrix. For a subset S of {1,...,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 by 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.

-
Strange. This seems like a simple sorting problem. I also found 2926 distinct columns, but with 79 rows instead of 40. The indices of the 79 rows I found are: 36, 49, 68, 83, 84, 85,106,112,113,114,115,116, 120,130,131,138,142,144,146,148,151,161,162,163, 175,177,179,180,199,207,214,218,222,223,224,226, 230,235,236,258,260,264,268,276,282,291,295,298, 299,300,301,305,307,318,322,329,332,333,334,336, 338,340,353,354,355,366,374,377,378,379,382,392, 397,408,410,413,414,416,421 What are yours? – user1551 Aug 2 '11 at 1:55
I don't think it is so simple. My 40 rows are 18, 29, 32, 33, 36, 51, 53, 54, 56, 62, 72, 76, 83, 84, 100, 105, 106, 110, 115, 116, 137, 141, 163, 175, 199, 207, 216, 236, 257, 299, 300, 301, 305, 325, 338, 340, 371, 392, 405, 413 – W. Edwin Clark Aug 2 '11 at 3:05
You are right. I thought my algorithm is able to find out the optimal solution, but actually it cannot. – user1551 Aug 2 '11 at 3:43