Hadamard's inequality
Encyclopedia
In mathematics
, Hadamard's inequality, first published by Jacques Hadamard
in 1893, is a bound on the determinant
of a matrix
whose entries are complex number
s 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 vi, then
and equality is achieved if and only if the vectors are orthogonal or at least one of the columns is 0.
In particular, if the entries of N are +1 and −1 only then
In combinatorics
, matrices N for which equality holds, i.e. those with orthogonal columns, are called Hadamard matrices
.
A positive-semidefinite matrix P can be written as N*N, where N* denotes the conjugate transpose
of N (see Cholesky decomposition
). Then
So, the determinant of a positive definite matrix is less than or equal to the product of its diagonal entries. Sometimes this is also known as Hadamard's inequality.
and equality is achieved if and only if the vectors are an orthogonal set, that is when the matrix is unitary. The general result now follows:
For the positive definite case, let P =M*M and let the eigenvalues of P be λ1, λ2, … λn. By assumption, each entry in the diagonal of P is 1, so the trace
of P is n. Applying the inequality of arithmetic and geometric means
,
so
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.
Many other proofs can be found in the literature.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, Hadamard's inequality, first published by Jacques Hadamard
Jacques Hadamard
Jacques Salomon Hadamard FRS was a French mathematician who made major contributions in number theory, complex function theory, differential geometry and partial differential equations.-Biography:...
in 1893, is a bound on the determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
of a matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
whose entries are complex number
Complex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...
s in terms of the lengths of its column vectors. In geometrical terms, when restricted to real numbers, it bounds the volume
Volume
Volume is the quantity of three-dimensional space enclosed by some closed boundary, for example, the space that a substance or shape occupies or contains....
in Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
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 vi, then
and equality is achieved if and only if the vectors are orthogonal or at least one of the columns is 0.
Alternate forms and corollaries
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, thenIn particular, if the entries of N are +1 and −1 only then
In combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, matrices N for which equality holds, i.e. those with orthogonal columns, are called Hadamard matrices
Hadamard matrix
In mathematics, an Hadamard matrix, named after the French mathematician Jacques Hadamard, is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal...
.
A positive-semidefinite matrix P can be written as N*N, where N* denotes the conjugate transpose
Conjugate transpose
In mathematics, the conjugate transpose, Hermitian transpose, Hermitian conjugate, or adjoint matrix of an m-by-n matrix A with complex entries is the n-by-m matrix A* obtained from A by taking the transpose and then taking the complex conjugate of each entry...
of N (see Cholesky decomposition
Cholesky decomposition
In linear algebra, the Cholesky decomposition or Cholesky triangle is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose. It was discovered by André-Louis Cholesky for real matrices...
). Then
So, the determinant of a positive definite matrix is less than or equal to the product of its diagonal entries. Sometimes this is also known as Hadamard's inequality.
Proof
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 thenand equality is achieved if and only if the vectors are an orthogonal set, that is when the matrix is unitary. The general result now follows:
For the positive definite case, let P =M*M and let the eigenvalues of P be λ1, λ2, … λn. By assumption, each entry in the diagonal of P is 1, so the trace
Trace (linear algebra)
In linear algebra, the trace of an n-by-n square matrix A is defined to be the sum of the elements on the main diagonal of A, i.e.,...
of P is n. Applying the inequality of arithmetic and geometric means
Inequality of arithmetic and geometric means
In mathematics, the inequality of arithmetic and geometric means, or more briefly the AM–GM inequality, states that the arithmetic mean of a list of non-negative real numbers is greater than or equal to the geometric mean of the same list; and further, that the two means are equal if and only if...
,
so
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.
Many other proofs can be found in the literature.