close
Image TOPICS
Image
Search

Hadamard Matrix

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
HadamardMatrices

A Hadamard matrix is a type of square (-1,1)-matrix invented by Sylvester (1867) under the name of anallagmatic pavement, 26 years before Hadamard (1893) considered them. In a Hadamard matrix, placing any two columns or rows side by side gives half the adjacent cells the same sign and half the other sign. When viewed as pavements, cells with 1s are colored black and those with -1s are colored white. Therefore, the n×n Hadamard matrix H_n must have n(n-1)/2 white squares (-1s) and n(n+1)/2 black squares (1s).

A Hadamard matrix of order n is a solution to Hadamard's maximum determinant problem, i.e., has the maximum possible determinant (in absolute value) of any n×n complex matrix with elements |a_(ij)|<=1 (Brenner and Cummings 1972), namely n^(n/2). An equivalent definition of the Hadamard matrices is given by

H_nH_n^(T)=nI_n,
(1)

where I_n is the n×n identity matrix.

A Hadamard matrix of order 4n+4 corresponds to a Hadamard design (4n+3, 2n+1, n), and a Hadamard matrix H_n gives a graph on 4n vertices known as a Hadamard graph

HadamardWalshArrays

A complete set of 2^n Walsh functions of order n gives a Hadamard matrix H_(2^n) (Thompson et al. 1986, p. 204; Wolfram 2002, p. 1073). Hadamard matrices can be used to make error-correcting codes, in particular, the Reed-Muller error-correcting code.

If H_n and H_m are known, then H_(nm) can be obtained by replacing all 1s in H_m by H_n and all -1s by -H_n. For n<=100, Hadamard matrices with n=12, 20, 28, 36, 44, 52, 60, 68, 76, 84, 92, and 100 cannot be built up from lower order Hadamard matrices.

H_2=[1 1; -1 1]
(2)
H_4=[H_2 H_2; -H_2 H_2]
(3)
Image=[[1 1; -1 1] [1 1; -1 1]; -[1 1; -1 1] [1 1; -1 1]]
(4)
Image=[1 1 1 1; -1 1 -1 1; -1 -1 1 1; 1 -1 -1 1].
(5)

H_8 can be similarly generated from H_4.

HadamardPaley

Hadamard (1893) remarked that a necessary condition for a Hadamard matrix to exist is that n=1, 2, or a positive multiple of 4 (Brenner and Cummings 1972). Paley's theorem guarantees that there always exists a Hadamard matrix H_n when n is divisible by 4 and of the form 2^e(p^m+1) for some positive integer m, nonnegative integer e, and p an odd prime. In such cases, the matrices can be constructed using a Paley construction, as illustrated above (Wolfram 2002, p. 1073). The number of Paley classes for n=4, 8, ... are 2, 3, 2, 3, 2, 3, 2, 4, 1, ... (OEIS A074070). The values of n for which there are no Paley classes (and hence cannot be constructed using a Paley construction) are 92, 116, 156, 172, 184, 188, 232, 236, 260, 268, ... (OEIS A046116).

Hadamard 428x428 matrix

It is conjectured that H_n exists for all n divisible by 4. Sawade (1985) constructed H_(268). As of 1993, Hadamard matrices were known for all n divisible by 4 up to n<428 (Brouwer et al. 1989, p. 20; van Lint and Wilson 1993). A H_(428) was subsequently constructed (Kharaghani and Tayfeh-Rezaie 2004), illustrated above, leaving the smallest unknown order as 668. However, the proof of the general conjecture remains an important problem in coding theory. The number of distinct Hadamard matrices of orders 4n for n=1, 2, ... are 1, 1, 1, 5, 3, 60, 487, ... (OEIS A007299; Wolfram 2002, p. 1073). Djoković (2009) corrected the list in Colbourn and Dinitz (2007) and found four previously unknown n<10^4 divisible by 4 for which it is possible to construct a Hadamard matrix: 764, 23068, 28324, 32996.

See also

Hadamard Design, Hadamard Graph, Hadamard's Maximum Determinant Problem, Integer Matrix, Paley Class, Paley Construction, Paley's Theorem, Walsh Function

Explore with Wolfram|Alpha

