Orthonormal basis for boolean functions Consider the set of functions with domain $\{+1, −1\}^n$ and range $\mathbb R$. Observe that it is a vector space over $\mathbb R$ of dimension $2^n$. Consider the inner product and norm defined by
$$\langle f,g\rangle=\frac{1}{2^n} \sum_{x\epsilon\{+1,-1\}^n} f(x)g(x) \quad and\quad \Vert f\Vert = \sqrt{\langle f,f\rangle}$$
a)Define the following functions:
$$\{\chi_S\}_{S\subseteq\{1,...,n\}} \quad where \quad \chi_S(x)=\prod_{i\epsilon S}x_i$$
For $S=\varnothing$, $\chi_S$ is the constant 1 function. Show that these functions form an orthonormal basis under the inner product defined.
b)Let f be any function this space with range $\{+1,-1\}$ such that
$$f=\sum_{S\subseteq\{1,...,n\}} \hat f_S\chi_S \quad where \quad \hat f_S\in \mathbb{R}$$
That is $(\widehat f_S)_{S\subseteq\{1,...,n\}}$ are the co-ordinates with respect to the $\chi_S$ basis.
Show that
$$\sum_{S\subseteq\{1,...,n\}} (\widehat {f_S})^2=1$$
 A: Right, so I think $b)$ is clear from the fact that $\{\chi_S\}_S$ are orthogonal. Your argument for $\langle \chi_S,\chi_S\rangle=1$ is correct. So let us focus on
showing that $\langle \chi_S,\chi_R\rangle=0$ if $R\neq S$.
We have that
$$
\langle \chi_S,\chi_R\rangle=
2^{-n} \sum_{x \in \{-1,+1\}^{\{1,\dots,n\}}} \prod_{i\in S} x_i \prod_{j\in R} x_j.
$$
Notice that for each $x$ the indexes $i \in S\cap R$ do not contribute to the product as $x_i^2=1$, therefore we have that
$$
\prod_{i\in S} x_i \prod_{j\in R} x_j
=
\prod_{i\in S \Delta R} x_i,
\qquad (1)
$$
where $S \Delta R$ denotes the symmetric difference of $S$ and $R$.
Finally, we argue that for any non-empty set $J \subset \{1,\dots,n\}$, we have
$$
\sum_{x \in \{-1,+1\}^{\{1,\dots,n\}}} \prod_{i\in J} x_i =0. \qquad (2)
$$
Indeed, choose $j \in J$, we can write the right hand side as
$$
\sum_{x \in \{-1,+1\}^{\{1,\dots,n\}}} \prod_{i\in J} x_i 
=
\left(\sum_{x_j \in \{-1,1\}} x_j \right)\left(\sum_{x \in \{-1,+1\}^{\{1,\dots,n\} \setminus \{j\}}}  \prod_{i\in J \setminus \{j\}} x_i \right).
$$
Now the first term is equal to zero.
Finally, from $(1)$ and $(2)$, we have the desired result, as $S\neq R \iff S\Delta R \neq \emptyset$.
