In our lecture notes we're given some properties of Walsh-Transform, for a given mapping $f: F_2^n \mapsto F_2$ (from n-dimensional-Vectorspace over F2 to F2)
The Walsh-Transform itself is given as $f^w(a) = \displaystyle{\sum_{x \in \mathbb{F}}((-1)^{(f(x)+<a,x>))}}$ with being the inner product of the two vectors a,x. (means $\sum_i^n a_i*x_i$)
The first property is given as:
$\displaystyle{\sum_{a \in \mathbb{F}}}f^w(a) = 2^n(-1)^{f(0)}$
which is still quite easy. But than it comes to:
$\displaystyle{\sum_{a \in \mathbb{F}_2^n}}f^w(a)^2 = 2^{2n}$
which gives me a rough time. It seems to follow the first property, but I seem to miss the correct rearrangement. It's obvious, that one cannot just square the right side of the first equation, though it would give us the very needed result. Any hints or ideas?
This is an instance of Parseval's identity. Walsh-Hadamard transform is similar to any other discrete Fourier transform in this sense.
We have $$ f^w(a)^2=\left(\sum_{x\in\Bbb{F}_2^n}(-1)^{f(x)+\langle a, x\rangle}\right)\left(\sum_{y\in\Bbb{F}_2^n}(-1)^{f(y)+\langle a, y\rangle}\right)=\sum_{x,y\in\Bbb{F}_2^n}(-1)^{f(x)+f(y)+\langle a, x+y\rangle}. $$ So when you sum these over $a\in\Bbb{F}_2^n$ you should first change the order of summation so that in the triple sum $\sum_{x,y,a\in\Bbb{F}_2^n}$ you do the $a$-sum first. Then you can use orthogonality to see that the $a$-sum is zero unless $x=y$ in which case it is $=2^n(-1)^{f(x)+f(y)}$. But, when $x=y$ we have $f(x)+f(y)=0$. The claim follows.