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.
