Inmathematics, aHadamard matrix, named after the French mathematicianJacques Hadamard, is asquare matrix whose entries are either +1 or −1 and whose rows are mutuallyorthogonal. Ingeometric terms, this means that each pair of rows in a Hadamard matrix represents twoperpendicularvectors, while incombinatorial 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.

Then-dimensionalparallelotope spanned by the rows of ann ×n Hadamard matrix has the maximum possiblen-dimensionalvolume among parallelotopes spanned by vectors whose entries are bounded inabsolute value by 1. Equivalently, a Hadamard matrix has maximaldeterminant amongmatrices with entries of absolute value less than or equal to 1 and so is an extremal solution ofHadamard's maximal determinant problem.

Certain Hadamard matrices can almost directly be used as anerror-correcting code using aHadamard code (generalized inReed–Muller codes), and are also used inbalanced repeated replication (BRR), used bystatisticians to estimate thevariance of aparameterestimator.

LetH be a Hadamard matrix of ordern. Thetranspose ofH is closely related to itsinverse. In fact:

${\displaystyle H{H}^{\mathsf{\text{T}}}=n{I}_n}$

whereI_n is then ×nidentity matrix andH^T is the transpose ofH. To see that this is true, notice that the rows ofH are all orthogonal vectors over thefield ofreal numbers and each have length${\displaystyle \sqrt{n}.}$ DividingH through by this length gives anorthogonal matrix whose transpose is thus its inverse:

${\displaystyle \frac{1}{\sqrt{n}}{H}^{\mathsf{\text{T}}}=\sqrt{n}{H}^{-1}}$

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

${\displaystyle \det (H)=\pm n^{n/2},}$

where det(H) is the determinant ofH.

Suppose thatM is acomplex matrix of ordern, whose entries are bounded by |M_ij| ≤ 1, for eachi,j between 1 andn. ThenHadamard's determinant bound states that

${\displaystyle |\det (M)|\le n^{n/2}.}$

Equality in this bound is attained for a real matrixMif and only ifM is a Hadamard matrix.

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

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

If${\displaystyle n>1}$, then there is at least one scalar product of 2 rows which has to be 0. The scalar product is a sum ofn values each of which is either 1 or −1, therefore the sum isodd for oddn, son must beeven.

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

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

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

${\displaystyle \sum _{i=0}^{n-1}{a}_{k,i}{a}_{l,i}=\sum _{i=0}^{n-1}{h}_{0,i}{h}_{k,i}{h}_{0,i}{h}_{l,i}=\sum _{i=0}^{n-1}{h}_{0,i}^2{h}_{k,i}{h}_{l,i}=\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${\displaystyle n/2}$ entries of 1 and${\displaystyle n/2}$ entries of −1 each. (*)

Let${\displaystyle \alpha }$ denote the number of 1s of row 2 beneath 1s in row 1.Let${\displaystyle \beta }$ denote the number of −1s of row 2 beneath 1s in row 1.Let${\displaystyle \gamma }$ denote the number of 1s of row 2 beneath −1s in row 1.Let${\displaystyle \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,${\displaystyle \alpha +\delta }$, has to match those resulting in −1,${\displaystyle \beta +\gamma }$.Due to (*), we also have${\displaystyle n/2=\alpha +\gamma =\beta +\delta }$, from which we can express${\displaystyle \gamma =n/2-\alpha }$ and${\displaystyle \delta =n/2-\beta }$ and substitute:

${\displaystyle \alpha +\delta =\beta +\gamma }$

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

${\displaystyle \alpha -\beta =\beta -\alpha }$

${\displaystyle \alpha =\beta }$

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

Examples of Hadamard matrices were actually first constructed byJames Joseph Sylvester in 1867. LetH be a Hadamard matrix of ordern. Then the partitioned matrix

is a Hadamard matrix of order 2n. This observation can be applied repeatedly and leads to the following sequence of matrices, also calledWalsh matrices.

and

for${\displaystyle 2\le k\in N}$, where${\displaystyle \otimes }$ denotes theKronecker product.

In this manner, Sylvester constructed Hadamard matrices of order 2^k for every non-negativeintegerk.^[2]

Sylvester's matrices have a number of special properties. They aresymmetric and, whenk ≥ 1 (2^k  > 1), havetrace 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 betweenpositive and negative. Sylvester matrices are closely connected withWalsh functions.

If we map the elements of the Hadamard matrix using thegroup homomorphism${\displaystyle (\{1,-1\},\times )\to (\{0,1\}),+)}$, where${\displaystyle (\{0,1\}),+)}$ is the additive group of thefield${\displaystyle \mathrm{G}\mathrm{F}(2)}$ with two elements, we can describe an alternative construction of Sylvester's Hadamard matrix. First consider the matrix${\displaystyle F_n}$, the${\displaystyle n\times 2^n}$ matrix whose columns consist of alln-bit numbers arranged in ascending counting order. We may define${\displaystyle F_n}$ recursively by

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

${\displaystyle H_{2^n}\mapsto F_n^{\mathsf{\text{T}}}{F}_n,}$

where the matrix arithmetic is done over${\displaystyle \mathrm{G}\mathrm{F}(2)}$.

This construction demonstrates that the rows of the Hadamard matrix${\displaystyle H_{2^n}}$ can be viewed as a length${\displaystyle 2^n}$ linearerror-correcting code ofrankn, andminimum distance${\displaystyle 2^{n-1}}$ withgenerating matrix${\displaystyle F_n.}$

This code is also referred to as aWalsh code. TheHadamard code, by contrast, is constructed from the Hadamard matrix${\displaystyle H_{2^n}}$ by a slightly different procedure.

