Fact-checked by Grok 2 weeks ago

Hadamard matrix

A Hadamard matrix of order n is an n \times n whose entries are either +1 or -1 and whose rows (equivalently, columns) are pairwise orthogonal, satisfying H H^T = n I_n. Such matrices achieve the maximum possible among all n \times n matrices with entries in \{-1, +1\}, specifically \det(H) = \pm n^{n/2}. They exist only if n = 1, n = 2, or n \equiv 0 \pmod{4}. Hadamard matrices were first studied by the French mathematician in 1893, in the context of bounding the growth of entire functions and maximizing determinants. In his seminal work, Hadamard conjectured that a Hadamard matrix exists for every order n satisfying the necessary condition n \equiv 0 \pmod{4} (beyond the known cases n=1,2), a statement known as the , which remains unsolved despite constructions for all multiples of 4 up to 664 and many larger orders, though the existence for order 668 and a few others remains unknown as of 2025. The conjecture has driven extensive research in combinatorial matrix theory since the mid-20th century, with notable advances including the Paley construction in 1933 using quadratic residues modulo prime powers. Key properties include the fact that any two rows of a Hadamard matrix agree in exactly n/2 positions and differ in the remaining n/2, ensuring their is zero. Normalization often involves scaling by $1/\sqrt{n} to yield unitary matrices, which extend to variants with entries on the unit circle. Constructions fall into recursive families like the Sylvester method—starting from the $1 \times 1 matrix {{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}} and doubling via \begin{pmatrix} H & H \\ H & -H \end{pmatrix}—yielding matrices for all powers of 2, as well as non-recursive methods like Paley's (for n = q+1 where q is a congruent to 3 4) and Williamson's (for orders $4t using four circulant matrices). Theorems such as MacPhail's () further explore their in unconditional of series in \ell^p spaces. Hadamard matrices find applications across diverse fields, including error-correcting codes where they enable efficient transmission, as in NASA's mission (1971) using punctured codes of length $2^n - 1. In , they underpin the fast for data compression and , analogous to the but over \pm 1 bases. employs them in Hadamard gates for creating superpositions and in for quantum random access codes. Additionally, they appear in experimental design for weighing problems in chemistry and statistics, optimizing orthogonal arrays for balanced incomplete block designs.

Fundamentals

Definition

A Hadamard matrix is named after the mathematician , who utilized such matrices in 1893 in the context of maximizing determinants. Although named after Hadamard, such matrices were first studied by J.J. Sylvester in 1867 under the name "anallagmatic pavements." Formally, a Hadamard matrix of order n is an n \times n [H](/page/H+) whose entries are either +1 or -1 and satisfies the condition [H](/page/H+) [H](/page/H+)^T = n I_n, where I_n denotes the n \times n and [H](/page/H+)^T is the of [H](/page/H+). Equivalently, the rows of [H](/page/H+) (or columns) are pairwise orthogonal, and each has equal Euclidean norm \sqrt{n}. A necessary condition for the existence of a Hadamard matrix of order n > 2 is that n is a multiple of 4 (with n=1 and n=2 also possible). The trivial examples include the $1 \times 1 matrix H = {{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}} and the $2 \times 2 matrix \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}. For consistency in discussions of Hadamard matrices, a common normalization convention sets the first row and first column to all +1.

Properties

A Hadamard matrix H of order n satisfies H H^T = n I_n, where the entries of H are \pm 1 and I_n is the n \times n . This condition implies that the rows of H are pairwise orthogonal vectors in \mathbb{R}^n. To see this, consider the (i,j)-entry of H H^T: for i = j, it is the squared norm of the i-th row, which equals n since the row consists of n entries each \pm 1 (so each squared entry is 1). For i \neq j, it is the of the i-th and j-th rows, which equals 0. Thus, the rows are orthogonal, and each has norm \sqrt{n}. Since H is real and square with orthogonal rows of equal norm, the columns are also pairwise orthogonal with the same norm, as H^T H = n I_n follows from the invertibility of H and the row property (specifically, H^T H = H^T (H H^T) H^{-T} = H^T (n I_n) H^{-T} = n I_n, but more directly, the column mirrors the row case due to the \pm 1 entries and symmetry of the definition). The relation H H^T = n I_n further implies that H / \sqrt{n} is an , i.e., U = H / \sqrt{n} satisfies U U^T = I_n and U^T U = I_n. Thus, H = \sqrt{n} \, U where U is orthogonal, meaning the singular values of H are all \sqrt{n}. The eigenvalues \lambda of H therefore satisfy |\lambda| = \sqrt{n}, as they are \sqrt{n} times the eigenvalues of U, which lie on the unit circle. In the special case where H is symmetric (i.e., H^T = H), H is orthogonally diagonalizable with real eigenvalues \pm \sqrt{n}, each of multiplicity n/2. Consequently, the trace of such a symmetric H is 0 for n > 2. The determinant of a Hadamard matrix satisfies |\det H| = n^{n/2}. This follows from Hadamard's inequality, which bounds the determinant of any real n \times n matrix A with columns a_1, \dots, a_n by |\det A| \leq \prod_{k=1}^n \|a_k\|_2. For H, each column has \|a_k\|_2 = \sqrt{n}, so |\det H| \leq (\sqrt{n})^n = n^{n/2}. Equality holds in Hadamard's inequality if and only if the columns a_1, \dots, a_n are pairwise orthogonal, a condition satisfied by H. To prove Hadamard's inequality, consider the volume interpretation: \det A is (up to sign) the volume of the parallelepiped spanned by the columns. By the properties of orthogonal projections and Cauchy-Schwarz, this volume is maximized when the vectors are orthogonal, with the bound given by the product of their lengths. More formally, one can use the QR decomposition A = Q R where Q is orthogonal and R upper triangular; then |\det A| = |\det R| = \prod |r_{ii}|, and by properties of the Gram-Schmidt process, |r_{ii}| \leq \|a_i - \proj_{\span\{a_1,\dots,a_{i-1}\}} a_i \| \leq \|a_i\|, yielding the product bound with equality under orthogonality. Hadamard matrices are closely related to matrices. A matrix C of order m has zero diagonal and off-diagonal entries \pm 1, satisfying C C^T = (m-1) I_m. For m \equiv 0 \pmod{4}, if there exists a matrix C of order m, then H = I_m + C is a Hadamard of order m. To derive this, note that the diagonal of H is all 1's (since C has zeros there), and off-diagonal entries are \pm 1. The key property is H H^T = (I_m + C)(I_m + C^T) = I_m + C + C^T + C C^T = I_m + C - C + (m-1) I_m = m I_m, using skew-symmetry (C^T = -C) and the conference condition. Conversely, if H is a Hadamard of order m \equiv 0 \pmod{4}, then C = H - I_m is a matrix of order m.

Constructions

Sylvester Construction

The Sylvester construction provides a recursive method for generating Hadamard matrices of orders that are powers of 2, beginning from a small initial matrix and iteratively doubling the size. This approach was first introduced by in 1867, who described the resulting structures as "anallagmatic pavements" in his work on inverse orthogonal matrices, predating Jacques Hadamard's later study of these objects by over two decades. The construction starts with the basic Hadamard matrix of order 1, denoted H_1 = {{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}}, or equivalently, the order-2 matrix H_2 = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, which satisfies the Hadamard property H_2 H_2^T = 2I_2. Given a Hadamard matrix H_m of order m, the Sylvester doubling procedure produces H_{2m} as the H_{2m} = \begin{pmatrix} H_m & H_m \\ H_m & -H_m \end{pmatrix}. This recursive formula allows for the explicit of Hadamard matrices of any order $2^k for positive k, by repeated application starting from H_1 or H_2. To verify that H_{2m} is indeed a Hadamard matrix, compute its product with its : H_{2m} H_{2m}^T = \begin{pmatrix} H_m & H_m \\ H_m & -H_m \end{pmatrix} \begin{pmatrix} H_m^T & H_m^T \\ H_m^T & -H_m^T \end{pmatrix} = \begin{pmatrix} H_m H_m^T + H_m H_m^T & H_m H_m^T - H_m H_m^T \\ H_m H_m^T - H_m (-H_m^T) & H_m H_m^T + (-H_m) (-H_m^T) \end{pmatrix} = \begin{pmatrix} 2 H_m H_m^T & 0 \\ 0 & 2 H_m H_m^T \end{pmatrix}. Since H_m H_m^T = m I_m by the induction hypothesis, it follows that H_{2m} H_{2m}^T = 2m I_{2m}, confirming the Hadamard property. For illustration, applying the construction to H_2 yields the order-4 matrix H_4 = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{pmatrix}, and further doubling produces H_8, a $8 \times 8 with entries determined by the block structure, all of whose rows are orthogonal with norm \sqrt{8}. These matrices, often called Sylvester-Hadamard matrices, can also be expressed using the : H_{2^k} = H_2^{\otimes k}, where the preserves the Hadamard condition due to the multiplicative property of Kronecker products for orthogonal matrices.

Paley Construction

