In Quantum Computing: From Linear Algebra to Physical Realizations, pg. 103, it states:
Let us consider the summation $$ \frac{1}{2^n}\sum_{x=0}^{2^n-1}(-1)^{x \cdot y} $$ with a fixed $y \in S_n$ Clearly it vanishes since $x \cdot y = 0$ for half of $x$ and $x\cdot y = 1$ for the other half unless $y=0$.
Where $x \cdot y := x_{n-1}y_{n-1}\oplus ...\oplus x_0y_0$ I have been thinking about it for quite some time and do not understand how this is clear. Why is it immediate that $x \cdot y = 0$ for half of $x$?
If $y\neq 0$ then there exists some $x_0$ such that $x_0 \cdot y = 1$ and also as $x$ ranges over $\{0,1\}^n$, so does $x+x_0$. Then $$S := \sum_{x\in \{0,1\}^n}(-1)^{x\cdot y} = \sum_{x\in \{0,1\}^n}(-1)^{(x+x_0)\cdot y}=(-1)^{x_0 \cdot y}\sum_{x\in \{0,1\}^n}(-1)^{x\cdot y}=-S$$ which shows that $S=0$.