Hadamard Matrix
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 
s are colored
white. Therefore, the 
Hadamard matrix 
must have 
white squares (
s) and 
black squares
(1s).
A Hadamard matrix of order 
is a solution to
Hadamard's maximum determinant
problem, i.e., has the maximum possible determinant
(in absolute value) of any 
complex
matrix with elements 
(Brenner
and Cummings 1972), namely 
. An equivalent
definition of the Hadamard matrices is given by
 |
(1)
|
where 
is the 
identity
matrix.
A Hadamard matrix of order 
corresponds
to a Hadamard design (
, 
, 
), and a Hadamard
matrix 
gives a graph on 
vertices known
as a Hadamard graph
A complete set of 
Walsh
functions of order 
gives a Hadamard matrix 
(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 
and 
are known, then
can be obtained by replacing all 1s in 
by 
and all 
s by 
. For 
, Hadamard
matrices with 
, 20, 28, 36, 44, 52, 60, 68, 76,
84, 92, and 100 cannot be built up from lower order Hadamard matrices.
 |  | ![[1 1; -1 1]](/images/equations/HadamardMatrix/Inline33.gif) |
(2)
|
 |  | ![[H_2 H_2; -H_2 H_2]](/images/equations/HadamardMatrix/Inline36.gif) |
(3)
|
 |  | ![[[1 1; -1 1] [1 1; -1 1]; -[1 1; -1 1] [1 1; -1 1]]](/images/equations/HadamardMatrix/Inline39.gif) |
(4)
|
 |  | ![[1 1 1 1; -1 1 -1 1; -1 -1 1 1; 1 -1 -1 1].](/images/equations/HadamardMatrix/Inline42.gif) |
(5)
|
can be similarly generated from 
.
Hadamard (1893) remarked that a necessary condition for a Hadamard matrix to exist is that 
, 2, or a positive
multiple of 4 (Brenner and Cummings 1972). Paley's
theorem guarantees that there always exists a Hadamard matrix 
when 
is divisible by
4 and of the form 
for some
positive integer 
, nonnegative integer 
, and 
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 
, 8, ... are
2, 3, 2, 3, 2, 3, 2, 4, 1, ... (OEIS A074070).
The values of 
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).
It is conjectured that 
exists for all 
divisible
by 4. Sawade (1985) constructed 
. As of 1993,
Hadamard matrices were known for all 
divisible by 4
up to 
(Brouwer et al. 1989,
p. 20; van Lint and Wilson 1993). A 
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 
for 
, 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 
divisible by 4 for which it
is possible to construct a Hadamard matrix: 764, 23068, 28324, 32996.
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." Preprint, 2004. https://math.ipm.ac.ir/tayfeh-r/papersandpreprints/h428.pdf.
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.
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.
Weisstein, Eric W. "Hadamard Matrix." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HadamardMatrix.html
Contact the MathWorld Team
{{1, 1}, {-1, 1}}