Introduction :
In the realm of real numbers, an Hadamard matrix is a square matrix whose elements are
all either 1 or +1 and whose rows are pairwise orthogonal.
Such matrices are named after the Frenchman
Jacques
Hadamard (18651963) who is
also remembered for his 1896 proof of the Prime Number Theorem
(simultaneous with, and independent from, the proof of
de la ValléePoussin ).
In 1893, Hadamard did write an important paper about those matrices,
but Hadamard matrices were actually first investigated in 1867,
under the quaint name of anallagmatic pavements,
by James Joseph
Sylvester
(18141897).
They may be represented graphically as square mosaics of
square tiles that are either light or dark...
Here are special Hadamard matrices,
known as Walsh matrices, whose orders are
powers of 2 (1, 2, 4, 8 and 16).
In this, the light color stands for +1.
The usual convention in normalized cases
where one whole row and one whole column
have a uniform color is indeed that this color stands for +1.
In a normalized Hadamard matrix,
there are ½ n(n+1) positive elements
and ½ n(n1) negative ones.
(The color code is relatively unimportant, since the opposite of an Hadamard matrix
is also Hadamard.)
The above also serves to illustrate an observation of Sylvester (1867)
that an Hadamard matrix of order 2n
may be obtained from a known Hadamard matrix H of order n,
simply by juxtaposing four copies of H and negating one of those:
More generally, an Hadamard matrix of order mn may be constructed from an
Hadamard matrix K of order m and
an Hadamard matrix H of order n by substituting in K all occurrences of
+1 by H and all occurences of 1 by H
(the above is the special case m = 2).
In other words, the
Kronecker product
of two Hadamard matrices is also an Hadamard matrix...
Abstract Algebraic Definition :
Hadamard matrices of order n may also be defined as square matrices of order n
whose elements have an absolute value of 1 (one) and which verify the relation:
M M* = n I_{n}
In this, M* is the transpose of a real matrix M or, more generally,
the transpose conjugate
of a complex one. Matrices with complex
elements of unit moduli which satisfy the above relation are called
complex Hadamard matrices.
Those were introduced in 1970 by R.J. Turyn,
as proper generalizations of the ordinary (real) Hadamard matrices.
Many property of ordinary Hadamard matrices may just as well be discussed
in the complex realm. For example:
A (complex) Hadamard matrix is trivially obtained from another by using one or
several of the following transformations.
 Multiply a row or a column by an element of unit modulus (like 1).
 Replace a row or a column by its (elementwise) conjugate.
 Permutate rows or permutate columns.
Matrices so obtained from each other are said to be
Hadamardequivalent.
A complex Hadamard matrix where all firstrow and firstcolumn elements
are equal to 1 is said to be dephased.
Any complex Hadamard matrix is equivalent to a dephased one
(HINT: Use the first type of the above transformations.)
It's not difficult to prove that all
complex Hadamard matrices of order 2 are
Hadamardequivalent to
the aforementioned Walsh matrix of order 2.
Similarly, there's essentially only one complex Hadamard matrix of order 3.
It involves a primitive cube root of 3,
denoted w :

1 
1 
1 

where
w
= w_{3}
= ½ (1 + i Ö3 )

1 
w 
w^{2} 
1 
w^{2} 
w 
That's an example of a socalled ButsonHadamard matrix,
namely a complex Hadamard matrix of order n whose elements are
nth roots of unity. Those were first discussed by A.T. Butson
in 1962
(before Turyn introduced more general complex Hadamard matrices in 1970).
For any order n, one example of a ButsonHadamard matrix
is given by the Vandermonde matrix
of all the nth roots of unity
(which is Hadamardequivalent
to their circulant matrix).
Another example is provided, for any
composite
order, by extending to complex Hadamard matrices what we've
already remarked about real ones, namely that the Kronecker product of
two (complex) Hadamard matrices is a (complex) Hadamard matrix.
In particular, if H is a complex Hadamard matrix of order m,
a complex Hadamard matrix of order 3m is obtained from the following pattern:

H 
H 
H 

where
w
= w_{3}
= ½ (1 + i Ö3 )

