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
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.
(2)
(3)
(4)
(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. Monthly79, 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.
http://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. Monthly70, 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. http://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." http://library.wolfram.com/infocenter/MathSource/499/.Ogilvie,
G. A. "Solution to Problem 2511." Math. Questions and Solutions10,
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 Combinatorics1,
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. Math140, 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 Solutions10, 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. A16,
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.
s are colored white. Therefore, the 
Hadamard matrix 
must have 
white squares (
s) and 
black squares (1s).
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
is the 
identity matrix.
corresponds to a Hadamard
design (
,
, 
), and a Hadamard matrix 
gives a graph on 
vertices known as a Hadamard
graph
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.
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.svg)
![[H_2 H_2; -H_2 H_2]](/images/equations/HadamardMatrix/Inline36.svg)
![[[1 1; -1 1] [1 1; -1 1]; -[1 1; -1 1] [1 1; -1 1]]](/images/equations/HadamardMatrix/Inline39.svg)
![[1 1 1 1; -1 1 -1 1; -1 -1 1 1; 1 -1 -1 1].](/images/equations/HadamardMatrix/Inline42.svg)
can be similarly generated from 
.
, 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).
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.
Kitis, L. "Paley's Construction of Hadamard Matrices."