Spanning sets in linear block codes

Question

Let $C$ be a binary linear code of length $n$ and rank $k$. Say that a codeword $c\in C$ satisfies the $i$-property in $C$ if $c$ has a $1$ in the $i$-th position and $$w(c)=min\{w(c') : c'\in C\text{ and $c'$ has a $1$ in the $i$-th position}\}$$ where $w(c)$ denotes the weight of $c$. Suppose that $C$ contains a subset $X$ such that $|X|\ge k$, and, for each $i$, $1\le i\le n$, there exists $x\in X$ such that $x$ satisfies the $i$-property. I thought it might be interesting to think about the question: how small (in terms of dimension) can $Span_{\mathbb{Z}_{2}}(X)$ be? For instance, if $k=n$, then $Span_{\mathbb{Z}_{2}}(X)$ must be the entire code. It seems intuitive that $X$ must generate a "large" space. Apologies in advance if my question is trivial, and for the terminology $i$-property - I've only just started to look at linear coding, so my knowledge is sparse to say the least! Thanks.

Answer 1

It is not difficult to introduce a lot of linear dependencies to $X$. The first possibility that occurred to me involves the even weight $[n,n-1,2]$ code $C$.

For example, let $n=17$, and let $X$ consist of those ten ($10={5\choose 2}$) words of weight two that have their two non-zero bits within the first five positions, together with the six words $00000\, 110000\, 000000$, $00000\, 001100\, 000000$, $00000\, 000011\, 000000$, $00000\, 000000\, 110000$, $00000\, 000000\, 001100$, $00000\, 000000\, 000011$. So $X$ consists of 16 weight two words such that their ones occur at all positions. Thus $X$ has the $i$-property for all $i$. Yet the set $X$ only spans a 10-dimensional subspace inside the 16-dimensional code $C$. The first ten vectors all belong to a 4-dimensional subspace, and the last six listed codes all add a dimension to the span of $X$.

It seems easy to increase the gap between the dimension of the entire code, and the span of $X$ by picking a larger $n$. I also think it's likely that something similar happens with e.g. most large Reed-Muller codes.

Note BTW: In the example above all the words in $X$ have the $i$-property for some $i$. If we allow "ballast inside $X$", we can widen the gap in the above example further by covering all the bit position with nine linearly independent weight two words, and then use their higher weight linear combinations to increase the size of $X$ as large as you required it to be.