The Paley construction provides a method to generate Hadamard matrices of q + 1, where q is a congruent to 3 4, utilizing the structure of the \mathbb{F}_q and its residues. In this setup, let \chi: \mathbb{F}_q \to \{ -1, 0, 1 \} denote the character ( extended to \mathbb{F}_q), defined such that \chi(a) = 1 if a is a nonzero , \chi(a) = -1 if a is a quadratic nonresidue, and \chi(0) = 0. The elements of \mathbb{F}_q are identified with the indices $0, 1, \dots, q-1. The core of the construction is the q \times q Jacobian matrix J (also called the Paley matrix), with entries J_{i,j} = \chi(j - i) for i, j \in \{0, 1, \dots, q-1\}. The full Hadamard matrix H of order q+1 is then formed by bordering J with an all-ones row and column, adjusted for the diagonal: specifically, H = \begin{pmatrix} 1 & \mathbf{1}^T \\ \mathbf{1} & J - I \end{pmatrix}, where \mathbf{1} is the all-ones column vector of length q, and I is the q \times q identity matrix. This ensures all entries are \pm 1, with the first row and column consisting of all 1's, the off-diagonal entries of the core block given by \chi(j - i), and the diagonal of the core block being -1. Equivalently, some presentations normalize the diagonal to 1 and adjust signs elsewhere, but the orthogonality holds up to equivalence. For a small example, consider q = 3 (where 3 ≡ 3 mod 4), so \mathbb{F}_3 = \{0, 1, 2\} with quadratic residues 0 and 1 (\chi(0) = 0, \chi(1) = 1, \chi(2) = -1). The Jacobian matrix J is J = \begin{pmatrix} 0 & \chi(1-0) & \chi(2-0) \\ \chi(0-1) & 0 & \chi(2-1) \\ \chi(0-2) & \chi(1-2) & 0 \end{pmatrix} = \begin{pmatrix} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0 \end{pmatrix}. Then J - I yields the core \begin{pmatrix} -1 & 1 & -1 \\ -1 & -1 & 1 \\ 1 & -1 & -1 \end{pmatrix}, and bordering gives the order-4 Hadamard matrix H = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & -1 & -1 & 1 \\ 1 & 1 & -1 & -1 \end{pmatrix}, which satisfies H H^T = 4I. A larger example is q = 7 (7 ≡ 3 mod 4), with \mathbb{F}_7 = \{0, 1, 2, 3, 4, 5, 6\} and quadratic residues 1, 2, 4 (\chi(1)=\chi(2)=\chi(4)=1, \chi(3)=\chi(5)=\chi(6)=-1, \chi(0)=0). The resulting order-8 Hadamard matrix from this construction is skew-symmetric up to equivalence and can be explicitly computed, but its rows are orthogonal with inner products zero, confirming H H^T = 8I. This matrix is distinct from the Sylvester construction of order 8. The orthogonality of H follows from character sum properties in finite fields. For rows corresponding to distinct field elements a, b \in \mathbb{F}_q, the inner product involves sums like \sum_{k \in \mathbb{F}_q} \chi(k - a) \chi(k - b) = \sum_{k} \chi((k - a)(k - b)), which evaluates to -1 using the fact that \chi is multiplicative and the Jacobi sum J(\chi, \chi) = -1 when q \equiv 3 \pmod{4}. The all-ones row is orthogonal to others due to \sum_{k} \chi(k) = 0. These properties ensure the rows are pairwise orthogonal and normalized. Paley also extended the construction to cases where q \equiv 1 \pmod{4}. The Type I Paley yields a conference matrix C of order q+1, which is then augmented to form a Hadamard matrix of order $2(q+1) via the block form H = \begin{pmatrix} I + C & I - C \\ I - C & -(I + C) \end{pmatrix}, leveraging the Jacobsthal matrix structure where entries are derived from \chi(j - i) with diagonal 0. This produces the Type II Paley Hadamard matrix. For instance, with q=5 (5 ≡ 1 mod 4), this yields an order-12 Hadamard matrix. This construction was developed by Raymond Paley in his 1933 paper, marking a significant advance in producing Hadamard matrices for orders beyond powers of 2.

Existence

Hadamard Conjecture

