# Basic classical linear error correcting code for bits exercice (from Nielsen & Chuang)

I am learning about quantum error correction which is for a part based on classical linear error correcting code.

There is a very basic answer on an exercice I do not understand. Here is the problem (From Nielsen & Chuang, page 450, exercice 10.25)

Let $$C$$ be a linear code. Show that if $$x \in C^{\perp}$$, then: $$\sum_{y \in C} (-1)^{x.y} = |C|$$ Show that if $$x \notin C^{\perp}$$, then: $$\sum_{y \in C} (-1)^{x.y}=0$$

I can show the first one using the definition, basically if $$x \in C^{\perp}$$ by definition $$\forall y \in C$$ I have $$x.y=0$$

Thus: $$\sum_{y \in C} (-1)^{x.y} = \sum_{y \in C} (-1)^0 = |C|$$ (where I assume that what is called $$|C|$$ is the number of element in the linear code which is $$2^k$$ if we want to encode $$k$$ bits an information right ?

However I don't understand the second one. Indeed, if $$x \notin C^{\perp}$$ then $$x.y=1$$ (We work with modulo 2 scalar product). And we have:

$$\sum_{y \in C} (-1)^{x.y}=\sum_{y \in C} (-1)=-|C|$$

Where is my mistake ?

In summary my questions are:

• Do you agree with me that if we want to encode $$k$$ bits of info, then $$|C|=2^k$$
• Why for $$x \notin C^{\perp}$$ $$\sum_{y \in C} (-1)^{x.y}=0$$

Suppose that $$e_1, \ldots, e_k$$ are (linearly independent) rows of the generator matrix of $$C$$. We can find vectors $$e_{k+1}, \ldots, e_{n}$$ s.t. $$\{e_i\}_{i=1}^n$$ is a basis in $$\mathbb{F}_2^n$$ (not necessarily orthogonal).
$$\textbf{Claim 1.}$$ $$\exists i \in [k],$$ s.t. $$\langle x, e_i \rangle = 1$$. Otherwise, for $$\forall y \in C$$ the inner product $$\langle x, y \rangle = \sum_{i=1}^k \beta_i \langle x, e_i \rangle = 0,$$ where $$y = \sum_{i=1}^k\beta_ie_i$$ is the basis decomposition of $$y$$ (all operations are modulo 2). Hence, the assumption that $$x \notin C^{\perp}$$ is incorrect.
Without loss of generality, $$\langle x, e_1\rangle = \ldots = \langle x, e_s\rangle = 1$$, $$\langle x, e_{s+1}\rangle = \ldots = \langle x, e_k\rangle = 0$$ for some $$s \in [k]$$.
Then $$\langle x, y\rangle = \sum_{i=1}^s\beta_i$$. The number of sequences $$\{\beta_i\}_{i=1}^s$$ of an even weight is the same as the number of odd-weight sequences, and it's equal to $$2^{s-1}$$, which concludes the proof.