Identity for linear codes and their duals: why do we have $\sum_y (-1)^{x\cdot y}=|C|\delta_{x\in C^\perp}$?

Question

I've come across this exercise plenty of times and I still don't understand how to do it. (Here it is from N.C. Ex.10.25)

Let $C$ be a linear code (Lets suppose its a binary code, i.e. a $k$-dimensional subspace of $\mathbb{F}_2^n$). Show that $$\sum_{y\in C}(-1)^{x\cdot y} =\begin{cases} |C|\, \text{ if $x\in C^\perp$},\\ 0\, \text{ if $x\notin C^\perp$}.\end{cases}$$

(Aside: This exercise is key in understanding why CSS codes can correct both bit flip and phase flip errors.)

The case where $x\in C^\perp$ is trivial. It's the second case that is less so... I know the following: If $x\notin C^\perp$ then $x\in C$. I can also see that the solution would follow if I could show that half the vectors $y\in C$ were orthogonal to $x$. Since this would imply that the other half are not orthogonal and we would have an equal number of $(+1)$'s coming from $x\cdot y=0$ that would cancel out with the $(-1)$'s from the $x\cdot y=1$ terms. Anyone have the missing piece or am I on the wrong track here.

Answer 1

Here is a lovely proof. Recall that we can think of any vector space as an abelian group, in particular, the codespace $C$ is an abelian group (isomorphic to $\mathbb{Z}_2^k$). The dot product $\varphi_x(y)=x\cdot y$ is a group homomorphism $\varphi_x:C\rightarrow \mathbb{Z}_2$. Provided that $x\notin C^\perp$ the map is surjective which means that $K=ker(\varphi)$ is an index 2 subgroup of $C$. It follows from Lagrange's theorem that $|K|=|C|/2$ and the result follows.

Answer 2

Here is another proof, which is more elementary but less enlightening. If $x \in C^{\perp}$ then $$\sum_{y\in C}(-1)^{x\cdot y} = \sum_{y\in C} 1 = |C|.$$ If $x \not\in C^{\perp}$ then there exists $z \in C$ where $x \cdot z$ is odd, so $(-1)^{x \cdot z} = -1$. Now, $$(-1)^{x \cdot z}\sum_{y\in C}(-1)^{x\cdot y} = \sum_{y \in C}(-1)^{x\cdot (z+y)} = \sum_{y \in C}(-1)^{x\cdot y}$$ where the last equality follows from the fact that addition on vectors in $C$ by a fixed vector $z \in C$ is a bijection on $C$. This shows that $\sum_{y \in C}(-1)^{x\cdot y} = -\sum_{y \in C}(-1)^{x\cdot y}$, which can only happen if $\sum_{y\in C}(-1)^{x\cdot y} = 0$.