What Is a Hadamard Matrix?

A Hadamard matrix is an $n\times n$ matrix with elements $\pm 1$ and mutually orthogonal columns. For example,

$\left[\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 \end{array}\right]$

is a Hadamard matrix.

A necessary condition for an $n\times n$ Hadamard matrix to exist with $n > 2$ is that $n$ is divisible by $4$ , but it is not known if a Hadamard matrix exists for every such $n$ .

A Hadamard matrix of order 428 was found for the first time in 2005. The smallest multiple of $4$ for which a Hadamard matrix has not been found is 668.

A Hadamard matrix satisfies $H^T H = nI$ , so $H^{-1} = n^{-1}H^T$ . It also follows that $\det(H) = \pm n^{n/2}$ . Hadamard’s inequality states that for an $n\times n$ real matrix $A$ , $|\det(A)| \le \prod_{k=1}^n \|a_k\|_2$ , where $a_k$ is the $k$ th column of $A$ . A Hadamard matrix achieves equality in this inequality (as does any matrix with orthogonal columns).

Hadamard matrices can be generated with a recursive (Kronecker product) construction: if $H$ is a Hadamard matrix then so is

$\left[\begin{array}{rr} H & H\\ H & -H \end{array}\right].$

So starting with a Hadamard matrix of size $m$ , one can build up matrices of size $2^km$ for $k = 1,2,\dots$ . The MATLAB hadamard function uses this technique. It includes the following Hadamard matrix of order 12, for which we simply display the signs of the elements:

$\left[\begin{array}{rrrrrrrrrrrr} {}+ & + & + & + & + & 1 & + & + & + & + & + & +\\ {}+ & - & + & - & + & + & + & - & - & - & + & -\\ {}+ & - & - & + & - & + & + & + & - & - & - & +\\ {}+ & + & - & - & + & - & + & + & + & - & - & -\\ {}+ & - & + & - & - & + & - & + & + & + & - & -\\ {}+ & - & - & + & - & - & + & - & + & + & + & -\\ {}+ & - & - & - & + & - & - & + & - & + & + & +\\ {}+ & + & - & - & - & + & - & - & + & - & + & +\\ {}+ & + & + & - & - & - & + & - & - & + & - & +\\ {}+ & + & + & + & - & - & - & + & - & - & + & -\\ {}+ & - & + & + & + & - & - & - & + & - & - & +\\ {}+ & + & - & + & + & + & - & - & - & + & - & - \end{array}\right].$

Hadamard matrices have applications in optimal design theory, coding theory, and graph theory.

In numerical analysis, Hadamard matrices are of interest because when LU factorization is performed on them they produce a growth factor of at least $n$ , for any form of pivoting. Evidence suggests that the growth factor for complete pivoting is exactly $n$ , but this has not been proved. It has been proved that any $n\times n$ Hadamard matrix has growth factor $n$ for complete pivoting for $n = 12$ and $n = 16$ .

An interesting property of Hadamard matrices is that the $p$ -norm (the matrix norm subordinate to the vector $p$ -norm) is known explicitly for all $p$ :

$\|H\|_p = \max\bigl( n^{1/p}, n^{1-1/p} \bigr), \quad 1\le p\le \infty.$

References

This is a minimal set of references, which contain further useful references within.

A. Hedayat and W. D. Wallis, Hadamard Matrices and Their Applications, Ann. Statist. 6, 1184–1238, 1978.
Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, second edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2002.
Christos D. Kravvaritis, Hadamard Matrices: Insights into Their Growth Factor and Determinant Computations, in M. Themistocles Rassias and Vijay Gupta, eds, Mathematical Analysis, Approximation Theory and Their Applications, Springer-Verlag, Berlin, 383–415, 2016.
Christos Kravvaritis and Marilena Mitrouli, The Growth Factor of a Hadamard Matrix of Order $16$ is $16$ , Numer. Linear Algebra Appl. 16, 715–743, 2009.
H. Kharaghani and B. Tayfeh-Rezaie, A Hadamard Matrix of Order $428$ , J. Combin. Des. 56, 435–440, 2005.
A Library of Hadamard Matrices, N. J. A. Sloane.