The set of codewords starting with $0$ in a linear code on the field $\mathbb F_q$

Question

Show that in linear code $C$ on the field $\mathbb F_q$ ,the set of codewords starting with $0$ namely $C'$ is $C$ itself or it has the cardinality $|C|/q$.

We know that $|C| = q^{dim(C)}$ for every linear $C$ on the field $\mathbb F_q$ so all we have to do is show that $dim(C')=dim(C)-1$ but I don't know how to deal with dimensions...

Answer 1

but I dont' know how to deal with dimensions...

Well... let's try to rectify that as soon as possible! Not understanding dimension would be a huge handicap for lots of reasoning about linear algebra.

I suppose the most elementary way to look at it would be this way: if $n=\dim(C)$, then you can write codewords as elements of $\mathbb F_q^n$. Obviously this has the standard basis of $n$ elements which have a $1$ in exactly one position. Call that set $\mathcal B$.

This makes a natural candidate for a basis of the subspace $\{(x_0,\ldots, x_n)\mid x_i\in \mathbb F_q, x_0=0\}$: you just take the set $\mathcal B'=\mathcal B\setminus \{(1,0,\ldots, 0)\}$. $\mathcal B'$ is obviously a basis for the subspace you are talking about, and it clearly has $n-1$ elements... so there you have it!

Reasoning with dimension and bases is very important. I'm not sure what issues you are having with the topic, but here are some important things to keep in mind:

• The dimension of a finite dimensional vector space is the maximal size of a set of linearly independent elements of the space. This number is unique.
• Given a linearly independent subset, you can always add elements to it to create a basis.
• If $V$ has dimension $n$, then its subspaces can only have dimensions $0,\ldots, n$.
• If $W$ is a subspace of $V$, and $\dim(W)=\dim(V)$, then $W=V$.
• If $V=V_1\oplus V_2$, then $\dim(V)=\dim(V_1)+\dim(V_2)$
• If $W$ is subspace of $V$, then $\dim(V/W)=\dim(V)-\dim(W)$.

You could leverage these last two points to prove your code $\mathcal C'$ has dimension $\dim(\mathcal C)-1$ too.

the set of codewords starting with $0$ namely $C'$ is $C$ itself or it has the cardinality $|C|/q$. but I dont' know how to deal with dimensions...

I do not understand the boldface part. By talking about "codewords starting with zero," you have implicitly assumed that $\mathcal C$ is of the form $\mathbb F_q^n$ for some integer $n$ (I assume this because this is the normal context) and so clearly some elements are nonzero on the first element.

It would be fair to say that any linear code containing the elements which are zero on the first coordinate is $\mathcal C$ or is $\mathcal C'$. This is because the code is either $\mathcal C'$ itself, or if it has more elements, it must have dimension strictly greater than that of $\mathcal C'$, at which point it can only have dimension equal to that of $\mathcal C$, but then it is equal to $\mathcal C$ by one of the points I mention above.

Answer 2

Let us consider a code $C$ has a stander generator matrix $G=[I_k|A]$, where $k$ is the dimension of the code. Without taking first row of the generator matrix, remaining $k-1$ rows give $q^{k-1}$ codewords starting with $0$. Now if we combine first row with these $q^{k-1}$ codewords, we are getting $|C|/q$ codewords starting with zero. I think it will help.