Hadamard matrix

A Hadamard matrix is a square matrix with entries +1, -1 whose rows are mutually orthogonal. From this definition it follows that a Hadamard matrix, H, of order n satisfies

$HH^{\mathrm {T} }=nI_{n}\quad$

where I_n is the n × n identity matrix.

Examples:

$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}}$

A real matrix, M, of order n, with bounded elements, |M_ij| ≤1 attains equality in Hadamard's determinant bound

$|\operatorname {det} (M)|\leq n^{n/2}$

if and only if it is a Hadamard matrix. The order of a Hadamard matrix must be 1, 2, or a multiple of 4. The most important open question in the theory of Hadamard matrices is that of existence. The Hadamard conjecture proposes that a Hadamard matrix of order 4k exists for every positive integer k. Following the announcement of the discovery of a Hadamard matrix of order 428 on 21 June 2004 by Hadi Kharaghani and Behruz Tayfeh-Rezaie, the smallest order for which no Hadamard matrix is presently known is 668.

Examples of Hadamard matrices were actually first constructed by James Joseph Sylvester. Let H be a Hadamard matrix of order n. Then the partitioned matrix

${\begin{bmatrix}H&H\\H&-H\end{bmatrix}}$

is a Hadamard matrix of order 2n. Applying this observation repeatedly, starting with the matrix H₁, Sylvester constructed Hadamard matrices of order 2^k for every non-negative integer k.

Sylvester's matrices have a number of special properties. They are symmetric and traceless. 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 positive and negative. Sylvester matrices are closely connected with Walsh functions.

Hadamard matrices of orders 12 and 20 were subsequently constructed by Hadamard. Raymond Paley later showed how to construct a Hadamard matrix of order q+1 where q is any power of a prime number which is congruent to 3 modulo 4. He also constructed matrices of order 2(q+1) for prime powers q which are congruent to 1 modulo 4. His method uses finite fields. The Hadamard conjecture should probably be attributed to Paley. Many other methods for constructing Hadamard matrices are now known.

Hadamard matrices have been used in error-correcting codes such as Reed-Muller.