Hadamard matrix

 ( Combinatorial Design ) 

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 geometry terms, this means that each pair of rows in a Hadamard matrix represents two perpendicular vectors, while in combinatorics terms, it means that each pair of rows has 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 parallelotope spanned by the rows of an n × n Hadamard matrix has the maximum possible 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 error-correcting code using a Hadamard code (generalized in Reed–Muller codes), and are also used in balanced repeated replication (BRR), used by 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 matrix. In fact:

$H\; H^\backslash textsf\{T\}\; =\; n\; I\_n$

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 and each have length $\backslash sqrt\{n\}\backslash ,.$ Dividing H through by this length gives an orthogonal matrix whose transpose is thus its inverse:

$\backslash frac\{1\}\{\backslash sqrt\{n\}\}\; H^\backslash textsf\{T\}\; =\; \backslash sqrt\{n\}\; H^\{-1\}$

Multiplying by the length again gives the equality above. As a result,

$\backslash operatorname\{det\}(H)\; =\; \backslash pm\backslash ,\; n^\{n/2\},$

where det( H) is the determinant of H.

Suppose that M is a complex number 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.

---

Proof The proof of the nonexistence of Hadamard matrices with dimensions other than 1, 2, or a multiple of 4 follows:

If $n>1$, then there is at least one scalar product of 2 rows which has to be 0. The scalar product is a sum of n values each of which is either 1 or −1, therefore the sum is odd for odd n, so n must be even.

If $n\; =\; 4\; m\; +\; 2$ with $m\; \backslash geq\; 1$, and there exists an $n\; \backslash times\; n$ Hadamard matrix $H\; =\; (h\_\{i,j\})\_\{i,j\; \backslash in\; \backslash \{0,1,...,n-1\backslash \}\}$, then it has the property that for any $k\; \backslash neq\; l$:

$\backslash sum\_\{i=0\}^\{n-1\}\; h\_\{k,i\}\; h\_\{l,i\}\; =\; 0$

Now we define the matrix $A\; =\; (a\_\{i,j\})\_\{i,j\; \backslash in\; \backslash \{0,1,...,n-1\backslash \}\}$ by setting $a\_\{i,j\}\; =\; h\_\{0,j\}h\_\{i,j\}$. Note that $A$ has all 1s in row 0. We check that $A$ is also a Hadamard matrix:

$\backslash sum\_\{i=0\}^\{n-1\}\; a\_\{k,i\}\; a\_\{l,i\}\; =\; \backslash sum\_\{i=0\}^\{n-1\}\; h\_\{0,i\}\; h\_\{k,i\}\; h\_\{0,i\}\; h\_\{l,i\}\; =\; \backslash sum\_\{i=0\}^\{n-1\}\; h\_\{0,i\}^2\; h\_\{k,i\}\; h\_\{l,i\}\; =\; \backslash sum\_\{i=0\}^\{n-1\}\; h\_\{k,i\}\; h\_\{l,i\}\; =\; 0.$

Row 1 and row 2, like all other rows except row 0, must have $n/2$ entries of 1 and $n/2$ entries of −1 each. (*)

Let $\backslash alpha$ denote the number of 1s of row 2 beneath 1s in row 1. Let $\backslash beta$ denote the number of −1s of row 2 beneath 1s in row 1. Let $\backslash gamma$ denote the number of 1s of row 2 beneath −1s in row 1. Let $\backslash delta$ denote the number of −1s of row 2 beneath −1s in row 1.

Row 2 has to be orthogonal to row 1, so the number of products of entries of the rows resulting in 1, $\backslash alpha\; +\; \backslash delta$, has to match those resulting in −1, $\backslash beta\; +\; \backslash gamma$. Due to (*), we also have $n/2\; =\; \backslash alpha\; +\; \backslash gamma\; =\; \backslash beta\; +\; \backslash delta$, from which we can express $\backslash gamma\; =\; n/2\; -\; \backslash alpha$ and $\backslash delta\; =\; n/2\; -\; \backslash beta$ and substitute:

$\backslash alpha\; +\; \backslash delta\; =\; \backslash beta\; +\; \backslash gamma$

$\backslash alpha\; +\; \backslash frac\{n\}\{2\}\; -\; \backslash beta\; =\; \backslash beta\; +\; \backslash frac\{n\}\{2\}\; -\; \backslash alpha$

$\backslash alpha\; -\; \backslash beta\; =\; \backslash beta\; -\; \backslash alpha$

$\backslash alpha\; =\; \backslash beta$

But we have as the number of 1s in row 1 the odd number $n/2\; =\; \backslash alpha\; +\; \backslash beta$, contradiction.

---

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\\
 H & -H
     

\end{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 matrix.

$\backslash begin\{align\}$

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

\end{align}

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\; \backslash le\; k\; \backslash in\; N$, where $\backslash 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, 1867

Sylvester's matrices have a number of special properties. They are symmetric matrix and, when k ≥ 1 (2 ^k  > 1), 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 .

. The binary matrix (white 0, red 1) is the result with operations in finite field. The gray numbers show the result with operations in $\backslash mathbb\{N\}$.]]

---

