Editing Hadamard matrix (section)

==Sylvester's construction==
Examples of Hadamard matrices were actually first constructed by [[James Joseph Sylvester]] in 1867. Let ''H'' be a Hadamard matrix of order ''n''. Then the partitioned matrix
:<math>\begin{bmatrix}
  H &  H\\
  H & -H
\end{bmatrix}</math>

is a Hadamard matrix of order 2''n''. This observation can be applied repeatedly and leads to the following sequence of matrices, also called [[Walsh matrix|Walsh matrices]].

:<math>\begin{align}
  H_1 &= \begin{bmatrix} 1 \end{bmatrix}, \\
  H_2 &= \begin{bmatrix}
    1 &  1 \\
    1 & -1
  \end{bmatrix}, \\
  H_4 &= \begin{bmatrix}
    1 &  1 &  1 &  1\\
    1 & -1 &  1 & -1\\
    1 &  1 & -1 & -1\\
    1 & -1 & -1 &  1
  \end{bmatrix},
\end{align}</math>

and

:<math>
  H_{2^k} = \begin{bmatrix}
     H_{2^{k-1}} &  H_{2^{k-1}}\\
     H_{2^{k-1}} & -H_{2^{k-1}}
  \end{bmatrix} = H_2 \otimes H_{2^{k-1}},
</math>

for <math> 2 \le k \in N </math>, where <math> \otimes </math> denotes the [[Kronecker product]].

In this manner, Sylvester constructed Hadamard matrices of order 2<sup>''k''</sup> for every non-negative [[integer]] ''k''.<ref>J.J. Sylvester. ''Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton's rule, ornamental tile-work, and the theory of numbers.'' [[Philosophical Magazine]], 34:461–475, 1867</ref>

Sylvester's matrices have a number of special properties. They are [[symmetric matrix|symmetric]] and, when ''k''&nbsp;≥&nbsp;1 (2<sup>''k''</sup> &nbsp;>&nbsp;1), have [[trace (linear algebra)|trace]] zero. The elements in the first column and the first row are all positive. The elements in all the other rows and columns are evenly divided between [[sign (mathematics)|positive and negative]]. Sylvester matrices are closely connected with [[Walsh function]]s.

[[File:Binary Walsh matrix 16.svg|thumb|320px|Binary Hadamard matrix as a [[matrix multiplication|matrix product]].
The binary matrix (white 0, red 1) is the result with operations in [[finite field|'''F'''<sub>2</sub>]]. The gray numbers show the result with operations in <math>\mathbb{N}</math>.]]
===Alternative construction===
If we map the elements of the Hadamard matrix using the [[group homomorphism]] <math> (\{1, -1\}, \times) \rightarrow (\{0, 1\}), +) </math>, where <math>(\{0, 1\}), +) </math> is the additive group of the [[finite field|field]] <math>\mathrm{GF}(2)</math> with two elements, we can describe an alternative construction of Sylvester's Hadamard matrix. First consider the matrix <math> F_n </math>, the <math> n\times 2^n </math> matrix whose columns consist of all ''n''-bit numbers arranged in ascending counting order. We may define <math> F_n </math> recursively by

:<math>\begin{align}
  F_1 &= \begin{bmatrix}0 & 1\end{bmatrix} \\
  F_n &= \begin{bmatrix}
    0_{1\times 2^{n-1}} & 1_{1\times 2^{n-1}} \\
    F_{n-1}             & F_{n-1}
  \end{bmatrix}.
\end{align}</math>

It can be shown by [[mathematical induction|induction]] that the image of the Hadamard matrix under the above homomorphism is given by

: <math>H_{2^n} \mapsto F_n^\textsf{T} F_n,</math>

where the matrix arithmetic is done over <math>\mathrm{GF}(2)</math>.

This construction demonstrates that the rows of the Hadamard matrix <math> H_{2^n} </math> can be viewed as a length <math> 2^n </math> linear [[error-correcting code]] of [[linear code#Popular notation|rank]] ''n'', and [[linear code#Properties|minimum distance]] <math> 2^{n-1} </math> with [[linear code#Popular notation|generating matrix]] <math> F_n. </math>

This code is also referred to as a [[Walsh code]]. The [[Hadamard code]], by contrast, is constructed from the Hadamard matrix <math> H_{2^n} </math> by a slightly different procedure.