I am reading through the text [*Analysis of Boolean Functions* by Ryan O'Donnell](http://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Analysis-Of-Boolean-Functions.pdf), and I am struggling with exercise 1.12, which is the following:



> 
> A *Hadamard Matrix* is any $N \times N$ real matrix with $\pm 1$ entries and orthogonal rows. Particular examples are the *Walsh-Hadamard Matrices* $H\_N$, inductively defined for $N=2^n$ as follows: $H\_1 = [1]$, $$H\_{2^{n+1}} = \begin{bmatrix}
> \,H\_{2^n} & H\_{2^n}\\
> \,H\_{2^n} & -H\_{2^n}\\
> \end{bmatrix}$$
>  **(a)** Let's index the rows and columns of $H\_{2^n}$ by the integers $\{0,1,2,...2^n-1\}$ rather than $[2^n]$. Further, let's identify such an integer $i$ with its binary expansion $(i\_0, i\_1,...i\_{n-1})\in \mathbb{F}\_2^n$, where $i\_0$ is the least significant bit and $i\_{n-1}$ the most. For example, if $n=3$, we identify the index $i=6$ with $(0,1,1)$. Now show that the $(\gamma,x)$ entry of $H\_{2^n}$ is $(-1)^{\gamma \cdot x}$.
> 
> 
> **(b)** Show that if $f : \mathbb{F}\_2^n \to \mathbb{R}$ is represented as a column vector in $\mathbb{R}^{2^n}$ (according to the indexing scheme from part (a)) then $$\hat{f} = 2^{-n}H\_{2^n} f$$ Here we think of $\hat{f}$ as also being a function $\mathbb{F}\_2^n \to \mathbb{R}$, identifying subsets $S \subseteq \{0,1,...n-1\}$ with their indicator vectors.
> 
> 
> 


There are two more parts to the exercise in the textbook, but since I haven't even completed part **(b)**, I'll leave them out of this question. 




---


For part **(a)**, I think my solution is correct. I did a proof by induction on $n$, and separated $H\_{2^{n+1}}$ into four quadrants to complete the inductive step. Essentially, adding $2^n$ to a coordinate is equivalent to changing the most significant bit from a $0$ to $1$, and the dot product of the $\gamma$ and $x$ coordinates is unchanged by this unless both are increased by $2^n$, which happens only in the bottom right quadrant (which explains the negation in that quadrant). 




---


I don't know how to approach part **(b)**. 


I know what $\hat{f}$ means according to O'Donnell's definition. Given a boolean function $f$, $\hat{f}(S)$ is the fourier coefficient of $f$ on $S$. 


However, I don't understand how to show this computation of the fourier coefficients using the Walsh-Hadamard matrices. 


Any help is appreciated. Thank you!



How do I use Walsh-Hadamard matrices to compute Fourier coefficients of a boolean function?
Let $n=3,$ for concreteness. As you said, the correspondence is:
$$
\begin{array}{c|c|l}
\mathbb{1}(S) & \leftrightarrow & S \\ \hline
(0,0,0) &\leftrightarrow & \{\} \\
(1,0,0) & \leftrightarrow & \{ 1 \}\\
(0,1,0) &\leftrightarrow & \{2\} \\
(1,1,0) & \leftrightarrow & \{ 1,2 \}\\
(0,0,1) &\leftrightarrow & \{3 \} \\
(1,0,1) & \leftrightarrow & \{ 1,3 \}\\
(0,1,1) &\leftrightarrow & \{2,3\} \\
(1,1,1) & \leftrightarrow & \{ 1,2,3 \}\\
\end{array}
$$
and by observing the entries of the matrix are $(-1)^{\gamma\cdot x}$
we obtain
$$\hat{f}(S)=2^{-n}\sum\_{x\in \mathbb{F}\_2^n} (-1)^{ \mathbb{1}(S) \cdot x}=2^{-n}H\_{2^n} f,$$
where $\mathbb{1}(S)$ denotes the indicator vector of $S.$


