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 kth 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.

Related Blog Posts

This article is part of the “What Is” series, available from https://nhigham.com/category/what-is and in PDF form from the GitHub repository https://github.com/higham/what-is.

This entry was posted in what-is. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s