The Hadamard conjecture, proposed by in 1893, asserts that a Hadamard matrix of order n exists for every positive integer n such that n = 1, n = 2, or n \equiv 0 \pmod{4}. This statement was motivated by Hadamard's study of maximal , where he proved that the absolute value of the of any n \times n with entries \pm 1 is at most n^{n/2}, with equality holding if and only if the matrix is a (possibly scaled) Hadamard matrix. Beyond determinants, the conjecture connects to combinatorial designs, such as balanced incomplete block designs derived from Hadamard matrices, and to , where these matrices yield optimal error-correcting codes achieving the Plotkin bound. A key partial result, also established by Hadamard, shows that the condition n = 1, 2, or n \equiv 0 \pmod{4} is necessary for the existence of a Hadamard matrix: for other orders, the rows cannot be pairwise due to the properties of inner products over \pm 1 entries. Specifically, Hadamard demonstrated that for n \equiv 2 \pmod{4} with n > 2, the sum of squared inner products would exceed n^2, violating . Proving the faces significant challenges, including the of exhaustive computational searches for large orders to the in the search space—there are $2^{n^2} possible \pm 1 matrices of order n. It also relates to other open problems, such as Ryser's 1963 that no circulant Hadamard matrix exists for n > 4, which, if true, would restrict certain structured constructions but not disprove the general case. As of November 2025, the conjecture remains unresolved with no counterexamples found, though it has been verified constructively for all multiples of 4 up to 664. Early computational efforts by Herbert Ryser in the 1960s explored equivalence classes and bounds on row correlations, establishing foundational algorithms that informed later searches, but the smallest unresolved order, 668, continues to elude confirmation despite advances in quantum-inspired methods.

Known Existence Results

Hadamard matrices of order 1 and 2 are the trivial cases, with the order-1 matrix being the single entry [+1] and the order-2 matrix given by the Sylvester construction \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}. These were recognized in early studies of orthogonal matrices by Sylvester in 1867 and Hadamard in 1893. For all powers of 2, Hadamard matrices exist via the recursive Sylvester construction, which doubles the order at each step: if H_n is a Hadamard matrix of order n, then H_{2n} = \begin{pmatrix} H_n & H_n \\ H_n & -H_n \end{pmatrix} is a Hadamard matrix of order $2n. This yields explicit constructions for orders 4, 8, 16, 32, 64, and arbitrarily large powers of 2. The Paley construction provides Hadamard matrices of order q+1, where q is a congruent to 3 4. For example, this gives matrices of orders 4 (q=3), 8 (q=7), 12 (q=11), 20 (q=19), 24 (q=23), 28 (q=27=3^3), 32 (q=31), 44 (q=43), 48 (q=47), 60 (q=59), 68 (q=67), 80 (q=79), 84 (q=83), and 104 (q=103). This method, introduced by Paley in , covers many prime power-related orders and has variants extending to quadratic residues in finite fields. For composite orders, the Kronecker product (or tensor product) construction allows combining existing Hadamard matrices: if H_m and H_n exist, then H_m \otimes H_n is a Hadamard matrix of order mn. This enables constructions for products of known orders, such as 24 = 12 × 2. Additionally, methods like Williamson's construction produce matrices of order 4t for odd t, using four symmetric circulant matrices of order t satisfying certain orthogonality conditions; this was developed in 1944 and applies to orders like 12 (t=3), 20 (t=5), and 28 (t=7). The Goethals-Seidel construction, from 1967, further extends this to orders 4t using arrays of order t with specific autocorrelation properties, covering additional cases like 36 and 52. As of November 2025, explicit constructions exist for Hadamard matrices of all possible orders—namely, 1, 2, and all multiples of 4 up to 664—through combinations of the above methods and computational searches. Recent advances include verifications and new constructions reported in 2023, filling previous gaps up to 664, such as order 660 via optimized Williamson-type arrays. The smallest unresolved order remains 668 (=4×167, with 167 a prime ≡3 mod 4, but not covered by standard Paley due to field issues in variants). Computational databases now provide explicit constructions for all known orders up to 1208, though gaps persist beyond 664, with open orders below 2000 including 668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, and 1964. No Hadamard matrices exist for orders ≡2 mod 4 (except 2) or odd orders greater than 1, as proven by Hadamard in 1893 via determinant bounds. For small orders up to 100, all feasible cases are covered, as summarized in the following table:
OrderExample Construction
1Trivial [+1]
2
4 or Paley (q=3)
8 or Paley (q=7)
12Williamson (t=3) or Paley (q=11)
16
20Williamson (t=5) or Paley (q=19)
24Paley (q=23) or (12×2)
28Williamson (t=7) or Paley (q=27)
32 or Paley (q=31)
36Goethals-Seidel (t=9)
40 (e.g., 2×20)
44Paley (q=43)
48Paley (q=47) or Williamson
52Goethals-Seidel (t=13)
56Product or Williamson
60Paley (q=59)
64
68Paley (q=67)
72 (e.g., 2×36)
76Williamson variants
80Paley (q=79)
84Williamson (t=21)
88Goethals-Seidel
92Williamson
96Product
100Goethals-Seidel or product
Progress on larger orders relies on computational verification and hybrid methods, with the 2024 SageMath database confirming all constructions up to the known frontier and highlighting persistent challenges for orders like 4p where p is a large prime ≡3 mod 4 not amenable to direct Paley extensions without additional multipliers.

Classification

Equivalence Relations

