11
$\begingroup$

Let $V$ be a vector space over $\mathbb{Z}/2\mathbb{Z}$. Can there be a set $S$ of $2 n$ vectors in $V$ such that any $n$ vectors in $S$ span a space of dimension exactly $n-1$, but no $n$ vectors $v_1,\dotsc ,v_n\in S$ satisfy $v_n = v_1 + v_2 + \dotsc + v_{n-1}$?

$\endgroup$
  • 2
    $\begingroup$ Is it false even without the last condition? $\endgroup$ – LeechLattice Sep 2 at 12:43
  • $\begingroup$ That would seem to be intuitively clear, in that one can take a set $S$ of $2 n$ random vectors in an $(n-1)$-dimensional space $V$. However, $\mathbb{Z}/2\mathbb{Z}$ is so small that it's likely that there will be unexpected linear relations between them, thereby spoiling the example. So it seems a bit tricky, though I would expect a set $S$ without the last condition to exist. $\endgroup$ – H A Helfgott Sep 2 at 13:47
  • $\begingroup$ (Of course, the same naive model would predict the existence of a set $S$ satisfying the last condition.) $\endgroup$ – H A Helfgott Sep 2 at 13:48
19
$\begingroup$

Since every $n$ vectors span a space of dimension $n-1$, the whole set $S$ spans a space of dimension $n-1$, and we can assume that $V$ has dimension $n-1$. Choose $n-1$ linearly independent vectors $T=\{t_1,t_2,\dots,t_{n-1}\}\subseteq S$ and assign the standard basis to them, i.e. $t_k=(0,0,\dots,0,1,0,\dots,0)$ where the $1$ is at index $k$.

Let $x,y\in S\setminus T$ be distinct. For each $k\in\{1,\dots,n-1\}$, $x_k\neq 0$ or $y_k\neq 0$, otherwise there are $n$ vectors in $S$ spanning a $n-2$ dimensional space: $x$, $y$, and all the vectors in $T$ excluding $t_k$.

By the pigeonhole principle, there are at most $n-1$ zero indices in $S\setminus T$. So there are at most $n$ vectors in $S\setminus T$ (otherwise there would be two all-$1$ vectors).

So the size of $S$ is at most $2n-1$. As a result, there is no set $S$ of size $|S|=2n$ such that any $n$ vectors from $S$ span an $(n-1)$-dimensional subspace.

$\endgroup$
  • 2
    $\begingroup$ Hah, that's nice. Of course it also means the question was perhaps not the right question to ask. $\endgroup$ – H A Helfgott Sep 2 at 14:58
  • 1
    $\begingroup$ "By the pigeonhole principle, there are at most $n-1$ zero indices in $S\setminus T$." What do you mean by this? $\endgroup$ – darij grinberg Sep 4 at 15:29
  • 3
    $\begingroup$ It means $\sum_{x\in S\setminus T} \#\{k:x_k =0\} \leq n-1$. $\endgroup$ – Dan Petersen Sep 4 at 15:35
  • 1
    $\begingroup$ @DanPetersen: Ah! So "zero indices" means zero coordinates of elements of $S \setminus T$ (counted as pairs of an element and a position). And indeed, this follows from the pigeonhole principle, since otherwise there would be two elements having zero coordinates at the same position, and this is ruled out by the preceding paragraph. Nice proof! $\endgroup$ – darij grinberg Sep 4 at 18:19
  • $\begingroup$ Isn't the all 1-vector just what the OP doesn't want, and the size of $S$ therefore at most $2n-2$? $\endgroup$ – j.p. Sep 14 at 17:34

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.