The most importantopen question in the theory of Hadamard matrices is one of existence. Specifically, theHadamard conjecture proposes that a Hadamard matrix of order 4k exists for every positive integerk. The Hadamard conjecture has also been attributed to Paley, although it was considered implicitly by others prior to Paley's work.^[3]

A generalization of Sylvester's construction proves that if${\displaystyle H_n}$ and${\displaystyle H_m}$ are Hadamard matrices of ordersn andm respectively, then${\displaystyle H_n\otimes H_m}$ is a Hadamard matrix of ordernm. 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).^[4] In 1933,Raymond Paley discovered thePaley construction, which produces a Hadamard matrix of orderq + 1 whenq is anyprime power that iscongruent to 3 modulo 4 and that produces a Hadamard matrix of order 2(q + 1) whenq is a prime power that is congruent to 1 modulo 4.^[5] His method usesfinite fields.

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 byBaumert,Golomb, andHall in 1962 atJPL.^[6] They used a construction, due toWilliamson,^[7] 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.^[8] 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.^[9] They are:668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, and 1964.

Two Hadamard matrices are consideredequivalent 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 acoarser notion of equivalence that also allowstransposition, there are 4 inequivalent matrices of order 16, 3 of order 20, 36 of order 24, and 294 of order 28.^[10]

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

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

A Hadamard matrixH isskew if${\displaystyle H^{\mathsf{\text{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 regulartournament of ordern if and only if there exists a skew Hadamard matrix of ordern + 1. In a mathematical tournament of ordern, each ofn 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 then(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 thatj loses both toi 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 then − 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 rowi, columnj contains 1 ifi = j ori defeatsj and −1 ifj defeatsi. 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.^[12]

Regular Hadamard matrices are real Hadamard matrices whose row and column sums are all equal. A necessary condition on the existence of a regularn ×n Hadamard matrix is thatn be asquare number. Acirculant matrix is manifestly regular, and therefore a circulant Hadamard matrix would have to be of square order. Moreover, if ann ×n circulant Hadamardmatrix existed withn > 1 thenn would necessarily have to be of the form 4u² withu odd.^[13][14]

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 ofu less than 10⁴.^[15]

One basic generalization is aweighing matrix. A weighing matrix is a square matrix in which entries may also be zero and which satisfies${\displaystyle W{W}^{\mathsf{\text{T}}}=wI}$ for some w, its weight. A weighing matrix with its weight equal to its order is a Hadamard matrix.^[16]

Another generalization defines acomplex Hadamard matrix to be a matrix in which the entries are complex numbers of unitmodulus and which satisfiesH H^* = n I_n whereH^* is theconjugate transpose ofH. Complex Hadamard matrices arise in the study ofoperator algebras and the theory ofquantum computation.Butson-type Hadamard matrices are complex Hadamard matrices in which the entries are taken to beq^throots of unity. The termcomplex Hadamard matrix has been used by some authors to refer specifically to the caseq = 4.

• 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 thevariance of astatistical estimator.
• Coded aperture spectrometry – an instrument for measuring thespectrum 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 ofindependent variables.
• Robust parameter designs for investigating noise factor impacts on responses
• Compressed sensing forsignal processing and under-determined linear systems (inverse problems)
• Quantum Hadamard gate forquantum computing and theHadamard transform for quantum algorithms.

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

• Baumert, L. D.; Hall, Marshall (1965)."Hadamard matrices of the Williamson type".Math. Comp.19 (91):442–447.doi:10.1090/S0025-5718-1965-0179093-2.MR 0179093.
• Georgiou, S.; Koukouvinos, C.; Seberry, J. (2003). "Hadamard matrices, orthogonal designs and construction algorithms".Designs 2002: Further computational and constructive design theory. Boston: Kluwer. pp. 133–205.ISBN 978-1-4020-7599-5.
• Goethals, J. M.; Seidel, J. J. (1970)."A skew Hadamard matrix of order 36".J. Austral. Math. Soc.11 (3):343–344.doi:10.1017/S144678870000673X.S2CID 14193297.
• Kimura, Hiroshi (1989). "New Hadamard matrix of order 24".Graphs and Combinatorics.5 (1):235–242.doi:10.1007/BF01788676.S2CID 39169723.
• Mood, Alexander M. (1964)."On Hotelling's Weighing Problem".Annals of Mathematical Statistics.17 (4):432–446.doi:10.1214/aoms/1177730883.
• Reid, K. B.; Brown, E. (1972)."Doubly regular tournaments are equivalent to skew Hadamard matrices".J. Combin. Theory Ser. A.12 (3):332–338.doi:10.1016/0097-3165(72)90098-2.
• Seberry Wallis, Jennifer (1976)."On the existence of Hadamard matrices".J. Comb. Theory A.21 (2):188–195.doi:10.1016/0097-3165(76)90062-5.
• Seberry, Jennifer (1980)."A construction for generalized hadamard matrices".J. Statist. Plann. Infer.4 (4):365–368.doi:10.1016/0378-3758(80)90021-X.
• Seberry, J.; Wysocki, B.; Wysocki, T. (2005)."On some applications of Hadamard matrices".Metrika.62 (2–3):221–239.doi:10.1007/s00184-005-0415-y.S2CID 40646.
• Spence, Edward (1995)."Classification of hadamard matrices of order 24 and 28".Discrete Math.140 (1–3):185–242.doi:10.1016/0012-365X(93)E0169-5.
• Yarlagadda, R. K.; Hershey, J. E. (1997).Hadamard Matrix Analysis and Synthesis. Boston: Kluwer.ISBN 978-0-7923-9826-4.

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

• Combinatorial design
• Matrices (mathematics)
• Unsolved problems in mathematics

• Articles with short description
• Short description is different from Wikidata
• Use dmy dates from February 2023