How many distinct non-zero vectors are needed to ensure that they span $\mathbb{F}_2^n$.

Question

My Attempt:

for $n=1,2,3,4$ the answer is $2^{n-1}$ which I found by brute force.

The question can also be rephrased as follows. Let $S \subseteq \mathcal{P}([n]) - \{ \emptyset\}$. What is the smallest we can make $S$ to ensure that $\{i\} = T_1 \triangle T_2 \triangle \dots\triangle T_k$ (where $\triangle$ is symmetric difference) for all $i \in [n]$ and some $T_j \in S$.

Answer 1

A set of vectors does not span the whole space if and only if it is contained in a hyperplane. So there exist sets of $2^{n-1}$ vectors that do not span the whole space, and every set of $2^{n-1}+1$ does span the whole space.

This agrees with your finding that every set of $2^{n-1}$ nonzero vectors spans the whole space.

Answer 2

You mean the ${\Bbb F}_2$-vector space ${\Bbb F}_2^n$ of dimension $n$? Then each ${\Bbb F}_2$-basis of ${\Bbb F}_2^n$ has $n$ elements.

Answer 3

I figured it out thanks to Servaes.

Every hyperplane in $V=\mathbb{F}_2^n$ contains exactly $2^{n-1}-1$ non-zero vectors; thus, any set of $2^{n-1}$ distinct, non-zero vectors in $V$ cannot be contained in a single hyperplane, so they must span $V$.