H 
w H 
w^{2} H 
H 
w^{2} H 
w H 
This can be applied repeatedly to obtain the following ternary equivalent of
the aforementioned
(binary) Walsh matrices, using a threecolor code:
For any odd prime p,
a complex Hadamard matrix whose elements are p^{th }
roots of unity must have an order which is a multiple of p.
Conversely, it is conjectured that such matrices exist for any order which is a multiple
of p.
The existence of ordinary (real) Hadamard matrices
(as discussed next) can be construed to
be the case p=2,
for which a slightly different rule holds...
Existence of (Real) Hadamard Matrices of Order n :
Back to ordinary Hadamard matrices (whose elements are either 1 or +1).
The empty matrix (of order 0) is vacuously
an Hadamard matrix.
The order of any Hadamard matrix
must be 1, 2, or a multiple of 4 (Hadamard, 1893).
Conversely,
the HadamardPaley conjecture (better known as the Hadamard Conjecture )
states that there are Hadamard matrices of all such orders...
In 1933, Raymond Paley used finite fields
to construct Hadamard matrices of all orders of the form q+1
(resp. 2q+2) where q is the power of
a prime congruent to 3 (resp. 1) modulo 4.
Paley's Theorem states that Hadamard matrices
can be constructed (using
Paley's construction
and the aforementioned construction of Sylvester)
for all positive orders divisible by 4 except
those in the following sequence (i.e.,
multiples of 4 not equal to a power of 2 multiplied
by q+1, for some power q of an odd prime):
92, 116, 156, 172, 184, 188, 232, 236, 260, 268, 292, 324, 356, 372, 376, 404, 412, 428,
436, 452, 472, 476, 508, 520, 532, 536, 584, 596, 604, 612, 652, 668,
712, 716, 732, 756, 764, 772, 808, 836, 852, 856, 872, 876, 892, 904, 932, 940, 944, 952,
956, 964, 980, 988, 996, 1004, 1012, 1016, 1028, 1036, 1068, 1072,
1076, 1100, 1108, 1132, 1148, 1168, 1180, 1192, 1196, 1208, 1212, 1220, 1244, 1268, 1276,
1300, 1316, 1336, 1340, 1364, 1372, 1380, 1388, 1396, 1412, 1432, 1436, 1444, 1464, 1476,
1492, 1508, 1528, 1556, 1564, 1588, 1604, 1612, 1616, 1636, 1652, 1672, 1676, 1692, 1704,
1712, 1732, 1740, 1744, 1752, 1772, 1780, 1796, 1804, 1808, 1820, 1828, 1836, 1844, 1852,
1864, 1888, 1892, 1900, 1904, 1912, 1916, 1928, 1940, 1948, 1960, 1964, 1972, 1976, 1992,
2008, 2024, 2032, 2036, 2052, 2056, 2060, 2072, 2076, 2092, 2108, 2116, 2136, 2148, 2152,
2156, 2164, 2172, 2200, 2212, 2216, 2228, 2264, 2276, 2284, 2292, 2296, 2300 ...
(A046116)
For many of those remaining orders,
Hadamard matrices have been discovered by other methods.
Here's a brief summary...
In 1962, Baumert, Golomb,
and Hall found an Hadamard matrix of order 92, using
the general approach
introduced in 1944, by John Williamson
(who so constructed an Hadamard matrix of order 172).
A Williamson matrix of order 4m is an Hadamard matrix obtained as follows from 4 matrices of
order m (with unit elements) A, B, C and D,
provided 4 matching relations are satisfied:

A 
B 
C 
D 


AA* + BB* + CC* + DD* = 4 m I_{m}
AB*  BA* = CD*  DC*
AC*  CA* = DB*  BD*
AD*  DA* = BC*  CB*

B 
A 
D 
C 
C 
D 
A 
B 
D 
C 
B 
A 
For example, we may build an Hadamard matrix of order 12 with 4 matrices of order 3,
by letting one of them be the matrix U whose 9 elements are equal to +1
(the square of U is 3U) while the 3 others are equal to U2I.
With A = U, the resulting Hadamard matrix of order 12
(which isn't normalized in the above sense)
is shown graphically below, next to the Hadamard matrices of order 24 and 48
obtained from it with the aforementioned Sylvester construct:
It turns out that all (real) Hadamard matrices of order 12 are
equivalent.
In particular, the above order12 Hadamard matrix is Hadamardequivalent to
the following Hadamard matrix, which is normalized (dephased) and symmetrical:
In 1985, K. Sawade found an Hadamard matrix of order 268.
In June 2004,
Hadi Kharaghani and
Behruz TayfehRezaie
built the
Hadamard
matrix of order 428 illustrated below
(1 pixel per matrix element).
If we denote by M the symmetrical of any M with respect to its
antidiagonal,
the above matrix
is based on 4 matrices A, B, C, D of order m = 107
put together in the following pattern, which gives an Hadamard matrix
of order 4m if and only if all the 10 conditions listed are met.
(Note that M N = N M .)

A 
B 
C 
D 


AA* + BB* + CC* + DD* = 4 m I_{m}
B B* = B B*
C C* = C C*
D D* = D D*

B 
A 
D 
C 
C 
D 
A 
B 
D 
C 
B 
A 
A B*  B A* = D C*  C D*
A C*  C A* = B D*  D B*
A D*  D A* = B C*  C B*

A B*  B A* = D C*  C D*
A C*  C A* = B D*  D B*
A D*  D A* = C B*  B C*

Since June 2004, the order
668 has been the smallest multiple of 4
for which no Hadamard matrix is yet known
(as of January 2007).
Hadamard Matrix :
Wikipedia

MathWorld
Usage note :
Both spellings "a Hadamard matrix" and "an Hadamard matrix" can be construed
as correct:
The former one applies to an anglicized pronounciation of "Hadamard"
("h" and "d" both pronounced) whereas the latter must be used with
the proper French pronounciation
(initial "h" and final "d" both silent).