A Hadamard matrix of order n is a square matrix H whose entries are all +1 or −1 and which satisfies the equation HHT = nIn, where HT is the transpose of H and In is the identity matrix of order n. That equation is equivalent to saying that any two distinct rows of H are orthogonal: laid side by side, two rows agree in exactly half of the n positions and disagree in the other half. Matrices of this kind were studied by Sylvester in 1867 under the name anallagmatic pavements, twenty-six years before Hadamard considered them in the determinant work that gave them their modern name.
The defining identity is symmetric in rows and columns: HHT = nIn holds if and only if HTH = nIn, so the columns of a Hadamard matrix are mutually orthogonal whenever the rows are. Two elementary operations preserve the Hadamard property: permuting rows or columns, and multiplying every entry of a single row or column by −1. Matrices related by sequences of such operations are regarded as equivalent, and a matrix whose first row and first column consist entirely of +1 entries is called normalized; every Hadamard matrix can be brought to normalized form by sign changes.
A third property supplies the simplest way of building large examples from small ones: the tensor (Kronecker) product of Hadamard matrices of orders m and n is a Hadamard matrix of order mn, obtained by replacing each entry a of one matrix by the block aB, where B is the other matrix.
Hadamard's interest in these matrices arose from an inequality he proved in 1893 bounding the determinant of a matrix with complex entries. If every entry of an n × n matrix has modulus at most M, the determinant is at most Mnnn/2 in absolute value. For entries drawn from {+1, −1} the bound is nn/2, and it is attained exactly by the Hadamard matrices, which are therefore the extremal solutions of Hadamard's maximum determinant problem. Because Hadamard matrices do not exist in most orders, the companion question of the true maximum determinant of an n × n matrix with entries ±1 remains an active research topic, with upper bounds derived largely from Gram matrices and lower bounds from constructions using quadratic residues and design theory.
The orthogonality conditions are restrictive: the order of a Hadamard matrix must be 1, 2, or a multiple of 4, a necessary condition already noted by Hadamard in 1893. Whether this condition is also sufficient is the Hadamard conjecture, which asserts that a Hadamard matrix exists for every order divisible by 4. It is a well-known open problem in combinatorics, though matrices have been produced for an ever-larger set of orders. The order 268 was settled by Sawade in 1985 and 428 by Kharaghani and Tayfeh-Rezaie in 2004; that construction left 668 as the smallest order divisible by 4 for which no Hadamard matrix is known. Computer algebra systems now assemble matrices for all known orders up to 1200 and beyond by combining the various construction families.
Complete classification up to equivalence is available only in small orders: there is a single matrix in each of the orders 4, 8 and 12, five inequivalent matrices of order 16, three of order 20, sixty of order 24, and 487 of order 28.
Sylvester construction. Tensoring a Hadamard matrix of order n with the order-2 matrix yields one of order 2n. Iterating from the 1 × 1 matrix produces Hadamard matrices in every order that is a power of 2. The more general substitution of one matrix into another, described above, gives order mn from orders m and n.
Paley construction. This method uses the arithmetic of a finite field GF(q) with q an odd prime power, assigning signs according to which field elements are quadratic residues. It comes in two forms: when q ≡ 3 (mod 4) it produces a Hadamard matrix of order q + 1 (Paley type I), and when q ≡ 1 (mod 4) it produces one of order 2(q + 1) (Paley type II). Combined with doubling, Paley's theorem guarantees a Hadamard matrix in every order divisible by 4 of the form 2e(pm + 1) with p an odd prime. Many orders escape this net — 92 is the smallest multiple of 4 with no Paley construction — and are handled instead by Williamson-type and Turyn-type constructions, skew Hadamard matrices, or searches based on difference sets and conference matrices.
Hadamard matrices are interchangeable with certain combinatorial designs: a Hadamard matrix of order 4t is equivalent to a symmetric (4t − 1, 2t − 1, t − 1) block design, sometimes called a Hadamard design or Hadamard 2-design. This correspondence makes them a standard ingredient in design theory and in statistical experimental design.
In coding theory, reading the rows of a Hadamard matrix of order 2m as binary words yields the Hadamard code (also known as the Walsh or Walsh–Hadamard code), a binary code with parameters [2m, m, 2m−1]. Its augmented version, with parameters [2m, m + 1, 2m−1], is precisely the first-order Reed–Muller code RM(1, m), while the shortened version [2m − 1, m, 2m−1] is the simplex code. The minimum distance is half the block length, so the code tolerates a high error rate at the cost of a very low information rate. A complete set of Walsh functions of order n likewise forms a Hadamard matrix, linking the subject to the Walsh–Hadamard transform used in signal processing. Hadamard matrices also generate combinatorial objects such as Hadamard graphs, and admit a generalization whose entries are p-th roots of unity and whose defining equation uses the conjugate transpose.