A Hadamard matrix is an matrix with elements
and mutually orthogonal columns. For example,
is a Hadamard matrix.
A necessary condition for an Hadamard matrix to exist with
is that
is divisible by
, but it is not known if a Hadamard matrix exists for every such
.
A Hadamard matrix of order 428 was found for the first time in 2005. The smallest multiple of for which a Hadamard matrix has not been found is 668.
A Hadamard matrix satisfies , so
. It also follows that
. Hadamard’s inequality states that for an
real matrix
,
, where
is the
th column of
. 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 is a Hadamard matrix then so is
So starting with a Hadamard matrix of size , one can build up matrices of size
for
. 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:
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 , for any form of pivoting. Evidence suggests that the growth factor for complete pivoting is exactly
, but this has not been proved. It has been proved that any
Hadamard matrix has growth factor
for complete pivoting for
and
.
An interesting property of Hadamard matrices is that the -norm (the matrix norm subordinate to the vector
-norm) is known explicitly for all
:
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
is
, Numer. Linear Algebra Appl. 16, 715–743, 2009.
- H. Kharaghani and B. Tayfeh-Rezaie, A Hadamard Matrix of Order
, J. Combin. Des. 56, 435–440, 2005.
- A Library of Hadamard Matrices, N. J. A. Sloane.
Related Blog Posts
- Hadamard Matrices by Cleve Moler (2019)
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.