Under what condition is $\tilde{C}$ linear?

Question

I'm doing problem 25 in the book (Fundamentals of Error Correcting Codes written by W. Cary Huffman and Vera Pless page 15)

And the problem states that Suppose we extend the [n, k] linear code C over the field $\mathbb{F_{q}}$to the code $\tilde{C}$ where

$\tilde{C}=\{x_{1}\dots x_{n+1} \in \mathbb{F}_{q}^{n+1}|x_{1}\dots x_{n}\in C $ with $ x_{1}^2+x_{2}^2+\dots +x_{n+1}^2=0\}$

Under what condition is $\tilde{C}$ linear?

A linear code with n tuples over a finite filed with q elements is (if I'm not mistaken) a subspace of $\mathbb{F_{q}^n}$

So I'm a bit confused, am I supposed to find out then $\tilde{C}$ is a subspace of $\mathbb{F_{q}^n}$ or $\mathbb{F_{q}^{n+1}}$ ?

And I'm also completely stuck on showing under what condition $\tilde{C}$ is linear given it's structure.

Could you give me some hints or whole solution to this problem?

Answer 1

Barring some very unusual situations the resulting code will be linear if and only if $\Bbb{F}_q$ has characteristic two (i.e. $q$ is a power of two). Consider the following:

• If $q=2^m$, then $x_1^2+\cdots+x_{n+1}^2=0$ if and only if $x_1+x_2+\cdots+x_{n+1}=0$.
• If $q$ is odd, and $w=(x_1,x_2,\ldots,x_{n+1})\in\tilde{C}$ then also $\tilde{w}=(x_1,x_2,\ldots,-x_{n+1})\in\tilde{C}$. If $\tilde{C}$ is linear, then we should have $$w-\tilde{w}=(0,\ldots,0,2x_{n+1})\in\tilde{C}.$$ Leaving it to you to figure when this might be ok. Often it is a contradiction but not always.