1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ (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$. $\endgroup$ – Christian Remling May 31 '15 at 23:31
  • $\begingroup$ @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. $\endgroup$ – Max Alekseyev Jun 1 '15 at 0:38
1
$\begingroup$

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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.