# rank minimization over vector subsets

Let $S$ be a set of $n$ vectors from $\mathbb{Q}^d$. For every $k=1,2,\dots,n$, define $$r_k = \min_{T\subset S, |T|=k} \mathrm{rank}(T),$$ where $\mathrm{rank}(T)$ is the rank of a matrix formed by the vectors from $T$.

Question 1. Is there an efficient way to compute numbers $r_k$ ? I've developed some iterative procedure computing $r_1, r_2, \dots$ in order, but it is still rather slow.

Question 2. (updated) How to characterize sets $S$ that possess an ordering of elements, say, $S=\{ v_1, v_2, \dots, v_n \}$, such that for every $k=1,2,\dots,n$, $$\mathrm{rank}(\{v_1, v_2, \dots, v_k\}) = r_k.$$ Christian Remling gave an example of $S$ that does not have such an ordering.

• (2) is false: let $S$ contain $N_1$ vectors from a $1$-dimensional subspace $V_1$ and then $N_2\gg N_1$ vectors from a $2$-dimensional subspace that does not contain $V_1$. – Christian Remling May 31 '15 at 23:31
• @ChristianRemling: Thanks for the counterexample. I need to figure out what is so special about $S$ I'm dealing with, since they seem to have a described ordering. – Max Alekseyev Jun 1 '15 at 0:38

Regarding Question 1, it's actually NP-hard to compute $r_d$. Indeed, $r_d<d$ precisely when $d$ of your vectors are linearly dependent, and the corresponding decision problem ("LINEAR DEGENERACY") is NP-complete by Theorem 1 of Khachiyan's "On the Complexity of Approximating Extremal Determinants in Matrices" (link).