Two Hadamard matrices of the same order are said to be equivalent if one can be obtained from the other by permuting the rows, permuting the columns, multiplying one or more rows by −1, or multiplying one or more columns by −1. This relation partitions the set of all Hadamard matrices into , which is crucial for and efforts, as matrices within the same class share the same combinatorial properties. A common way to represent a unique representative from each is through a normalized form. In this form, the first row and first column consist entirely of +1 entries, achieved by appropriate sign changes on rows and columns. Additionally, the remaining rows (from the second onward) can be permuted to achieve based on their entries, providing a ordering within the class. Weaker equivalence relations are also studied to analyze specific symmetries. D-equivalence refers to the relation obtained solely by multiplying rows and columns by −1, without permutations. T-equivalence extends the standard equivalence by including of the , allowing for comparisons between a and its . These relations help in understanding subsets of symmetries, such as those preserving certain structural features like core orders in decompositions. The standard equivalence relation arises from the action of a group generated by row and column permutations together with row and column sign changes. This group, often called the equivalence group or the group of signed permutations acting on rows and columns separately, has order $2^{2n} (n!)^2, where the $2^n n! accounts for the signed permutations on rows (or similarly for columns). The size of each is then this group order divided by the order of the of the specific matrix. For small orders, the equivalence classes are simple. There is exactly one equivalence class for order 1 (the trivial matrix ) and order 2 (the matrix \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}). For order 4, all Hadamard matrices fall into a single equivalence class, represented by the Sylvester construction matrix.

Uniqueness and Enumeration

The enumeration of Hadamard matrices up to equivalence reveals a rapid growth in the number of distinct classes as the order n increases, with exact counts available only for small orders due to computational challenges. For n=1 and n=2, there is exactly one equivalence class each. Similarly, there is a unique Hadamard matrix up to equivalence for n=4 (the Sylvester matrix), n=8, and n=12. For n=16, there are 5 equivalence classes, 3 for n=20, 60 for n=24, and 487 for n=28. Uniqueness holds for all Hadamard matrices of orders n=4k \leq 12, with each having precisely one . Computational enumerations have extended these results to higher orders, such as n=[32](/page/32), where exactly 13,710,027 equivalence classes exist. For n=[64](/page/64), full enumeration remains infeasible, but partial classifications have identified 1,691 equivalence classes among those invariant under the of order 126, corresponding to specific Hadamard 2-(63,31,15) designs. Asymptotic bounds on the number of classes reflect the underlying . The total number of Hadamard matrices of n (a multiple of 4) satisfies H(n) \leq 2^{(1 - c_H) n^2 / 2} for some absolute constant c_H > 0 and sufficiently large n, providing an upper bound on the classes since each class size is at most the order of the group, which is O(2^{2n} n^{2n}). Lower bounds indicate that the number of Hadamard matrices grows at least as $2^{\Omega(n \log n)}, implying a similar asymptotic for the number of classes after accounting for the . Recent computational advances post-2020 have focused on specialized enumerations. For instance, in , all Hadamard matrices of 60 with an of 29 were classified up to , yielding 266 distinct classes, while those of 64 with an of 31 comprise 414 classes. These results leverage group-theoretic constraints to tame the complexity, though full counts for orders beyond 32 remain elusive. For Paley orders, where matrices arise from residues prime powers, enumerations confirm up to in known cases, with no multiple classes reported in recent studies. Enumerating Hadamard matrices up to equivalence is computationally intensive for large n, as the search space encompasses $2^{n^2} possible \pm 1 matrices, reduced by symmetries but still requiring exploration of orbits under a group of size roughly $2^{2n} (n!)^2. This exponential growth in both the ambient space and the number of classes limits exhaustive methods to n \leq 32, with algorithms for n=100+ typically generating representatives via recursive constructions or optimization rather than complete counts.

Special Types

Skew-Hadamard Matrices

