Hadamard matrix

In mathematics, a Hadamard matrix is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal. This means that every two different rows in a Hadamard matrix represent two perpendicular vectors. Such matrices are used in error-correcting codes such as the Reed-Muller code. Hadamard matrices are also used in balanced repeated replication (BRR), which is a method used by statisticians to estimate the variance of a parameter estimator . They are named after the French mathematician Jacques Hadamard.

Properties

It follows from the definition that a Hadamard matrix H of order n satisfies

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

where I_n is the n × n identity matrix.

Suppose that M is a real matrix of order n, whose entries are bounded by |M_ij| ≤1. Then Hadamard's determinant bound states that

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

Equality is attained in this bound if and only if M is a Hadamard matrix.

The order of a Hadamard matrix must be 1, 2, or a multiple of 4.

Sylvester's construction

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. This observation can be applied repeatedly and leads to the following series of matrices.

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

$\vdots$

In this manner, 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.

The Hadamard conjecture

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.

Sylvester's construction yields Hadamard matrices of order 1, 2, 4, 8, 16, 32, etc. 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.

Hadi Kharaghani and Behruz Tayfeh-Rezaie announced on 21 June 2004 that they constructed a Hadamard matrix of order 428. The smallest order for which no Hadamard matrix is presently known is 668.

Generalizations and special cases

There are many generalizations and special cases of Hadamard matrices investigated in the mathematical literature. One basic generalization is a weighing matrix in which one allows also zeros in the entries of the matrix and requires the number of +1, −1 to be a certain constant throughout the matrix. Another special case are circulant Hadamard matrices. Such a square matrix is defined by its first row, and every other row is a cyclic shift of its predecessor row. Circulant Hadamard matrices of orders 1 and 4 are known and it is conjectured that no other orders exist.

References

• H. Kharaghani and B. Tayfeh-Rezaie, A Hadamard matrix of order 428, 2004.