Welcome to mapoid.com on July 9 2009.
This is an internet experiment running to monitor browsing habbits of individuals through wikipedia contents.

Hadamard matrix

From Wikipedia, the free encyclopedia

  (Redirected from Hadamard matrices)
Jump to: navigation, search

In mathematics, a Hadamard matrix is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal. In geometric terms, this means that every two different rows in a Hadamard matrix represent two perpendicular vectors, while in combinatorial terms, it means that every two different rows have matching entries in exactly half of their columns and mismatched entries in the remaining columns. It is a consequence of this definition that the corresponding properties hold for columns as well as rows. The n-dimensional parallelepiped spanned by the rows of an n×n Hadamard matrix has the maximum possible n-dimensional volume among parallelepipeds spanned by vectors whose entries are bounded in absolute value by 1. Equivalently, a Hadamard matrix has maximal determinant among matrices with entries of absolute value less than or equal to 1.

Certain Hadamard matrices can almost directly be used as an error-correcting code using a Hadamard code (generalized in Reed–Muller codes), and are also used in balanced repeated replication (BRR), used by statisticians to estimate the variance of a parameter estimator. Hadamard matrices are named after the French mathematician Jacques Hadamard.

Contents

[edit] Properties

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

H H^{\mathrm{T}} = n I_n \

where In is the n × n identity matrix and HT is the transpose of H. Consequently the determinant of H equals ±nn/2.

Suppose that M is a complex matrix of order n, whose entries are bounded by |Mij| ≤1, for each i, j between 1 and n. Then Hadamard's determinant bound states that

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

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

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

[edit] 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

\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 sequence of matrices, also called Walsh matrices.

H_1 = \begin{bmatrix} 1 \end{bmatrix},
H_2 = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix},

and

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

for 2 \le k \in N , where \left.\otimes\right. denotes the Kronecker product.

In this manner, Sylvester constructed Hadamard matrices of order 2k for every non-negative integer k. [1]

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.

[edit] Alternative construction

If we map the elements of the Hadamard matrix using the group homomorphism \{1,-1,\times\}\mapsto \{0,1,\oplus\} , we can describe an alternative construction of Sylvester's Hadamard matrix. First consider the matrix Fn, the n\times 2^n matrix whose columns consist of all n-bit numbers arranged in ascending counting order. We may define Fn recursively by

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

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

H_{2^n}=F_n^TF_n.

This construction demonstrates that the rows of the Hadamard matrix H_{2^n} can be viewed as a length 2n linear error-correcting code of rank n, and minimum distance 2n − 1 with generating matrix Fn.

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

[edit] 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 1867 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 (in 1893).[2] In 1933 Raymond Paley discovered a construction that produces a Hadamard matrix of order q+1 when q is any prime power that is congruent to 3 modulo 4 and that produces a Hadamard matrix of order 2(q+1) when q is a prime power that is congruent to 1 modulo 4.[3] His method uses finite fields. The Hadamard conjecture should probably be attributed to Paley.

The smallest order that cannot be constructed by a combination of Sylvester's and Paley's methods is 92. A Hadamard matrix of this order was found using a computer by Baumert, Golomb, and Hall in 1962. They used a construction, due to Williamson, that has yielded many additional orders. 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. As a result, the smallest order for which no Hadamard matrix is presently known is 668.

As of 2008, there are 13 integers n less than or equal to 500 for which no Hadamard matrix of order 4n is known.[4] They are: 167, 179, 223, 251, 283, 311, 347, 359, 419, 443, 479, 487, 491.

[edit] Equivalence of Hadamard matrices

Two Hadamard matrices are considered equivalent if one can be obtained from the other by negating rows or columns, or by interchanging rows or columns. Up to equivalence, there is a unique Hadamard matrix of orders 1, 2, 4, 8, and 12. There are 5 inequivalent matrices of order 16, 3 of order 20, 60 of order 24, and 487 of order 28. Millions of inequivalent matrices are known for orders 32, 36, and 40.

[edit] Skew Hadamard matrices

A Hadamard matrix H is skew if H^T + H= 2I. \,

Reid and Brown in 1972 showed that there exists a "doubly regular tournament of order n" if and only if there exists a skew Hadamard matrix of order n+1.

[edit] Generalizations and special cases

Many generalizations and special cases of Hadamard matrices have been investigated in the mathematical literature. One basic generalization is the weighing matrix, a square matrix in which entries may also be zero and which satisfies WWT = wI for some w, its weight. A weighing matrix with its weight equal to its order is a Hadamard matrix.

Another generalization defines a complex Hadamard matrix to be a matrix in which the entries are complex numbers of unit modulus and which satisfies H H*= n In where H* is the conjugate transpose of H. Complex Hadamard matrices arise in the study of operator algebras and the theory of quantum computation. Butson-type Hadamard matrices are complex Hadamard matrices in which the entries are taken to be qth roots of unity. The term "complex Hadamard matrix" has been used by some authors to refer specifically to the case q = 4.

Circulant Hadamard matrices are real Hadamard matrices in which every row except the first is a cyclic shift of its predecessor. Circulant Hadamard matrices of orders 1 and 4 are known and it is conjectured that no other orders exist.

Regular Hadamard matrices are real Hadamard matrices whose row and column sums are all equal.

[edit] Practical applications

  • Olivia MFSK - an amateur-radio digital protocol designed to work in difficult (low signal-to-noise ratio plus multipath propagation) conditions on shortwave bands.
  • Balanced Repeated Replication (BRR) - a technique used by statisticians to estimate the variance of a statistical estimator.
  • coded aperture spectrometry - an instrument for measuring the spectrum of light. The mask element used in coded aperture spectrometers is often a variant of a Hadamard matrix.

[edit] Notes

  1. ^ 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
  2. ^ J. Hadamard. Résolution d'une question relative aux déterminants. Bulletin des Sciences Mathématiques, 17:240-246, 1893
  3. ^ R. E. A. C. Paley. On orthogonal matrices. Journal of Mathematics and Physics, 12:311–320, 1933.
  4. ^ Đoković, Dragomir Ž (2008). "Hadamard matrics of order 764 exist". Combinatorica 28 (4): 487-489. 

[edit] References

Further Reading

  • S. Georgiou, C. Koukouvinos, J. Seberry, Hadamard matrices, orthogonal designs and construction algorithms, pp. 133-205 in DESIGNS 2002: Further computational and constructive design theory, Kluwer 2003.
  • R. K. Yarlagadda and J. E. Hershey, "Hadamard Matrix Analysis and Synthesis, (1996)
  • K.B. Reid & E. Brown, Doubly regular tournaments are equivalent to skew Hadamard matrices, J. Combinatorial Theory A 12 (1972) 332-338.

[edit] External links

Retrieved from "http://en.wikipedia.org/wiki/Hadamard_matrix"
Personal tools
Visit joltnews for the latest headlines
Visit bloit.com for company information
Geed Media does computer consulting on long island.
This page viewed times. See Logs