Editing Hadamard transform (section)

==Definition==
{{Split portions|section=y |date=March 2025|Hadamard matrix}}

The Hadamard transform ''H''<sub>''m''</sub> is a 2<sup>''m''</sup>&nbsp;×&nbsp;2<sup>''m''</sup> matrix, the [[Hadamard matrix]] (scaled by a normalization factor), that transforms 2<sup>''m''</sup> real numbers ''x''<sub>''n''</sub> into 2<sup>''m''</sup> real numbers ''X''<sub>''k''</sub>.  The Hadamard transform can be defined in two ways: [[recursively]], or by using the [[binary numeral system|binary]] ([[radix|base]]-2) representation of the indices ''n'' and ''k''.

Recursively, we define the 1&nbsp;×&nbsp;1 Hadamard transform ''H''<sub>0</sub> by the [[identity matrix|identity]] ''H''<sub>0</sub> = 1, and then define ''H''<sub>''m''</sub> for ''m''&nbsp;>&nbsp;0 by:
<math display="block">H_m = \frac{1}{\sqrt2} \begin{pmatrix} H_{m-1} & H_{m-1} \\ H_{m-1} & -H_{m-1} \end{pmatrix}</math>
where the 1/{{radic|2}} is a normalization that is sometimes omitted.

For ''m''&nbsp;>&nbsp;1, we can also define ''H''<sub>''m''</sub> by:
<math display="block">H_m = H_{1} \otimes H_{m-1}</math>
where <math> \otimes </math> represents the [[Kronecker product]]. Thus, other than this normalization factor, the Hadamard matrices are made up entirely of 1 and −1.

Equivalently, we can define the Hadamard matrix by its (''k'',&nbsp;''n'')-th entry by writing
<math display="block">\begin{align}
  k &= \sum^{m-1}_{i=0} {k_i 2^i} = k_{m-1} 2^{m-1} + k_{m-2} 2^{m-2} + \dots + k_1 2 + k_0 \\
  n &= \sum^{m-1}_{i=0} {n_i 2^i} = n_{m-1} 2^{m-1} + n_{m-2} 2^{m-2} + \dots + n_1 2 + n_0
\end{align}</math>

where the ''k''<sub>''j''</sub> and ''n''<sub>''j''</sub> are the bit elements (0 or 1) of ''k'' and ''n'', respectively. Note that for the element in the top left corner, we define: <math>k = n = 0</math>.  In this case, we have:
<math display="block"> (H_m)_{k,n} = \frac{1}{2^{m/2}} (-1)^{\sum_j k_j n_j}</math>

This is exactly the multidimensional <math display=inline> 2 \times 2 \times \cdots \times 2 \times 2</math> DFT, normalized to be [[unitary operator|unitary]], if the inputs and outputs are regarded as multidimensional arrays indexed by the ''n''<sub>''j''</sub> and ''k''<sub>''j''</sub>, respectively.

Some examples of the Hadamard matrices follow.
<math display="block"> 
\begin{align}
  H_0 & = +\begin{pmatrix}1\end{pmatrix}\\[5pt]
  H_1 & = \frac{1}{\sqrt2}
            \left(\begin{array}{rr}
              1 &  1\\
              1 & -1
            \end{array}\right)\\[5pt]
  H_2 & = \frac{1}{2}
   \left(\begin{array}{rrrr}
      1 &  1 &  1 &  1\\
      1 & -1 &  1 & -1\\
      1 &  1 & -1 & -1\\
      1 & -1 & -1 &  1
   \end{array}\right)\\[5pt]
  H_3 & = \frac{1}{2^{3/2}}
   \left(\begin{array}{rrrrrrrr}
      1 &  1 &  1 &  1 &  1 &  1 &  1 &  1\\
      1 & -1 &  1 & -1 &  1 & -1 &  1 & -1\\
      1 &  1 & -1 & -1 &  1 &  1 & -1 & -1\\
      1 & -1 & -1 &  1 &  1 & -1 & -1 &  1\\ 
      1 &  1 &  1 &  1 & -1 & -1 & -1 & -1\\
      1 & -1 &  1 & -1 & -1 &  1 & -1 &  1\\
      1 &  1 & -1 & -1 & -1 & -1 &  1 &  1\\
      1 & -1 & -1 &  1 & -1 &  1 &  1 & -1
   \end{array}\right)\\[5pt]
  (H_n)_{i,j} & = \frac{1}{2^{n/2}} (-1)^{i \cdot j}
\end{align}
</math>
where <math> i \cdot j </math> is the bitwise [[dot product]] of the binary representations of the numbers i and j. For example, if <math display="inline"> n \;\geq\; 2</math>, then <math display="block"> (H_n)_{3,2} \;=\;  (-1)^{3 \cdot 2} \;=\; (-1)^{(1,1) \cdot (1,0)} \;=\; (-1)^{1+0} \;=\; (-1)^1 \;=\; -1</math>, agreeing with the above (ignoring the overall constant). Note that the first row, first column element of the matrix is denoted by <math display="inline"> (H_n)_{0,0} </math>.

''H''<sub>1</sub> is precisely the size-2 DFT.  It can also be regarded as the [[Fourier transform]] on the two-element ''additive'' group of '''Z'''/(2).

The rows of the Hadamard matrices are the [[Walsh function]]s.

{{missing information|section|ordering variants of the Hadamard matrices: sequency ([[Walsh matrix]]), Hadamard, and dyadic|date=April 2024}}