A skew-Hadamard matrix of order n is a Hadamard matrix H that can be expressed as H = S + I_n, where I_n is the n \times n and S is a satisfying S^T = -S, with all off-diagonal entries of S being \pm 1 and the diagonal entries zero. This form ensures that the first row and column of H consist entirely of +1s, allowing normalization where the first row is all +1s. Such matrices exist only for orders n \equiv 0 \pmod{4}, and it is conjectured that skew-Hadamard matrices exist for every such . A key property is that if H is skew-Hadamard, then C = H - I_n is a skew-symmetric matrix of n, satisfying C C^T = (n-1) I_n with zero diagonal and off-diagonal entries \pm 1. Conversely, a skew-symmetric matrix C of n \equiv 2 \pmod{4} yields a skew-Hadamard H = C + I_n. This connection links skew-Hadamard matrices to combinatorial structures like symmetric designs and projective planes. The Paley construction provides a seminal method for generating skew-Hadamard matrices of order q+1, where q is a congruent to 3 4; here, the core S is the skew-symmetric of the Paley on q vertices, defined using the symbol over the \mathbb{F}_q. This construction, introduced by Paley in 1933, relies on quadratic residue tournaments, where an edge from i to j (with i \neq j) is directed based on whether j - i is a q. Other constructions, such as the Seberry-Williamson array using "good matrices," extend existence to additional orders like 76, 132, 140, and 508. As of August 2025, a comprehensive database provides constructions of skew-Hadamard matrices for all known orders up to 1208, implemented in , excluding 41 gap orders below 1000 such as 356, 404, and 428; the skew-Hadamard conjecture remains open, with ongoing research filling gaps via computational and algebraic . Their ties to projective planes arise through the underlying sets in the Paley , which model lines and points in finite geometries. For illustration, a skew-Hadamard of order 4, obtained via the Paley (q=3), \begin{pmatrix} +1 & +1 & +1 & +1 \\ +1 & +1 & -1 & -1 \\ +1 & -1 & +1 & -1 \\ +1 & -1 & -1 & +1 \end{pmatrix}, where the core S has zeros on the diagonal and satisfies skew-symmetry.

Type I and Type II Matrices

Type I and Type II Hadamard matrices refer to specific variants of the Paley construction, distinguished by the properties of the underlying finite field. The Paley Type I construction applies when q is a prime power congruent to 3 modulo 4, producing a Hadamard matrix of order q+1 (which is a multiple of 4); this yields a skew-Hadamard matrix. The construction uses the quadratic residue symbol to define the off-diagonal entries of the Jacobian matrix Q, where Q_{i,j} = \chi(j - i) for i \neq j (\chi the Legendre symbol), and the full matrix is formed as the bordered matrix with I + Q in the core. In contrast, the Paley Type II construction is for q \equiv 1 \pmod{4}, producing a Hadamard matrix of order $2(q+1). It involves doubling the Type I structure, often using two copies of the quadratic character matrix combined with conference matrix properties, resulting in a non-skew matrix. These constructions highlight the role of finite fields in generating large classes of Hadamard matrices and demonstrate modular arithmetic dependencies on q. Existence results from Paley constructions cover orders like 4, 8, 12, 20, 28 (Type I for q=3,7,11,19,27) and 12, 24, 40 (Type II for q=5,11,19), contributing to known Hadamard matrices up to large orders without counterexamples to the Hadamard conjecture in these classes. This framework aids in applications to weighing matrices and combinatorial designs, where Type I () variants enable specific orthogonal arrays with even properties, while Type II support broader block designs. For example, the Paley Type I Hadamard matrix of order 4 (q=3) is H_4 = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 \\ 1 & -1 & -1 & 1 \end{pmatrix}, a skew . A Paley Type II matrix of order 12 (q=5) can be constructed similarly, with row sums aligning to the normalized form (first row sum 12, others 0).

Circulant Hadamard Matrices

A circulant Hadamard matrix of order n is a square H with entries in \{ +1, -1 \} that satisfies H H^T = n I_n and is circulant, meaning each row is a right cyclic shift of the previous row. Such a matrix is fully determined by its first row (c_0, c_1, \dots, c_{n-1}), where c_i \in \{ +1, -1 \} and conventionally c_0 = 1. Circulant Hadamard matrices are known to exist only for orders n = 1 (the trivial $1 \times 1 {{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}}) and n = 4. For n = 4, there are exactly eight such matrices up to under sign changes and reversals, one explicit example being the matrix generated by the first row (1, 1, 1, -1): \begin{pmatrix} 1 & 1 & 1 & -1 \\ -1 & 1 & 1 & 1 \\ 1 & -1 & 1 & 1 \\ 1 & 1 & -1 & 1 \end{pmatrix}. This yields pairwise orthogonal rows, each with norm \sqrt{4}. In 1963, Herbert J. Ryser conjectured that no circulant Hadamard matrices exist for n > 4. Prior to its resolution, the conjecture was verified computationally for all possible orders up to n \leq 10^5 (where n = 4u^2 with u odd), with exhaustive searches ruling out candidates for small n such as 8, 12, 20, and 28. Additionally, asymptotic arguments based on the eigenvalues of circulant matrices—diagonalized by the discrete Fourier transform—demonstrate non-existence for sufficiently large n, as the eigenvalues \lambda_j = \sum_{k=0}^{n-1} c_k \omega^{jk} (with \omega = e^{2\pi i / n}) cannot all satisfy |\lambda_j| = \sqrt{n} for \pm 1-entries when n is large, due to concentration bounds on the sums. The conjecture was fully proved in 2023, showing that any purported circulant Hadamard matrix for n > 4 violates a family of modular congruence conditions derived from its structure. As of 2025, no counterexamples have emerged, consistent with the proof, though approximate circulant structures appear in theory, such as block-circulant complex Hadamard matrices used for isolating quantum states, but these are not exact real \pm 1-cases. The non-existence restricts the design of sequences with ideal periodic (non-zero only at shift zero), limiting applications in and communications where such sequences would enable perfect sidelobe suppression beyond length 4.

