# Upper-bounding $\dim \text{span}\{v_1,\dots,v_n\}$ in terms of $\dim \text{span}$ of subsets

I asked this question on Stack Exchange two weeks ago, and didn't get any answers, so I'm shamelessly reposting it here.

Let $$S=\{v_1,\dots, v_n\} \subset V$$ be a set of nonzero vectors in a vector space (we can take the field to be algebraically closed). It is easy to prove that if there exists a sequence $$S_1,\dots, S_r \subseteq S$$ such that

1. $$\dim\text{span}S_j=1$$ for all $$j=1,\dots, r$$.

2. $$S_j \cap S_{j+1} \neq \emptyset$$ for all $$j=1,\dots, r-1$$.

3. $$\bigcup_{j=1}^r S_j=S$$.

then $$\dim\text{span}S=1$$.

Essentially, this gives a way to upper bound $$\dim\text{span}S$$ in terms of $$\dim\text{span}$$ of subsets obeying certain properties. My open-ended question is whether there are "interesting" generalizations of this to the case in which we want to upper bound $$\dim\text{span}S\leq d$$ for some $$d\geq 1$$, in terms of subsets obeying certain properties.

Of course, there are trivial results in this vein: If every subset of size $$\leq n-1$$ has dimension $$\leq d$$ for some $$d, then $$\dim\text{span}S\leq d$$. I am looking for something more useful, that hopefully looks something like the above result for $$d=1$$.

• I've included a link to avoid possible duplication of effort. It would be good to do the same thing in the other direction. Feb 25 '20 at 1:01
• Done. Thank you
– Ben
Feb 25 '20 at 1:03
• If condition 1 is replace by dim span $S_j = 2$ for $j=1,\ldots,r$, then dim span $S$ can be anything from 2 to $r$. Feb 25 '20 at 1:53
• That’s a nice observation, thanks!
– Ben
Feb 26 '20 at 0:13

Let $$S = \{v_1,...,v_n \} \subseteq V$$ be a set of nonzero vectors in a vector space over an algebraically closed field and suppose that we have $$S_1,...,S_r \subseteq S$$ such that $$S = \bigcup_{i=1}^r S_i$$.

For each $$S_i$$, set $$d_i = \mathrm{dim} \mathrm{span} (S_i)$$ and $$c_i = \dim \mathrm{span} (S_i \cap S_{i+1})$$, (we omit $$c_r$$). Then we have $$\mathrm{dim} \mathrm{span}(S) = \mathrm{dim} \mathrm{span} \left( \bigcup_{i=1}^r S_i \right) = \sum_{i=1}^r \mathrm{dim} \mathrm{span}(S_i) - \sum_{1 \leq i Therefore, $$\dim \mathrm{span}(S) \leq \sum_{i=1}^r d_i - \sum_{i=1}^{r-1} c_i.$$

At this point, we note that $$d_i \geq c_i$$ and $$|S_i \cap S_{i+1}| \geq c_i$$. The above gives us an upper-bound for the dimension of $$S$$, even if it's not very good. The special case is your original theorem: let $$d_i = 1$$ for all $$i$$ and let $$S_i \cap S_{i+1} \neq \emptyset$$. By the assumption that our vectors are non-zero, $$\dim \mathrm{span}(S_i \cap S_{i+1}) \geq 1$$. So $$c_i \geq 1$$ and $$c_i \leq d_i$$, so $$c_i = 1$$. Then $$\dim \mathrm{span}(S) = 1$$ immediately follows.

In the comment left by Brendan McKay, we have $$d_i = 2$$ and $$1 \leq c_i \leq 2$$, so $$\dim \mathrm{span}(S)$$ is between $$r$$ and $$2$$ inclusive.

Hopefully, this is a generalization you're satisfied with even if in general, it gives a huge range.