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.


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 $Z_2^k$). The dot product $\varphi_x(y)=x\cdot y$ is a group homomorphism $\varphi_x:C\rightarrow 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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