In mathematics, a Hadamard matrix, named after the French mathematician Jacques Hadamard, 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 ndimensional parallelotope spanned by the rows of an n×n Hadamard matrix has the maximum possible ndimensional volume among parallelotopes 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 and so, is an extremal solution of Hadamard's maximal determinant problem.
Certain Hadamard matrices can almost directly be used as an errorcorrecting 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.
Properties
Let H be a Hadamard matrix of order n. The transpose of H is closely related to its inverse. The correct formula is:
 $H\; H^\{\backslash mathrm\{T\}\}\; =\; n\; I\_n\; \backslash $
where I_{n} is the n × n identity matrix and H^{T} is the transpose of H. To see that this is true, notice that the rows of H are all orthogonal vectors over the field of real numbers and each have length $\backslash sqrt\; n$. Dividing H through by this length gives an orthogonal matrix whose transpose is thus its inverse. Multiplying by the length again gives the equality above. As a result,
 $\backslash operatorname\{det\}(H)\; =\; \backslash pm\; n^\{\backslash frac\{n\}\{2\}\},$
where det(H) is the determinant of H.
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
 $\backslash operatorname\{det\}(M)\; \backslash 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
 $\backslash begin\{bmatrix\}\; H\; \&\; H\backslash \backslash \; H\; \&\; H\backslash 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^{k1}} & H_{2^{k1}}\\
H_{2^{k1}} & H_{2^{k1}}\end{bmatrix} = H_2\otimes H_{2^{k1}},
for $2\; \backslash le\; k\; \backslash in\; N$, where $\backslash left.\backslash otimes\backslash right.$ denotes the Kronecker product.
In this manner, Sylvester constructed Hadamard matrices of order 2^{k} for every nonnegative integer k.^{[1]}
Sylvester's matrices have a number of special properties. They are symmetric and have trace zero. 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.
Alternative construction
If we map the elements of the Hadamard matrix using the group homomorphism $\backslash \{1,1,\backslash times\backslash \}\backslash mapsto\; \backslash \{0,1,\backslash oplus\backslash \}$, we can describe an alternative construction of Sylvester's Hadamard matrix. First consider the matrix $F\_n$, the $n\backslash times\; 2^n$ matrix whose columns consist of all nbit numbers arranged in ascending counting order. We may define $F\_n$ recursively by
 $$
F_1=\begin{bmatrix}
0 & 1\end{bmatrix}
 $$
F_n=\begin{bmatrix}
0_{1\times 2^{n1}} & 1_{1\times 2^{n1}} \\
F_{n1} & F_{n1} \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^{\rm T}F_n.
This construction demonstrates that the rows of the Hadamard matrix $H\_\{2^n\}$ can be viewed as a length $2^n$ linear errorcorrecting code of rank n, and minimum distance $2^\{n1\}$ with generating matrix $F\_n.$
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.
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.
A generalization of Sylvester's construction proves that if $H\_n$ and $H\_m$ are Hadamard matrices of orders n and m respectively, then $\backslash scriptstyle\; H\_n\; \backslash otimes\; H\_m$ is a Hadamard matrix of order nm. This result is used to produce Hadamard matrices of higher order once those of smaller orders are known.
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 at JPL.^{[4]} They used a construction, due to Williamson,^{[5]} that has yielded many additional orders. Many other methods for constructing Hadamard matrices are now known.
In 2005, Hadi Kharaghani and Behruz TayfehRezaie published their construction of a Hadamard matrix of order 428.^{[6]} As a result, the smallest order for which no Hadamard matrix is presently known is 668.
As of 2008^{[update]}, there are 13 multiples of 4 less than or equal to 2000 for which no Hadamard matrix of that order is known.^{[7]} They are:
668, 716, 892, 1004, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, and 1964.
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. Using a coarser notion of equivalence that also allows transposition, there are 4 inequivalent matrices of order 16, 3 of order 20, 36 of order 24, and 294 of order 28.^{[8]}
Skew Hadamard matrices
A Hadamard matrix H is skew if $H^\{\backslash rm\; T\}\; +\; H=\; 2I.\; \backslash ,$
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
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 $WW^\{T\}=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 I_{n} where H^{*} is the conjugate transpose of H. Complex Hadamard matrices arise in the study of operator algebras and the theory of quantum computation.
Butsontype Hadamard matrices are 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.
Regular Hadamard matrices are real Hadamard matrices whose row and column sums are all equal. A necessary condition on the existence of a regular n×n Hadamard matrix is that n be a perfect square. A circulant matrix is manifestly regular, and therefore a circulant Hadamard matrix would have to be of perfect square order. Moreover, if an n×n circulant Hadamard
matrix existed with n > 1 then n would necessarily have to be of the form 4u^{2} with u odd.^{[9]}^{[10]}
The circulant Hadamard matrix conjecture, however, asserts that, apart from the known 1×1 and 4×4 examples, no such matrices exist. This was verified for all but 26 values of u less than 10^{4}.^{[11]}
Practical applications
 Olivia MFSK – an amateurradio digital protocol designed to work in difficult (low signaltonoise 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.
 Feedback Delay Networks – Digital reverberation devices which use Hadamard matrices to blend sample values
 Plackett–Burman design of experiments for investigating the dependence of some measured quantity on a number of independent variables.
 Robust parameter designs for investigating noise factor impacts on responses
See also
Notes
Further reading
External links
 Skew Hadamard matrices of all orders up to 100, including every type with order up to 28;

 Online utility to obtain all orders up to 1000, except 668, 716, 876 & 892.

This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.