Alternative construction If we map the elements of the Hadamard matrix using the group homomorphism $(\backslash \{1,\; -1\backslash \},\; \backslash times)\; \backslash rightarrow\; (\backslash \{0,\; 1\backslash \}),\; +)$, where $(\backslash \{0,\; 1\backslash \}),\; +)$ is the additive group of the finite field $\backslash mathrm\{GF\}(2)$ with two elements, 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 n-bit numbers arranged in ascending counting order. We may define $F\_n$ recursively by

$\backslash begin\{align\}$

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

\end{align}

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

$H\_\{2^n\}\; \backslash mapsto\; F\_n^\backslash textsf\{T\}\; F\_n,$

where the matrix arithmetic is done over $\backslash mathrm\{GF\}(2)$.

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. 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 problem in the theory of Hadamard matrices is one of existence. Specifically, the Hadamard conjecture proposes that a Hadamard matrix of order 4 k exists for every positive integer k. The Hadamard conjecture has also been attributed to Paley, although it was considered implicitly by others prior to Paley's work..

A generalization of Sylvester's construction proves that if $H\_n$ and $H\_m$ are Hadamard matrices of orders n and m respectively, then $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). In 1933, Raymond Paley discovered the Paley construction, which 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. His method uses .

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 Leonard Baumert, Golomb, and Hall in 1962 at JPL. They used a construction, due to Williamson, that has yielded many additional orders. Many other methods for constructing Hadamard matrices are now known.

In 2005, Hadi Kharaghani and Behruz Tayfeh-Rezaie published their construction of a Hadamard matrix of order 428. As a result, the smallest order for which no Hadamard matrix is presently known is 668.

By 2014, there were 12 multiples of 4 less than 2000 for which no Hadamard matrix of that order was known. They are: 668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, and 1964.

---

Equivalence and uniqueness 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 transpose, there are 4 inequivalent matrices of order 16, 3 of order 20, 36 of order 24, and 294 of order 28.

Hadamard matrices are also uniquely recoverable, in the following sense: If an Hadamard matrix $H$ of order $n$ has $O(n^2/\backslash log\; n)$ entries randomly deleted, then with overwhelming likelihood, one can perfectly recover the original matrix $H$ from the damaged one. The algorithm of recovery has the same computational cost as matrix inversion.

---

Special cases Many special cases of Hadamard matrices have been investigated in the mathematical literature.

---

Skew Hadamard matrices A Hadamard matrix H is skew if $H^\backslash textsf\{T\}\; +\; H\; =\; 2I.$ A skew Hadamard matrix remains a skew Hadamard matrix after multiplication of any row and its corresponding column by −1. This makes it possible, for example, to normalize a skew Hadamard matrix so that all elements in the first row equal 1.

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. In a mathematical tournament of order n, each of n players plays one match against each of the other players, each match resulting in a win for one of the players and a loss for the other. A tournament is regular if each player wins the same number of matches. A regular tournament is doubly regular if the number of opponents beaten by both of two distinct players is the same for all pairs of distinct players. Since each of the n( n − 1)/2 matches played results in a win for one of the players, each player wins ( n − 1)/2 matches (and loses the same number). Since each of the ( n − 1)/2 players defeated by a given player also loses to ( n − 3)/2 other players, the number of player pairs ( i, j) such that j loses both to i and to the given player is ( n − 1)( n − 3)/4. The same result should be obtained if the pairs are counted differently: the given player and any of the n − 1 other players together defeat the same number of common opponents. This common number of defeated opponents must therefore be ( n − 3)/4. A skew Hadamard matrix is obtained by introducing an additional player who defeats all of the original players and then forming a matrix with rows and columns labeled by players according to the rule that row i, column j contains 1 if i =  j or i defeats j and −1 if j defeats i. This correspondence in reverse produces a doubly regular tournament from a skew Hadamard matrix, assuming the skew Hadamard matrix is normalized so that all elements of the first row equal 1.

---

Regular Hadamard matrices 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 square number. A circulant matrix is manifestly regular, and therefore a circulant Hadamard matrix would have to be of square order. Moreover, if an n × n circulant Hadamard matrix existed with n > 1 then n would necessarily have to be of the form 4 u² with u odd.

---

Circulant Hadamard matrices 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⁴.

---

Generalizations One basic generalization is a weighing matrix. A weighing matrix is a square matrix in which entries may also be zero and which satisfies $WW^\backslash textsf\{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 and the theory of quantum computation. Butson-type 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.

---

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.
• 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
• Compressed sensing for signal processing and under-determined linear systems (inverse problems)
• Quantum Hadamard gate for quantum computing and the Hadamard transform for quantum algorithms.

---

See also

• Combinatorial design
• Hadamard transform
• Quincunx matrix
• Walsh matrix
• Weighing matrix
• Quantum logic gate

---

Notes

---

Further reading

• (2026). 9781402075995, Kluwer. ISBN 9781402075995
• (1997). 9780792398264, Kluwer. ISBN 9780792398264

---

External links

• Skew Hadamard matrices of all orders up to 100, including every type with order up to 28;
• in OEIS
• On-line utility to obtain all orders up to 1000, except 668, 716, 876 & 892.
• R-Package to generate Hadamard Matrices using R
• JPL: In 1961, mathematicians from NASA’s Jet Propulsion Laboratory and Caltech worked together to construct a Hadamard Matrix containing 92 rows and columns

Post Comment