In mathematics, Hadamard's inequality (also known as Hadamard's theorem on determinants[1]) is a result first published by Jacques Hadamard in 1893.[2] It is a bound on the determinant of a matrix whose entries are complex numbers in terms of the lengths of its column vectors. In geometrical terms, when restricted to real numbers, it bounds the volume in Euclidean space of n dimensions marked out by n vectors vi for 1 ≤ i ≤ n in terms of the lengths of these vectors ||vi ||.
Specifically, Hadamard's inequality states that if N is the matrix having columns[3] vi, then
\left|\det(N)\right|\le
| n | |
| \prod | |
| i=1 |
\|vi\|.
A corollary is that if the entries of an n by n matrix N are bounded by B, so |Nij | ≤ B for all i and j, then
\left|\det(N)\right|\leBnnn/2.
\left|\det(N)\right|\lenn/2.
More generally, suppose that N is a complex matrix of order n, whose entries are bounded by |Nij | ≤ 1, for each i, j between 1 and n. Then Hadamard's inequality states that
|\operatorname{det}(N)|\leqnn/2.
Equality in this bound is attained for a real matrix N if and only if N is a Hadamard matrix.
A positive-semidefinite matrix P can be written as N*N, where N* denotes the conjugate transpose of N (see Decomposition of a semidefinite matrix). Then
\det(P)=\det(N)2\le
| n | |
| \prod | |
| i=1 |
| 2 | |
| \|v | |
| i\| |
=
| n | |
| \prod | |
| i=1 |
pii.
The result is trivial if the matrix N is singular, so assume the columns of N are linearly independent. By dividing each column by its length, it can be seen that the result is equivalent to the special case where each column has length 1, in other words if ei are unit vectors and M is the matrix having the ei as columns then
and equality is achieved if and only if the vectors are an orthogonal set. The general result now follows:
\left|\detN\right|=
| n | |
| (\prod | |
| i=1 |
\|vi\|)\left|\detM\right|\leq
| n | |
| \prod | |
| i=1 |
\|vi\|.
To prove (1), consider P =M*M where M* is the conjugate transpose of M, and let the eigenvalues of P be λ1, λ2, … λn. Since the length of each column of M is 1, each entry in the diagonal of P is 1, so the trace of P is n. Applying the inequality of arithmetic and geometric means,
\detP=
| n | |
| \prod | |
| i=1 |
λi\le({1\over
| n | |
| n}\sum | |
| i=1 |
| n | |
| λ | |
| i) |
=\left({1\overn}\operatorname{tr}P\right)n=1n=1,
\left|\detM\right|=\sqrt{\detP}\le1.
If there is equality then each of the λi's must all be equal and their sum is n, so they must all be 1. The matrix P is Hermitian, therefore diagonalizable, so it is the identity matrix—in other words the columns of M are an orthonormal set and the columns of N are an orthogonal set.[6] Many other proofs can be found in the literature.