Hadamard matrix
|
|
In mathematics, a Hadamard matrix is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal. Such matrices are used in error-correcting codes such as the Reed-Muller code. They are named after the French mathematician Jacques Hadamard.
| Contents |
Properties
It follows from the definition that a Hadamard matrix H of order n satisfies
- <math> H H^{\mathrm{T}}= n I_n <math>
where In is the n × n identity matrix.
Suppose that M is a real matrix of order n, whose entries are bounded by |Mij| ≤1. Then Hadamard's determinant bound states that
- <math> |\operatorname{det}(M)| \leq n^{n/2}. <math>
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
- <math>\begin{bmatrix} H & H\\ H & -H\end{bmatrix}<math>
is a Hadamard matrix of order 2n. This observation can be applied repeatedly and leads to the following series of matrices.
- <math> H_1 = \begin{bmatrix}1\end{bmatrix} <math>
- <math> H_2 = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} <math>
- <math> H_4 = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix} <math>
- <math> \vdots <math>
In this manner, Sylvester constructed Hadamard matrices of order 2k 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.
References
- H. Kharaghani and B. Tayfeh-Rezaie, A Hadamard matrix of order 428 (http://math.ipm.ac.ir/tayfeh-r/papersandpreprints/h428.pdf), 2004.fr:Matrice de Hadamard