Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider an m by n matrix $A$ with entries from some finite field $\mathbb{F}_q$, where $m\geq n$. Let us write matrix $A$ as follows $A=[A_1^T~A_2^T~\ldots A_l^T]^T$, where $A_i$'s are given matrices. Furthermore assume that all the rows of each matrix $A_i$ are linearly independent. For a given set of numbers $k_1,k_2,\ldots,k_l$, $\sum_i k_i\geq n$ the goal is to find a subset of $k_i$ rows of each $A_i$, denoted by $S_i$, such that $rank\{[S_1^T~S_2^T\ldots S_l^T]\}=n$.

Is it possible to devise a polynomial time algorithm that solves this problem?

Note that $k_1,k_2,\ldots,k_l$ are picked such that the solution always exists.

share|improve this question
2  
I have a feeling that exact set cover reduces to this problem. I am therefore not optimistic about finding a polynomial time solution. Gerhard "Ask Me About System Design" Paseman, 2011.05.05 –  Gerhard Paseman May 5 '11 at 22:19

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.