MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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


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

Browse other questions tagged or ask your own question.