span set and min distance of a code

Question

Let C have the spanning set $S$ where $S=\{v_1,v_2,v_3\}\subseteq \mathbb{F}^n_q$

then $d(C)=\min\{wt(v_1),wt(v_2),wt(v_3)\}$

Is that statement true?why?

thank you for your answers...

Answer 1

The answer is that the claim may or may not be true. The following cases are easy to do by hand. First, if $G$ is $$ G=\left(\begin{array}{c}111100000000\\000011110000\\000000001111\end{array}\right), $$ then the claim is true, and the minimum distance of the code is equal to the minimum weight of a generator, here 4.

On the other hand, when $$ G=\left(\begin{array}{c}111111111110\\111111111101\\111111111011\end{array}\right), $$ then the claim is not true. Prove this by writing sum linear combinations of the generators, and check that you get weights less than those of all the generators (here all the generators have weight 11).

Answer 2

If your three vectors are linearly independent, then they form a basis for the linear code $C$ as a subspace of $\mathbb{F}_q^n$. From this basis we can create the generator matrix for the code as

$G=\begin{pmatrix}v_1\\v_2\\v_3\end{pmatrix}$

Using the generator matrix, we can create a parity check matrix $H$ for the code. There's a pretty good explanation of how this works on this website (about halfway down the page, after "Definition 1.2.4").

After you have the parity check matrix, the distance $d(C)$ will be equal to the smallest number of linearly dependent columns in $H$. Think about it: a vector $w$ is a codeword iff $w H^T =0$. If there are $d$ linearly dependent columns in $H$, consider the vector $w$ with $1$'s in those positions and $0$'s elsewhere, such that $d(w)=d$. If there were any codeword of weight less than $d(w)=d$, then it would identify a set of less than $d$ linearly dependent columns in $H$. Thus $d(C)=d$.

Doing this for your vectors should lead you to your answer.