One hundred years ago, in 1893, Jacques Hadamard [89] found square matrices of orders 12 and 20, with entries ±1, which had all their rows (and columns) orthogonal. These matrices, X = (x_ij), satisfied the equality of the following inequality

and had maximal determinant. Hadamard actually asked the question of matrices with entries on the unit disc but his name has become associated with the real matrices.

Hadamard was not the first to study these matrices for J.J. Sylvester in 1867 in his seminal paper “Thoughts on inverse orthogonal matrices, simultaneous sign-successions, and tesselated pavements in two or more colours, with application to Newton’s rule, ornamental tile work, and the theory of numbers” [180] had found such matrices for all orders which are powers of 2. Nevertheless, Hadamard showed matrices with elements ±1 and maximal determinant could exist for all orders 1, 2, and 4t and so the Hadamard conjecture “that there exists an Hadamard matrix, or square matrix with every element ±1 and all row (column) vectors orthogonal” came from here. This survey indicates the progress that has been made in the past 100 years (Figure I.1).

J. Hadamard produced his determinant inequality while studying mathematical physics: the equality of the inequality led to Hadamard matrices. A paper by U. Scarpis 1898 [150] was the next contribution to the Hadamard story anticipating the work of R. E. A. C. Paley. However, it was not until J. Williamson’s work in 1944 that the name “Hadamard” attached to Hadamard matrices.

Hadamard’s inequality applies to matrices from the unit circle and matrices with entries ±1, ±i, and pairwise orthogonal rows (and columns) are called complex Hadamard matrices (note the scalar product is for complex numbers). These matrices were first studied by R.J. Turyn [190]. We believe complex Hadamard matrices exist for every order n ≡ 0 (mod 2). The truth of this conjecture implies the truth of the Hadamard conjecture.

In the 1960s, the US Jet Propulsion Laboratories (JPL) was working toward building the Mariner and Voyager space probes to visit Mars and the other planets of the solar system. Those of us who saw early black and white pictures of the back of the moon remember that whole lines were missing. The first black and white television pictures from the first landing on the moon were extremely poor quality. How many of us remember that the most recent flyby of Neptune was from a space probe launched in the 1970s? We take the high quality color pictures of Jupiter, Saturn, Uranus, Neptune, and their moons for granted.

In brief, these high quality color pictures are taken by using three black and white pictures taken in turn through red, green, and blue filters. Each picture is then considered as a thousand by a thousand matrix of black and white pixels. Each picture is graded on a scale of, say, 1 to 16, according to its greyness. So white is 1 and black is 16. These grades are then used to choose a codeword in, say, an eight error correction code based on, say, the Hadamard matrix of order 32. The codeword is transmitted to Earth, error corrected, the three black and white pictures reconstructed and then a computer used to reconstruct the colored pictures.

Hadamard matrices were used for these codewords for two reasons, first, error correction codes based on Hadamard matrices have maximal error correction capability for a given length of codeword and, second, the Hadamard matrices of powers of 2 are analogous to the Walsh functions, thus all the computer processing can be accomplished using additions (which are very fast and easy to implement in computer hardware) rather than multiplications (which are far slower).

It was Baumert et al. [8] working with JPL who sparked the interest in Hadamard matrices in the past 50 years. They pioneered the use of computing in the construction of Hadamard matrices. The existence of an Hadamard matrix is an NPC problem (or a problem which has computational resources exponential in the input to find the answer but easy to check the answer once it has been given).

Sylvester’s original construction for Hadamard matrices is equivalent to finding Walsh functions [110] which are the discrete analog of Fourier Series.

Example: Let H be a Sylvester–Hadamard matrix of order 8 and sequency order.

The Walsh function generated by H is the following:

Figure I.2 gives the points of intersections of Walsh functions are identical with that of trigonometrical functions

By mapping w(i, t) = wal_n(i, t) into the interval ,, then by mapping axial symmetrically into ,, we get w(2i, t) which is an even function. By operating similarly we get w(2i – 1, t), an odd function.

Just as any curve can be written as an infinite Fourier series

the curve can be written in terms of Walsh functions

The hardest curve to model with Fourier series is the step function wal₂ (0, t) and errors lead to the Gibbs phenomenon. Similarly, the hardest curve to model with Walsh functions is the basic sin 2πt or cos 2πt curve. Still, we see that we can transform from one to another.

Many problems require Fourier transforms to be taken, but Fourier transforms require many multiplications which are slow and expensive to execute. On the other hand, the fast Walsh–Hadamard transform uses only additions and subtractions (addition of the complement) and so is extensively used to transform power sequence spectrum density, band compression of television signals or facsimile signals, or image processing.

Walsh functions are easy to extend to higher dimensions (and higher dimensional Hadamard matrices) to model surfaces in three and higher dimensions – Fourier series are more difficult to extend. Walsh–Hadamard transforms in higher dimensions are also effected using only additions (and subtractions).

