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<n-1$, 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$.

  • 2
    $\begingroup$ I've included a link to avoid possible duplication of effort. It would be good to do the same thing in the other direction. $\endgroup$ Feb 25 '20 at 1:01
  • $\begingroup$ Done. Thank you $\endgroup$
    – Ben
    Feb 25 '20 at 1:03
  • $\begingroup$ 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$. $\endgroup$ Feb 25 '20 at 1:53
  • $\begingroup$ That’s a nice observation, thanks! $\endgroup$
    – 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 <j \leq r} \mathrm{dim} \mathrm{span} (S_i \cap S_j) \leq \sum_{i=1}^r \mathrm{dim} \mathrm{span}(S_i) - \sum_{i = 1}^{r-1} \mathrm{dim} \mathrm{span} (S_i \cap S_{i+1}) = \sum_{i=1}^r d_i - \sum_{i=1}^{r-1} c_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.

  • 1
    $\begingroup$ Thanks. Your bound is correct but your proof is not. The set S=S_1=S_2=S_3={e_1} contradicts your second equality. $\endgroup$
    – Ben
    Feb 27 '20 at 17:08
  • $\begingroup$ Ah, I see the error now. So right now this only works if every triple intersection is the empty set. When I'm at my computer I'll try and fix the proof, thanks! $\endgroup$ Feb 27 '20 at 21:09

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.