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.


1 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.

  • $\begingroup$ My favorite proof for this lemma so far that I've seen in the wild. $\endgroup$ Oct 22, 2021 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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