- Hadamard matrix
In

mathematics , a**Hadamard matrix**is asquare matrix whose entries are either +1 or −1 and whose rows are mutuallyorthogonal . This means that every two different rows in a Hadamard matrix represent twoperpendicular vectors. Such matrices can almost directly be used as anerror-correcting code using aHadamard code (generalized inReed–Muller code s), and are also used inbalanced repeated replication (BRR), used bystatistician s to estimate thevariance of aparameter estimator . Hadamard matrices are named after the Frenchmathematician Jacques Hadamard .**Properties**It follows from the definition that a Hadamard matrix "H" of order "n" satisfies

:$H\; H^\{mathrm\{T\; =\; n\; I\_n$

where "I

_{n}" is the "n" × "n"identity matrix . Thus $det\; H\; =pm\; n^\{n/2\}.$Suppose that "M" is a complex matrix of order "n", whose entries are bounded by |"M

_{ij}"| ≤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.

**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:$egin\{bmatrix\}\; H\; H\backslash \; H\; -Hend\{bmatrix\}$ 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 matrices.:$H\_1\; =\; egin\{bmatrix\}1\; end\{bmatrix\},$ :$H\_2\; =\; egin\{bmatrix\}1\; 1\; \backslash 1\; -1\; end\{bmatrix\},$

and

:$H\_\{2^k\}\; =\; egin\{bmatrix\}H\_\{2^\{k-1\; H\_\{2^\{k-1\backslash H\_\{2^\{k-1\; -H\_\{2^\{k-1end\{bmatrix\}\; =\; H\_2otimes\; H\_\{2^\{k-1,$

for $2\; le\; k\; in\; N$, where $otimes$ denotes the

Kronecker product .In this manner, Sylvester constructed Hadamard matrices of order 2

^{"k"}for every non-negative integer "k". [*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, 1867Sylvester's matrices have a number of special properties. They are symmetric and

traceless . The elements in the first column and the first row are allpositive . The elements in all the other rows and columns are evenly divided between positive and negative. Sylvester matrices are closely connected withWalsh function s.**Alternative construction**If we map the elements of the Hadamard matrix using the

group homomorphism $\{1,-1,\; imes\}mapsto\; \{0,1,oplus\}$, we can describe an alternative construction of Sylvester's Hadamard matrix. First consider the matrix $F\_n$, the $n\; imes\; 2^n$ matrix whose columns consist of all "n"-bit numbers arranged in ascending counting order. We may define $F\_n$ recursively by:$F\_1=egin\{bmatrix\}0\; 1end\{bmatrix\}$

:$F\_n=egin\{bmatrix\}0\_\{1\; imes\; 2^\{n-1\; 1\_\{1\; imes\; 2^\{n-1\; \backslash F\_\{n-1\}\; F\_\{n-1\}\; end\{bmatrix\}.$

In 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 $2^n$ linear error-correcting code of rank "n", and minimum distance $2^\{n-1\}$ with generating matrix $F\_n.$

This code is also referred to as a

Walsh code . (Not to be confused with theHadamard code , which is constructed from the Hadamard matrix $H\_\{2^n\}$ by a slightly different procedure.)**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 4"k" 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). [

*J. Hadamard. "Résolution d'une question relative aux déterminants."*] InBulletin des Sciences Mathématiques , 17:240-246, 18931933 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 4and that produces a Hadamard matrix of order 2("q"+1) when "q" is a prime power that is congruent to 1 modulo 4 [*R. E. A. C. Paley. "On orthogonal matrices."*] . His method usesJournal of Mathematics and Physics , 12:311–320, 1933.finite field s. 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 in1962 . 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.**Equivalence of Hadamard matrices**Two Hadamard matrices are considered equivalent if one can be obtained from the other by negating rows, negating columns, interchanging rows, and interchanging columns. Up to equivalence, there is a unique Hadamard matrix in orders 1, 2, 4, 8, and 12. There are 5 inequivalent matrices in order 16, 3 in order 20, 60 in order 24, and 487 in order 28. Millions of inequivalent matrices are known in orders 32, 36, and 40.

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

**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 generalization arecomplex Hadamard matrices in which the entries are complex numbers of unit modulus and for which the matrix satisfies "H H^{*}= n I_{n}" where "H^{*}" is theconjugate transpose of "H". Complex Hadamard matrices arise in the study ofoperator algebras and the theory ofquantum computation .Butson-type Hadamard matrices are a special case of complex Hadamard matrices in which the entries are taken to be "q"^{th}roots of unity . The term "complex Hadamard matrix" has been used by some authors to refer specifically to the case "q" = 4. A special case of real Hadamard matrices arecirculant Hadamard matrices . Such a square matrix is defined by its first row, and every other row is acyclic shift of its predecessor row. Circulant Hadamard matrices of orders 1 and 4 are known and it isconjecture d that no other orders exist.Regular Hadamard matrices are real Hadamard matrices whose row and column sums are all equal.**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 astatistical 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.**References****External links*** H. Kharaghani and B. Tayfeh-Rezaie, [

*http://math.ipm.ac.ir/tayfeh-r/papersandpreprints/h428.pdf "A Hadamard matrix of order 428"*] , 2004.*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.

*K.B. Reid & E. Brown, "Doubly regular tournaments are equivalent to skew Hadamard matrices", J. Combinatorial Theory A 12 (1972) 332-338.

* [

*http://rangevoting.org/SkewHad.html Skew Hadamard matrices*] of all orders up to 100, including every type with order up to 28;* [

*http://www.research.att.com/~njas/hadamard N.J.A. Sloane's Library of Hadamard Matrices*]* [

*http://www.iasri.res.in/webhadamard On-line utility*] to obtain all orders up to 1000, except 668, 716, 876 & 892.*R. K. Yarlagadda and J. E. Hershey, "Hadamard Matrix Analysis and Synthesis", (1996)

* [

*http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aoms/1177730883 "On Hotelling's Weighing Problem"*] , Alexander M. Mood, Ann. Math. Statist. Volume 17, Number 4 (1946), 432-446.

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

Matrix - получить на Академике рабочий купон на скидку Строительный Двор или выгодно matrix купить с бесплатной доставкой на распродаже в Строительный Двор

**Hadamard-Matrix**— Eine Hadamard Matrix vom Grad n ist eine Matrix, die ausschließlich die Zahlen 1 und − 1 als Koeffizienten enthält und bei der zudem alle Spalten orthogonal zueinander sind, ebenso alle Zeilen. Hadamard Matrizen sind nach dem französischen… … Deutsch Wikipedia**Complex Hadamard matrix**— A complex Hadamard matrix is any complex matrix H satisfying two conditions: unimodularity (the modulus of each entry is unity): orthogonality: , where denotes the Hermitian transpose of H and … Wikipedia**Regular Hadamard matrix**— In mathematics a regular Hadamard matrix is a Hadamard matrix whose row and column sums are all equal. While the order of a Hadamard matrix must be 1, 2, or a multiple of 4, regular Hadamard matrices carry the further restriction that the order… … Wikipedia**Butson-type Hadamard matrix**— In mathematics, a complex Hadamard matrix H of size N with all its columns (rows) mutually orthogonal, belongs to the Butson type H ( q , N ) if all its elements are powers of q th root of unity,:: (H {jk})^q=1 {quad m for quad} j,k=1,2,dots,N.… … Wikipedia**Hadamard-Code**— Matrix des [32,6,16] Hadamard Codes der NASA Raumsonde Mariner 9 (1971/1972). Die Farbe Schwarz kodiert die Binärziffer 1, und die Farbe Weiß kodiert die Binärziffer 0 … Deutsch Wikipedia**Hadamard (disambiguation)**— Hadamard may refer to* Jacques Hadamard * Hadamard gate * Hadamard matrix * Hadamard s inequality * Hermite–Hadamard inequality * Walsh–Hadamard transform * Fast Walsh–Hadamard transform … Wikipedia**Hadamard transform**— The Hadamard transform (also known as the Walsh Hadamard transform, Hadamard Rademacher Walsh transform, Walsh transform, or Walsh Fourier transform) is an example of a generalized class of Fourier transforms. It is named for the French… … Wikipedia**Hadamard code**— The Hadamard code, named after Jacques Hadamard, is a system used for signal error detection and correction. It is one of the family of [2 n , n + 1, 2 n − 1] codes. Especially for large n it has a poor rate but it is capable of correcting many… … Wikipedia**Hadamard**— Jacques Salomon Hadamard Jacques Salomon Hadamard (* 8. Dezember 1865 in Versailles; † 17. Oktober 1963 in Paris) war ein französischer Mathematiker. Inhaltsverzeichnis 1 … Deutsch Wikipedia**Hadamard's inequality**— In mathematics, Hadamard s inequality, named after Jacques Hadamard, bounds above the volume in Euclidean space of n dimensions marked out by n vectors: vi for 1 le; i le; n .It states, in geometric terms, that this is at a maximum when the… … Wikipedia