Constructions for Hadamard matrices can be roughly classified into three types:

• multiplication theorems
• “plug-in” methods
• direct theorems

In 1976 Jennifer Seberry Wallis in her paper “On the existence of Hadamard matrices” [213] showed that “given any odd natural number q there exists a t ≈ 2 ln₂(q - 3) so that there is an Hadamard matrix of order 2^tq (and hence for all orders 2^sq, s ≥ t).” This is represented graphically in Figure I.3. In recent work many far reaching asymptotic theorems by Craigen, Kharaghani, Holzmann and Ghaderpour, de Launey, Flannery, and Horadam [32, 46, 48, 79] have substantially improved Seberry’s result.

In fact, as we show in our Appendix A, Hadamard matrices are known to exist, of order 2²q, for most q < 3000 (we have results up to 40,000 which are similar). In many other cases Hadamard matrices of order 2³q or 2⁴q exist. A quick look shows most of the very difficult cases are for q (prime) ≡ 3 (mod 4).

Hadamard’s original construction for Hadamard matrices is a “multiplication theorem” as it uses the fact that the Kronecker product of Hadamard matrices of orders 2^am and 2^bn is an Hadamard matrix of order 2^a+bmn. Our graph shows we would like to reduce this power of2. In his book, Hadamard Matrices and their Applications, Agaian [1] shows how to multiply these Hadamard matrices to get an Hadamard matrix of order 2^a+b–1mn (aresult which lowers the curve in our graph except for q, a prime). We will show how Craigen, Seberry, and Zhang [37] and de Launey [44] have further improved this result.

A paper by V. Scarpis [150] was the second addition to the story anticipating Paley’s 1933 “direct” construction [144] which gives Hadamard matrices of order П_i,j(p_i + 1).(2(q_j + 1)), p_i (prime power)≡3 (mod 4), q_j (prime power) ≡ 1 (mod 4). This is extremely productive of Hadamard matrices but we note again the proliferation of powers of 2 as more products are taken.

Many people do not realize that in the same issue of the Journal of Mathematics and Physics as Paley’s paper appears, J.A.Todd showed the equivalence of Hadamard matrices of order 4t and SBIBD(4t – 1, 2t–1, t – 1). This family of SBIBD, its complementary family SBIBD(4t – 1, 2t, t), and the family SBIBD(4s², 2s² ±s,s² ±s)are called Hadamard designs. The latter family satisfies the constraint v = 4(k – λ) for v = 4s², k = 2s^s ± s, and λ = s² ± s which appears in some constructions (e.g. Shrikhande [168]). Hadamard designs have the maximum number of one’s in their incidence matrices of all incidence matrices of SBIBD(v, k, λ) (see Tsuzuku [187]) (Figure I.4).

In 1944 J. Williamson [223], who coined the name Hadamard matrices, first constructed what have come to be called Williamson matrices, or with a small set of conditions, Williamson type matrices. These matrices are used to replace the variables of a formally orthogonal matrix. We say Williamson type matrices are “plugged in” to the second matrix. Other matrices which can be “plugged in” to arrays of variables are called suitable matrices. Generally the arrays into which suitable matrices are plugged are orthogonal designs which have formally orthogonal rows (and columns) but may have variations such as Goethals–Seidel arrays, Wallis–Whiteman arrays, Spence arrays, generalized quaternion arrays, Agaian families, Kharaghani’s methods, Balonin–Seberry array, regular s-sets of regular matrices which give new matrices.

This is an extremely prolific method of construction. We will discuss methods which give matrices to “plug in” and matrices to “plug into.”

As a general rule if we want to check if an Hadamard matrix of a specific order 4pq exists we would first check if there are Williamson type matrices of order p, q, pq, then we would check if there were an OD(4t; t, t, t, t) for t = q, p, pq. This failing, we would check the “direct” constructions. Finally we would use a “multiplication theorem.” When we talk of“strength” of a construction this reflects a personal preference.

Before we proceed to more detail we consider diagrammatically some of the linkages between conjectures that will arise in this survey: the conjecture implied is “that the necessary conditions are sufficient for the existence of (say) Hadamard matrices” (see Figure I.5). (A weighing matrix, W, has elements 0, ±1, is square and satisfies WW^T = kI.)

The hierarchy of conjectures for weighing matrices and ODs is more straightforward. Settling the OD conjecture in Table I.1 would settle the weighing matrix conjecture to its left.

	Matrices	OD’s
Strongest	Skew-weighing	OD(n; 1, k)
	Weighing W(n; k) n odd
	WeighingW(2n, k) n odd	OD(2n; a, b) n odd
	Weighing W(4n, k) n odd	OD(4n; a, b, c, d) n odd
Weakest	W(2sn, k), n odd, s ≥ 3	OD(2sn; u1 , u2 , ..., us ) n odd

Source: Seberry and Yamada [166, table 1.1, p. 437], Wiley.

The original survey [166] emphasized those constructions, selected by us, which we believe showed the most promise toward solving the Hadamard conjecture.

Many diagrams, pictures, photos related to Hadamard matrices can be found on the website http://mathscinet.ru/catalogue/ created by Nickolay Balonin with a little help from D. Đoković, L.A. Mironovskiy, J. Seberry, and M.B. Sergeev (Figure I.6).

On the other hand, several arrays are related to representation theory of groups and group rings. A Williamson Hadamard matrix consists of Kronecker products of regular representation matrices of quaternion numbers and circulantmatrices. A Williamson Hadamard matrixis developed to an Hadamard matrix of generalized quaternion type, which is a regular representation matrix of the element of the ring obtained from Z[G]where G is a semidirect product of a cyclic group by the generalized quaternion group. The Ito Hadamard matrix and the Williamson Hadamard matrix are recognized as Hadamard matrices of generalized quaternion type.

We extend a representation of the group ring Z[G] to an extended representation from M₄(Z[G]) to M_4n(Z)where n is the order of a group G. We obtain the Welch array of order t and the Ono–Sawade–Yamamoto array of order 9 from the ordered set BHW(G). The Welch array uses the extended representation when G is a cyclic group of order t. We give an example of t = 5. The Ono–Sawade–Yamamoto array of order 9 uses the extended representation of a direct product of two cyclic groups of order 3. The Ono–Sawade–Yamamoto array is a matrix of order 36 [166].

The signed group Hadamard matrix which Craigen introduced [30], produces an Hadamard matrix using monomial representation. Craigen obtained new results on the asymptotic existence of Hadamard matrices via signed group Hadamard matrices.

There are many notable pioneers for the number theory of this book. However, Carl Frederick Gauss, born 1777, and Carl Gustav Jacobi born 1804 are the most important for our work. Gauss is generally regarded as one of the greatest mathematicians of all time. He is referred to as princeps mathematicorem. In his PhD, when aged 21, he proved the fundamental theorem of algebra. Jacobi was the first to apply elliptic functions to number theory, for example proving Fermat’s two-square theorem and Lagrange’s four-square theorem, and similar results for six and eight squares. His other work in number theory continued the work of C. F. Gauss: new proofs of quadratic reciprocity and the introduction of the Jacobi symbol in 1837 (Figure I.7).

The direct construction of Hadamard matrices relates closely to number theory. Paley Hadamard matrix is a regular representation matrix of the element Σ_α∈F ψ(α)α ∈ Z[F] where F is a finite field and ψ is a quadratic character of F. Then Σ_α∈Fη(α)ψ(α) is a Gauss sum where η is a nontrivial additive character. The properties of a Paley core matrix are proved from the relations of Gausssums.

Cyclotomic classes are an important tool for the construction not only of Hadamard matrices, but the other topics of combinatorics, for example, difference sets and supplementary difference sets. Cyclotomic numbers are written by Jacobi sums and conversely Jacobi sums are written by cyclotomic numbers[13]. Storer’s book [179] is essential and has been a fundamental reference since first published. We will give the explicit cyclotomic numbers for e=2,4,8 also covering the case e = 8 and f even not in Storer’s book.

An infinite family of Williamson Hadamard matrices by Whiteman [221] is constructed based on relative Gauss sums that is a ratio of Gauss sums[247]. This leads to infinite families of Hadamard matrices of generalized quaternion type constructed from relative Gauss sums.

Paley type I core matrix develops a Paley Hadamard difference set. The Stanton–Sprott difference set, which is a Paley Hadamard difference set, and its extension the Gordon–Mills–Welch difference set are associated with a relative Gauss sums.

Though it is difficult to determine the explicit values of Gauss sums and Jacobisums, we can obtain the munder the particular conditions. Index 2 Gauss sums and normalized relative Gauss sums are evaluated under the conditions of a group generated by a prime number [71, 253]. The construction theories of skew Hadamard difference sets by using index 2 Gauss sums [71, 72] and normalized relative Gauss sums [138] are new and widely applicable.

Construction of Hadamard matrices have been studied mainly over finite fields. The underlying algebraic structure in the research of combinatorics extends from finite fields to Galois rings. We obtain Menon Hadamard difference sets (which are equivalent to regular Hadamard matrices) over the Galois rings [242]. It should be noted that these difference sets have an embedding system, that is, a difference set is embedded in the ideal part of a difference set over a Galois ring of a higher characteristic. It gives one of many potential new directions to the research of Hadamard matrices.

The topics of combinatorics, relative difference sets [152], partial difference sets [146, 147], projective sets [18, 225], extended building sets [146, 147], (q; x, y)-partitions, [229] and planar functions [53] are also useful strong tools for the construction of Hadamard matrices. We will show how to use these tools for the construction of Hadamard matrices in this book.