Hadamard Matrix

A class of Square Matrix invented by Sylvester (1867) under the name of Anallagmatic Pavement. A Hadamard matrix is a Square Matrix containing only 1s and $-1$s such that when any two columns or rows are placed side by side, Half the adjacent cells are the same Sign and half the other (excepting from the count an $L$-shaped ``half-frame'' bordering the matrix on two sides which is composed entirely of 1s). When viewed as pavements, cells with 1s are colored black and those with $-1$s are colored white. Therefore, the $n\times n$ Hadamard matrix ${\hbox{\sf H}}_n$ must have $n(n-1)/2$ white squares ($-1$s) and $n(n+1)/2$ black squares (1s).

This is equivalent to the definition

$${\hbox{\sf H}}_n{{\hbox{\sf H}}_n}^{\rm T} = n{\hbox{\sf I}}_n,$$ (1)

where ${\hbox{\sf I}}_n$ is the $n\times n$ Identity Matrix. A Hadamard matrix of order $4n+4$ corresponds to a Hadamard Design ($4n+3$, $2n+1$, $n$).

Paley's Theorem guarantees that there always exists a Hadamard matrix ${\hbox{\sf H}}_n$ when $n$ is divisible by 4 and of the form $2^e(p^m+1)$, where $p$ is an Odd Prime. In such cases, the Matrices can be constructed using a Paley Construction. The Paley Class $k$ is undefined for the following values of $m<1000$: 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.

Sawade (1985) constructed ${\hbox{\sf H}}_{268}$. It is conjectured (and verified up to $n<428$) that ${\hbox{\sf H}}_n$ exists for all $n$ Divisible by 4 (van Lint and Wilson 1993). However, the proof of this Conjecture remains an important problem in Coding Theory. The number of Hadamard matrices of order $4n$ are 1, 1, 1, 5, 3, 60, 487, ... (Sloane's A007299).

If ${\hbox{\sf H}}_n$ and ${\hbox{\sf H}}_m$ are known, then ${\hbox{\sf H}}_{nm}$ can be obtained by replacing all 1s in ${\hbox{\sf H}}_m$ by ${\hbox{\sf H}}_n$ and all $-1$s by $-{\hbox{\sf H}}_n$. For $n\leq 100$, Hadamard matrices with $n=12$, 20, 28, 36, 44, 52, 60, 68, 76, 84, 92, and 100 cannot be built up from lower order Hadamard matrices.

$${\hbox{\sf H}}_2 = \left[\begin{array}{cc}1 & 1\\ -1 & 1\end{array}\right]$$ (2)

$${\hbox{\sf H}}_4 = \left[\begin{array}{cc}{\hbox{\sf H}}_2 & {\hbox{\sf H}}_2\\ -{\... ...right] & \left[{\matrix{1 & 1\\ -1 & 1\\ }}\right]\end{array}\right]\nonumber$$

$$= \left[\begin{array}{cccc}1 & 1 & 1 & 1\\ -1 & 1 & -1 & 1\\ -1 & -1 & 1 & 1\\ 1 & -1 & -1 & 1\end{array}\right].$$ (3)

${\hbox{\sf H}}_8$ can be similarly generated from ${\hbox{\sf H}}_4$. Hadamard matrices can also be expressed in terms of the Walsh Functions Cal and Sal

$$H_8=\left[{\matrix{\mathop{\rm Cal}\nolimits (0,t)\cr \matho... ...nolimits (1,t)\cr \mathop{\rm Sal}\nolimits (3,t)\cr}}\right].$$ (4)

Hadamard matrices can be used to make Error-Correcting Codes.

See also Hadamard Design, Paley Construction, Paley's Theorem, Walsh Function

References

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 107-109 and 274, 1987.

Beth, T.; Jungnickel, D.; and Lenz, H. Design Theory. New York: Cambridge University Press, 1986.

Colbourn, C. J. and Dinitz, J. H. (Eds.) ``Hadamard Matrices and Designs.'' Ch. 24 in CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, pp. 370-377, 1996.

Geramita, A. V. Orthogonal Designs: Quadratic Forms and Hadamard Matrices. New York: Marcel Dekker, 1979.

Golomb, S. W. and Baumert, L. D. ``The Search for Hadamard Matrices.'' Amer. Math. Monthly 70, 12-17, 1963.

Hall, M. Jr. Combinatorial Theory, 2nd ed. New York: Wiley, p. 207, 1986.

Hedayat, A. and Wallis, W. D. ``Hadamard Matrices and Their Applications.'' Ann. Stat. 6, 1184-1238, 1978.

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://www.mathsource.com/cgi-bin/MathSource/Applications/Mathematics/0205-760.

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 (Eds. J. H. Dinitz and D. R. Stinson). New York: Wiley, pp. 431-560, 1992.

Sloane, N. J. A. Sequence A007299/M3736 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

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.

van Lint, J. H. and Wilson, R. M. A Course in Combinatorics. New York: Cambridge University Press, 1993.