Editing Hadamard transform (section)

==Relation to Fourier transform==

The Hadamard transform is in fact equivalent to a multidimensional DFT of size {{math|2 × 2 × ⋯ × 2 × 2}}.<ref name="kunz">{{cite journal |first=H.O. |last=Kunz |title=On the Equivalence Between One-Dimensional Discrete Walsh–Hadamard and Multidimensional Discrete Fourier Transforms |journal=IEEE Transactions on Computers |volume=28 |issue=3 |pages=267–8 |year=1979 |doi=10.1109/TC.1979.1675334 |s2cid=206621901 }}</ref>

Another approach is to view the Hadamard transform as a Fourier transform on the [[Boolean group]] <math>(\Z / 2\Z)^n</math>.<ref>[https://www.staff.uni-mainz.de/pommeren/Kryptologie/Bitblock/A_Nonlin/Fourier.pdf Fourier Analysis of Boolean Maps– A Tutorial –, pp. 12–13]</ref>
<ref>[https://www.cse.iitk.ac.in/users/rmittal/prev_course/s19/reports/5_algo.pdf Lecture 5: Basic quantum algorithms, Rajat Mittal, pp. 4–5]</ref> Using the [[Fourier transform on finite groups|Fourier transform on finite (abelian) groups]], the Fourier transform of a function <math>f \colon (\Z/2\Z)^n \to \Complex</math> is the function <math>\widehat f</math> defined by
<math display="block">\widehat{f}(\chi) = \sum_{a \in (\Z/2\Z)^n} f(a) \bar{\chi}(a)</math>
where <math>\chi</math> is a [[Character (mathematics)|character]] of <math>(\Z/2\Z)^n</math>. Each character has the form <math>\chi_r(a) = (-1)^{a \cdot r}</math> for some <math>r \in (\Z/2\Z)^n</math>, where the multiplication is the boolean dot product on bit strings, so we can identify the input to <math>\widehat{f}</math> with <math>r \in (\Z/2\Z)^n</math> ([[Pontryagin duality]]) and define <math>\widehat f \colon (\Z/2\Z)^n \to \Complex</math> by
<math display="block">\widehat{f}(r) = \sum_{a \in (\Z/2\Z)^n} f(a) (-1)^{r \cdot a}</math>

This is the Hadamard transform of <math>f</math>, considering the input to <math>f</math> and <math>\widehat{f}</math> as boolean strings.

In terms of the above formulation where the Hadamard transform multiplies a vector of <math>2^n</math> complex numbers <math>v</math> on the left by the Hadamard matrix <math>H_n</math> the equivalence is seen by taking <math>f</math> to take as input the bit string corresponding to the index of an element of <math>v</math>, and having <math>f</math> output the corresponding element of <math>v</math>.

Compare this to the usual [[discrete Fourier transform]] which when applied to a vector <math>v</math> of <math>2^n</math> complex numbers instead uses characters of the [[cyclic group]] <math>\Z / 2^n \Z</math>.