2
$\begingroup$

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

$\endgroup$
4
  • 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$ Commented Feb 25, 2020 at 1:01
  • $\begingroup$ Done. Thank you $\endgroup$
    – Ben
    Commented Feb 25, 2020 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$ Commented Feb 25, 2020 at 1:53
  • $\begingroup$ That’s a nice observation, thanks! $\endgroup$
    – Ben
    Commented Feb 26, 2020 at 0:13

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • 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
    Commented Feb 27, 2020 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$ Commented Feb 27, 2020 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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