Generalizations

Complex Hadamard Matrices

A Hadamard matrix of order n is an n \times n H = (h_{ij}) with entries satisfying |h_{ij}| = 1 for all i, j and H H^* = n I_n, where H^* denotes the and I_n is the n \times n . This condition implies that the rows (and similarly the columns) of H are pairwise orthogonal with equal norm \sqrt{n}, making H / \sqrt{n} a . The real Hadamard matrices, with entries \pm 1, form a special subclass of Hadamard matrices. Key properties include the fact that the of the achieves the maximum possible for matrices with unit-modulus entries: |\det H| = n^{n/2}. This follows directly from \det(H H^*) = |\det H|^2 = \det(n I_n) = n^n. Any Hadamard matrix can be decomposed via equivalence relations involving diagonal phase matrices (unitary diagonal matrices) and permutations, reducing it to a dephased form where the first row and first column consist entirely of 1s; this dephased matrix effectively incorporates a real Hadamard modulated by off-diagonal s. Standard constructions include the Fourier matrix F_n, defined by [F_n]_{j,k} = \exp(2 \pi i j k / n) for j,k = 0, \dots, n-1, which satisfies the Hadamard condition for every positive integer n. Product constructions yield further examples: the H \otimes K of Hadamard matrices H ( m) and K ( l) is a Hadamard matrix of ml, since (H \otimes K)(H \otimes K)^* = (H H^*) \otimes (K K^*) = (m I_m) \otimes (l I_l) = ml I_{ml}. Additional product forms, such as generalizations of Sylvester's duplication, also generate families from smaller matrices. Complex Hadamard matrices exist for all orders n \geq 1, guaranteed by the construction. Equivalence classes under the action of and diagonal phase matrices are central to their study, with geometric approaches analyzing the orbits in the space of such matrices. Tadej and Życzkowski provided a comprehensive of inequivalent complex Hadamard matrices for dimensions n \leq 5, along with partial results for n=6 involving continuous families like the family F_6^{(2)}, the Dita family D_6^{(1)}, and others. Their 2006 catalogue extended to n \leq 16, highlighting isolated matrices and parametric families. Subsequent work has extended the catalogue, with ongoing classifications for higher dimensions available in dedicated resources.

Other Variants

Weighing matrices are square matrices with entries in \{0, \pm 1\} satisfying H H^T = w I_n for some positive integer w, where n is the order of the matrix. These generalize classical Hadamard matrices by permitting zero entries, with Hadamard matrices corresponding to the case w = n. Butson Hadamard matrices of type \mathrm{BH}(n, q) are n \times n matrices whose entries are q-th roots of unity and satisfy H H^* = n I_n. Unlike real \pm 1 Hadamard matrices, which are conjectured to exist only for orders n = 1, 2 or multiples of 4, Butson matrices \mathrm{BH}(n, n) exist for every positive integer n, as exemplified by the matrix whose entries are e^{2\pi i j k / n}. Recent variants include approximate Hadamard matrices, which are n \times n \pm 1 matrices A satisfying c \sqrt{n} \|x\|_2 \leq \|A x\|_2 \leq C \sqrt{n} \|x\|_2 for all x \in \mathbb{R}^n and constants $0 < c < C < \infty. Such matrices exist for all n \geq 1, achieved via signed conference matrices; these find use in for near-orthogonal transformations in and initialization. Non-square generalizations encompass rectangular Hadamard arrays, or partial Hadamard matrices, which are m \times n matrices with \pm 1 entries whose rows (or columns) are pairwise orthogonal, satisfying H H^T = d I_m for some d \leq n. These extend the square case and arise in for incomplete designs, with existence tied to the parameters m and n via bounds like m \leq n.

Applications

Combinatorial and

