2
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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 $\endgroup$ May 5, 2011 at 22:19

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.