Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we extend the $[n,k]$ linear code $C$ over the field $\Bbb F_q$ to the code $C'$, where

$$ C' = \{(x_1,\ldots ,x_n,x_{n+1})\in \Bbb F_q^{n+1} : (x_1,\ldots,x_n) \in C \text{ and } x_1^2+\ldots+x_{n+1}^2 = 0\} $$

Under what conditions is $C'$ linear?

share|cite|improve this question
I edited your question using $\LaTeX$. Please check that I didn't alter the meaning of your question. Anyway, $C'$ will be a linear code, if and only if, $C'$ is a subspace of the vector space $\Bbb F_{q^{n+1}}$. Edit: There's something wrong with the question, $C'$ is empty as it is currently defined. – Git Gud Apr 7 '13 at 19:43
I'm relatively certain x12+x22+...+xn+12 was meant to be a sum of squares. ötarcan, can you verify that my edit is indeed what you meant to ask? – Snowball Apr 7 '13 at 23:47
your edit is correct snowball.i meant the sum of squares of n+1 elements is 0 – ötarcan Apr 8 '13 at 6:01

In general, the extended code $C'$ is linear if and only if the map $C \to \mathbb F_q$, mapping a codeword to its extension symbol is linear.

In your case, the extension may or may not be linear, depending on the original code $C$. The problem is that squaring is not linear, normally.

However, there is a large class of cases where we can directly answer the question:

If $q$ is even, then squaring is an automorphism of $\mathbb F_q$ (Frobenius automorphism) and thus, the extension rule is indeed linear. So whenever $q$ is even, $C'$ is linear.

share|cite|improve this answer
+1: The code may also be linear in odd characteristic, if the quadratic polynomial $x_1^2+x_2^2+\cdots+x_n^2$ evaluated at all codewords is either $0$ or a quadratic non-residue modulo $p$. It is not easy to see describe, when this would be the case, which is why I refrained from answering. If the "squared norm" ever takes a non-zero quadratic residue as its value, then there will be two solutions for $x_{n+1}$, and linearity is automatically violated. – Jyrki Lahtonen Apr 12 '13 at 12:39
azimut,do you mean the linearness of C' depends on q is even? – ötarcan Apr 12 '13 at 12:46
@ötarcan: If $q$ is even, $C'$ is linear. If $q$ is odd, $C'$ may or may not be linear, compare the comment of (btw, thanks!) Jyrki Lahtonen. – azimut Apr 12 '13 at 13:20
@ötarcan: For an example of odd characteristic case, when we do geta a linear code: let $p=3$, let $C$ be the code generated by $111$. The code has 3 words: $000,111,222$. The set $C'$ is thus $0000,1110,2220$, which is clearly linear. Alas, I still don't know of a necessary and sufficient condition for the extension like this of an odd $q$ linear code to be linear. Sufficient is easy - norms vanish. Necessary is easy - non-zero norms must all be non-squares. Sufficient and necessary?? – Jyrki Lahtonen Apr 23 '13 at 4:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.