Hadamard matrices play a significant role in theory, particularly in the construction of symmetric balanced incomplete block designs (BIBDs) known as Hadamard designs. Given a Hadamard matrix H of order n = 4t, the rows of H (excluding the all-ones row) can be used to define the blocks of a symmetric BIBD on v = n-1 points, where each block has size k = (n-1)/2 and every pair of distinct points appears in exactly \lambda = (n-4)/4 blocks. This design arises by identifying points with the columns excluding the all-ones column and defining incidence via entries of +1 in the matrix. The of such designs is equivalent to that of the corresponding Hadamard matrix, providing a direct link between the matrix's and the design's balance properties. In , Hadamard matrices give rise to , which are linear binary codes with strong distance properties suitable for error correction. For a Sylvester-constructed Hadamard matrix of order n = 2^m, the has length n, dimension approximately \log_2 n (specifically m), and minimum distance n/2. These codes are special cases of Reed-Muller codes and achieve the Plotkin bound, making them optimal for certain parameter regimes. A closely related construction yields the simplex code, obtained by puncturing the to length n-1 = 2^m - 1, with dimension m and distance $2^{m-1}; this simplex code is the dual of the of the same length. The rows of the Hadamard matrix, mapped from \pm 1 to $0/1, generate these codes, leveraging the matrix's to ensure codewords. Hadamard matrices also facilitate the construction of weighing matrices, which are essential for experimental designs in , such as optimal weighing procedures to identify objects. A Hadamard matrix of order n is itself a weighing matrix of weight n, satisfying WW^T = n I_n with entries in \{0, \pm 1\} but no zeros. More generally, submatrices formed by selecting subsets of rows and columns from a larger Hadamard matrix yield weighing matrices of smaller order and weight, enabling efficient designs for multi-stage experiments where the goal is to minimize the number of weighings while maximizing information gain. These submatrices preserve key orthogonality properties, making them ideal for balanced incomplete block designs in experiments. Historically, Hadamard matrices have contributed to resolutions of the Kirkman schoolgirl problem, which seeks a resolvable Steiner triple system STS(15)—a decomposition of the K_{15} into triple systems with parallel classes. Constructions based on the AG(4,2), whose point-hyperplane derives from the Hadamard matrix of order 16, provide explicit resolutions by removing a point to obtain the 15-point design with seven parallel classes of five triples each. This geometric approach, rooted in the matrix's properties, confirms the existence of solutions and highlights connections between Hadamard matrices and resolvable designs.

Signal Processing and Quantum Computing

In signal processing, the Hadamard transform, particularly its fast Walsh-Hadamard variant, serves as an efficient for decomposing signals into sequency-ordered basis functions, analogous to the but using square waves instead of sinusoids. This transform is computed in O(n \log n) time for inputs of length n = 2^m, enabling applications in filtering, , and where computational efficiency is paramount. Hadamard-based transforms have been employed in image compression to achieve lossy encoding by concentrating energy in low-sequency coefficients, similar to the in . For instance, variants like replace the DCT with a for core processing, offering improved performance in certain low-bit-depth scenarios due to its simpler arithmetic operations limited to additions and subtractions. Historical applications include NASA's use of Hadamard compression for interplanetary imagery in the and , demonstrating its robustness for bandwidth-constrained transmission. In , the Hadamard gate is a fundamental single-qubit operation that creates superpositions from computational basis states, defined by the H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, which rotates the by \pi around the axis (X + Z)/\sqrt{2}. This gate underpins algorithms requiring balanced superpositions, such as random walks and phase estimation. The Hadamard gate forms a core component of the (QFT) circuit, where a sequence of Hadamard gates on n qubits generates the uniform superposition necessary for the transform's first stage, followed by controlled phase rotations; this structure enables the QFT to run in O(n^2) gates, providing quadratic speedup over classical FFT for period-finding tasks like . Complex Hadamard matrices generate (MUBs) essential for and secure key distribution, where bases \{ | \psi_j \rangle \} and \{ | \phi_k \rangle \} satisfy | \langle \psi_j | \phi_k \rangle |^2 = 1/d for dimension d; for example, in dimension 6, constructions using complex Hadamard matrices of order 6 yield up to three MUBs, aiding proofs of non-locality in multipartite systems. Recent advances include a qubit-efficient quantum approximate optimization (QAOA) for searching Hadamard matrices, which encodes the constraints into a low-depth circuit on gate-based hardware, outperforming classical methods for orders up to 32 by leveraging Grover-like amplification. Vector space constructions using generalized Hadamard matrices over finite fields provide new proofs of the Kochen-Specker () theorem, demonstrating contextuality in ; specifically, shifts of a seed Hadamard basis in \mathbb{Z}_p^d yield KS sets with fewer vectors than prior constructions, tightening bounds on non-contextual hidden variables for dimensions like p=5. Hadamard matrices underpin quantum error-correcting codes by defining groups for subspaces immune to single- errors; for instance, CSS codes derived from Hadamard matrices of order $2^m achieve rates approaching the quantum Gilbert-Varshamov bound, correcting up to (n-k)/2 errors in n- encodings. Hadamard transformations have been explored in artificial neural networks to enhance efficiency in models.