Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.