3
$\begingroup$

Let $S=\{c_1,\dots,c_n\}$ be a set of vectors in $\mathbb{R}^M$. Is the below problem studied in literature?
$$\max\limits_{S'\subset S} \vert S' \vert $$ $$s.t. dim(span(S')) < dim(span(S))$$

which is to find the cardinality of the largest subset which does not span the span of S.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ I won't be surprised if this is NP-hard. $\endgroup$
    – Brendan McKay
    Commented Feb 27, 2020 at 9:41
  • $\begingroup$ I asked this question a while ago: mathoverflow.net/q/339819/9924 There were no replies, and somehow I convinced myself that no reasonable answer exists. $\endgroup$
    – Seva
    Commented Feb 27, 2020 at 15:28

1 Answer 1

Reset to default
2
$\begingroup$

This seems to be a matroid theory question. If you let $S$ be the ground set of the matroid and you let $r$ be the rank of the matroid (i.e. $\dim \mathrm{span}(S)$), then your question amounts to finding the largest flat of rank $r-1$.

For reference, I would recommend Oxley's Matroid Theory.

That said, one generally cares more about finding the entire lattice of flats or a maximal chain of flats than a particular one. But to answer your question, flats, in general, are of particular interest in matroid theory. There are a number of tools for finding flats as well.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .