Hadamard matrix

A square matrix $ H = \| h _ {ij} \| $ of order $ n $, with entries $ + 1 $ or $ - 1 $, such that the equation

$$ \tag{* } HH ^ {T} = n I _ {n} $$

holds, where $ H ^ {T} $ is the transposed matrix of $ H $ and $ I _ {n} $ is the unit matrix of order $ n $. Equality (*) is equivalent to saying that any two rows of $ H $ are orthogonal. Hadamard matrices have been named after J. Hadamard who showed [1] that the determinant $ | A | $ of a matrix $ A = \| a _ {ij} \| $ of order $ n $, with complex entries, satisfies the Hadamard inequality

$$ | A | ^ {2} \leq \prod _ { i= 1} ^ { n } s _ {ii} , $$

where

$$ s _ {ik} = \sum _ {j = 1 } ^ { n } a _ {ij} \overline{ {a _ {kj} }}\; , $$

and $ \overline{ {a _ {kj} }}\; $ is the element conjugate to $ a _ {kj} $( cf. Hadamard theorem on determinants). In particular, if $ | a _ {ij} | \leq M $, then $ | A | \leq M ^ {n} n ^ {n/2} $. It follows that a Hadamard matrix is a square matrix consisting of $ \pm 1 $' s with maximal absolute value $ n ^ {n/2} $ of the determinant. The properties of Hadamard matrices are: 1) $ HH ^ {T} = nI _ {n} $ implies $ H ^ {T} H = nI _ {n} $ and vice versa; 2) transposition of rows or columns and multiplication of the elements of an arbitrary row or column by $ - 1 $ again yields a Hadamard matrix; 3) the tensor product of two Hadamard matrices is also a Hadamard matrix, of order equal to the product of the orders of the factors. In other words, if $ A = \| a _ {ij} \| $ and $ B = \| b _ {ij} \| $ are Hadamard matrices of orders $ m $ and $ n $ respectively, then $ C = \| a _ {ij} B \| $ is a Hadamard matrix of order $ mn $. A Hadamard matrix with its first row and first column consisting only of $ + 1 $ terms is said to be normalized. The order of a Hadamard matrix is $ n = 1, 2 $ or $ n \equiv 0 $( $ \mathop{\rm mod} 4 $). The normalized Hadamard matrices of orders 1 and 2 are:

$$ [ 1],\ \ \left [ \begin{array}{cr} 1 & 1 \\ 1 &- 1 \\ \end{array} \right ] . $$

The existence of a Hadamard matrix has been demonstrated for several classes of values of $ n $( see, for example, [2], [3]). At the time of writing (the 1980s), it has not yet been proved that a Hadamard matrix exists for any $ n \equiv 0 $( $ \mathop{\rm mod} 4 $). For methods of constructing Hadamard matrices see [2]. Hadamard matrices are used in the construction of certain types of block designs [2] and codes [3] (cf. Block design; Code). A Hadamard matrix of order $ n = 4t $ is equivalent to a $ ( 4t - 1, 2t - 1, t - 1 ) $- design.

A generalized Hadamard matrix is a square matrix $ H ( p, h) $ of order $ h $, with as entries $ p $- th roots of unity, which satisfies the equality

$$ HH ^ {cT} = h I _ {h} , $$

where $ H ^ {cT} $ is the conjugate transpose of the matrix $ H $ and $ I _ {h} $ is the unit matrix of order $ h $. Generalized Hadamard matrices have properties analogous to 1) and 3) (cf. [4]).

References

[1]	J. Hadamard, "Résolution d'une question relative aux déterminants" Bull. Sci. Math. (2) , 17 (1893) pp. 240–246
[2]	M. Hall, "Combinatorial theory" , Blaisdell (1967) pp. Chapt. 14
[3]	W.W. Peterson, "Error-correcting codes" , M.I.T. & Wiley (1961)
[4]	A.T. Butson, "Generalized Hadamard matrices" Proc. Amer. Math. Soc. , 13 (1962) pp. 894–898

Comments

Hadamard matrices are equivalent to so-called Hadamard $ 2 $- designs; they are also important in statistical applications [a6].

References

[a1]	W.D. Wallis, A.P. Street, J.S. Wallis, "Combinatorics: room squares, sum-free sets, Hadamard matrices" , Springer (1972)
[a2]	D.R. Hughes, F.C. Piper, "Design theory" , Cambridge Univ. Press (1988)
[a3]	F.J. MacWilliams, N.J.A. Sloane, "The theory of error-correcting codes" , I-II , North-Holland (1977)
[a4]	S.S. Agaian, "Hadamard matrices and their applications" , Lect. notes in math. , 1168 , Springer (1985)
[a5]	T. Beth, D. Jungnickel, H. Lenz, "Design theory" , Cambridge Univ. Press (1986)
[a6]	A. Hedayat, W.D. Wallis, "Hadamard matrices and their applications" Ann. Stat. , 6 (1978) pp. 1184–1238