References

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 107-109 and 274, 1987.Barrau, J. A. "Die Zentrische Zerlegung der Regularen Polytope." Nieuw Arch. voor Wisk. 7, 250-270, 1906.Beth, T.; Jungnickel, D.; and Lenz, H. Design Theory. New York: Cambridge University Press, 1986.Brenner, J. and Cummings, L. "The Hadamard Maximum Determinant Problem." Amer. Math. Monthly 79, 626-630, 1972.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. "Hadamard Matrices." §1.8 in Distance Regular Graphs. New York: Springer-Verlag, pp. 19-20, 1989.Colbourn, C. J. and Dinitz, J. H. (Eds.). CRC Handbook of Combinatorial Designs, 2nd ed. Boca Raton, FL: CRC Press, pp. 278-279, 2007.Craigen, R. "Hadamard Matrices and Designs." Ch. 24 in CRC Handbook of Combinatorial Designs (Ed. C. J. Colbourn and J. H. Dinitz). Boca Raton, FL: CRC Press, pp. 370-377, 1996.Djoković, D. Z. "Hadamard Matrices of Small Order and Yang Conjecture." Dec. 27, 2009. https://arxiv.org/abs/0912.5091.Gardner, M. "Mathematical Games: On the Remarkable Császár Polyhedron and Its Applications in Problem Solving." Sci. Amer. 232, 102-107, May 1975.Geramita, A. V. and Seberry, J. Orthogonal Designs: Quadratic Forms and Hadamard Matrices. New York: Dekker, 1979.Golomb, S. W. and Baumert, L. D. "The Search for Hadamard Matrices." Amer. Math. Monthly 70, 12-17, 1963.Hadamard, J. "Résolution d'une question relative aux déterminants." Bull. Sci. Math. 17, 240-246, 1893.Hall, M. Combinatorial Theory, 2nd ed. New York: Wiley, 1998.Hedayat, A. and Wallis, W. D. "Hadamard Matrices and Their Applications." Ann. Stat. 6, 1184-1238, 1978.Kharaghani, H. and Tayfeh-Rezaie, B. "A Hadamard Matrix of Order 428." J. Combin. Des. 13, 435-440, 2005. https://doi.org/10.1002/jcd.20043.Kimura, H. "Classification of Hadamard Matrices of Order 28." Disc. Math. 133, 171-180, 1994.Kimura, H. "Classification of Hadamard Matrices of Order 28 with Hall Sets." Disc. Math. 128, 257-269, 1994.Image Kitis, L. "Paley's Construction of Hadamard Matrices." https://library.wolfram.com/infocenter/MathSource/499/.Ogilvie, G. A. "Solution to Problem 2511." Math. Questions and Solutions 10, 74-76, 1868.Paley, R. E. A. C. "On Orthogonal Matrices." J. Math. Phys. 12, 311-320, 1933.Ryser, H. J. Combinatorial Mathematics. Buffalo, NY: Math. Assoc. Amer., pp. 104-122, 1963.Sawade, K. "A Hadamard Matrix of Order-268." Graphs Combinatorics 1, 185-187, 1985.Seberry, J. and Yamada, M. "Hadamard Matrices, Sequences, and Block Designs." Ch. 11 in Contemporary Design Theory: A Collection of Surveys (Ed. J. H. Dinitz and D. R. Stinson). New York: Wiley, pp. 431-560, 1992.Sloane, N. J. A. Sequences A007299/M3736, A046116, and A074070 in "The On-Line Encyclopedia of Integer Sequences."Spence, E. "Classification of Hadamard Matrices of Order 24 and 28." Disc. Math 140, 185-243, 1995.Sylvester, J. J. "Thoughts on 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." Phil. Mag. 34, 461-475, 1867.Sylvester, J. J. "Problem 2511." Math. Questions and Solutions 10, 74, 1868.Thompson, A. R.; Moran, J. M.; and Swenson, G. W. Jr. Interferometry and Synthesis in Radio Astronomy. New York: Wiley, p. 204, 1986.Turyn, R. J. "Hadamard Matrices, Baumert-Hall Units, Four-Symbol Sequences, Pulse Compression, and Surface Wave Encodings." J. Combin. Th. Ser. A 16, 313-333, 1974.van Lint, J. H. and Wilson, R. M. A Course in Combinatorics. New York: Cambridge University Press, 1993.Wallis, W. D.; Street, A. P.; and Wallis, J. S. Combinatorics: Room Squares, Sum-free Sets, Hadamard Matrices. New York: Springer-Verlag, 1972.Williamson, J. "Hadamard's Determinant Theorem and the Sum of Four Squares." Duke. Math. J. 11, 65-81, 1944.Williamson, J. "Note on Hadamard's Determinant Theorem." Bull. Amer. Math. Soc. 53, 608-613, 1947.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1073, 2002.

Referenced on Wolfram|Alpha

Hadamard Matrix

Cite this as:

Weisstein, Eric W. "Hadamard Matrix." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HadamardMatrix.html

Subject classifications