Positive-definite matrix

Top

Home > Library > Miscellaneous > Wikipedia

In linear algebra, a positive-definite matrix is a matrix that in many ways is analogous to a positive real number. The notion is closely related to a positive-definite symmetric bilinear form (or a sesquilinear form in the complex case).

The proper definition of positive-definite is unambiguous for Hermitian matrices, but there is no agreement in the literature on how this should be extended for non-Hermitian matrices, if at all. (See the section Non-Hermitian matrices below.)

Contents

1 Definition
2 Examples
3 Characterizations
- 3.1 Quadratic forms
4 Simultaneous diagonalization
5 Negative-definite, semidefinite and indefinite matrices
6 Further properties
7 Block matrices
8 Non-Hermitian matrices
9 See also
10 Notes
11 References
12 External links

Definition

An n × n real matrix M is positive definite if z^TMz > 0 for all non-zero vectors z with real entries ( $z \in \mathbb{R}^n$ ), where z^T denotes the transpose of z.

An n × n complex matrix M is positive definite if ℜ(z^*Mz) > 0 for all non-zero complex vectors z, where z^* denotes the conjugate transpose of z and ℜ(c) is the real part of a complex number c.

An n × n complex Hermitian matrix M is positive definite if z^*Mz > 0 for all non-zero complex vectors z. The quantity z^*Mz is always real because M is a Hermitian matrix.

Examples

The nonnegative matrix $M_0 = \begin{bmatrix} 1 & 0 \\ 0 & 1\end{bmatrix}$ is positive definite. For a vector with entries $\textbf{z}= \begin{bmatrix} z_0 \\ z_1\end{bmatrix}$ the quadratic form is $\begin{bmatrix} z_0 & z_1\end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} z_0 \\ z_1\end{bmatrix}=\begin{bmatrix} z_0\cdot 1+z_1\cdot 0 & z_0\cdot 0+z_1\cdot 1\end{bmatrix} \begin{bmatrix} z_0 \\ z_1\end{bmatrix}=z_0^2+z_1^2;$

when the entries z₀, z₁ are real and at least one of them nonzero, this is positive.

A matrix in which some elements are negative may still be positive-definite. An example is given by $M_1 = \begin{bmatrix} 2&-1&0\\-1&2&-1\\0&-1&2 \end{bmatrix}.$ It is positive definite since for any non-zero vector $x = \begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}$ , we have

$\begin{align} x^{\mathrm T}M_1 x &= \begin{bmatrix} x_1&x_2&x_3 \end{bmatrix} \begin{bmatrix} 2&-1&0\\-1&2&-1\\0&-1&2 \end{bmatrix} \begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix} \\ &= \begin{bmatrix} (2x_1-x_2)&(-x_1+2x_2-x_3)&(-x_2+2x_3) \end{bmatrix} \begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix} \\ &= 2{x_1}^2 - 2x_1x_2 + 2{x_2}^2 - 2x_2x_3 + 2{x_3}^2 \\ &= {x_1}^2+(x_1 - x_2)^{2} + (x_2 - x_3)^{2}+{x_3}^2 \end{align}$

which is a sum of squares and therefore nonnegative; in fact, each squared summand can be zero only when $x_1 = x_2 = x_3 = 0$ , so $M_1$ is indeed positive-definite.

Conversely, the positive matrix $M_2 = \begin{bmatrix} 1 & 2 \\ 2 & 1\end{bmatrix}$ is not positive definite, showing (together with the previous example) that these two properties are independent. Evaluated at $\textbf{z}= \begin{bmatrix} 1\\ -1\end{bmatrix}$ , the quadratic form is $\begin{bmatrix} 1 & -1\end{bmatrix} \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ -1\end{bmatrix}=-2 < 0.$

In statistics, covariance matrices have the property of positive semi-definiteness, and they are positive definite unless one variable is an exact linear combination of the others. In fact, every positive definite matrix is the covariance matrix of some multivariate probability distribution.

Characterizations

Let M be an n × n Hermitian matrix. The following properties are equivalent to M being positive definite:

1.	All eigenvalues λ_i of M are positive. Recall that any Hermitian M has an eigendecomposition M = P⁻¹DP where P is a unitary matrix whose rows are orthonormal eigenvectors of M, forming a basis, and D is a diagonal matrix. Therefore M may be regarded as a real diagonal matrix D that has been re-expressed in some new coordinate system. This characterization means that M is positive definite if and only if the diagonal elements of D (the eigenvalues) are all positive. In other words, in the basis consisting of the eigenvectors of M, the action of M is component-wise multiplication with a (fixed) element in Cⁿ with positive entries^{[clarification needed]}.
2.	The sesquilinear form $\langle \mathbf{x},\mathbf{y}\rangle := \mathbf{y}^*\mathbf{M}\mathbf{x}$ defines an inner product on Cⁿ. (In fact, every inner product on Cⁿ arises in this fashion from a Hermitian positive definite matrix.) In particular, positive definiteness for a Hermitian M is equivalent to the fact that $\langle \mathbf{x},\mathbf{x}\rangle > 0$ for all nonzero x.
3.	M is the Gram matrix of some collection of linearly independent vectors $\textbf{x}_1,\ldots,\textbf{x}_n \in \mathbb{C}^k$ for some k. That is, M satisfies: $M_{ij} = \langle \textbf{x}_i, \textbf{x}_j\rangle = \textbf{x}_i^{} \textbf{x}_j.$ The vectors x_i* may optionally be restricted to fall in Cⁿ. In other words, M is of the form $A^{}A$* where A is not necessarily square but must be injective in general.
4.	All the following matrices have a positive determinant (Sylvester's criterion): the upper left 1-by-1 corner of $M$ the upper left 2-by-2 corner of $M$ the upper left 3-by-3 corner of $M$ ... $M$ itself In other words, all of the leading principal minors are positive. In practice, this condition is often used to check the positive definiteness of any given square, symmetric matrix. The given matrix is first upper triangularized by using elementary row operations, in the fashion similar to the forward elimination process of the Gaussian elimination method. However, caution must be taken during pivoting process, as this can change the sign of the determinant. The Sylvester's criterion is then checked each time a leading principle submatrix is triangularized, the determinant of the triangular submatrix being given simply by the product of its diagonal elements. If the criterion is true of all the leading principle submatrix, then the matrix is declared to be positive definite. For positive semidefinite matrices, all principal minors have to be non-negative. The leading principal minors alone do not imply positive semidefiniteness, as can be seen from the example $\begin{bmatrix} 0 & 0 \\ 0 & -1 \end{bmatrix}.$
5.	There exists a lower triangular matrix $L$ , with strictly positive diagonal elements, that allows the factorization of $M$ into $M=L L^$ . where $L^$ is the conjugate transpose of $L$ . This factorization is called Cholesky decomposition for positive definite matrices, and for them it is unique.
6.	The quadratic function associated with M $f(\mathbf{x}) = \frac12 \mathbf{x}^\mathrm{T} M \mathbf{x} - \mathbf{x}^\mathrm{T} \mathbf{b}$ is, regardless of b, a strictly convex function. $f(\mathbf{x})$ has a unique global minimum, and this is why positive definite matrices are so common in optimization problems.

For real symmetric matrices, these properties can be simplified by replacing $\mathbb{C}^n$ with $\mathbb{R}^n$ , and "conjugate transpose" with "transpose."

Quadratic forms

Echoing condition 2 above, one can also formulate positive-definiteness in terms of quadratic forms. Let K be the field R or C, and V be a vector space over K. A Hermitian form

$B : V \times V \rightarrow K$

is a bilinear map such that B(x, y) is always the complex conjugate of B(y, x). Such a function B is called positive definite if B(x, x) > 0 for every nonzero x in V.

Simultaneous diagonalization

Two symmetric, positive-definite matrices can be simultaneously diagonalized, although not necessarily via a similarity transformation. This result does not extend to the case of three or more matrices. In this section we write for the real case, extension to the complex case is immediate.

Let $M$ and $N$ be two positive-definite matrices. Write the generalized eigenvalue equation as $(M - \lambda N)x=0$ where $x^{\mathrm T} N x =1$ . Now we can decompose the inverse of $N$ as $Q^{\mathrm T} Q$ (so $N$ must be positive definite, as the proof shows, in fact it is enough that $M$ is symmetric). Now multiply various places with $Q$ to get $Q(M - \lambda N)Q^{\mathrm T} Q^{-\mathrm T} x =0$ which we can rewrite as $(Q M Q^{\mathrm T})y= \lambda y$ where $y^{\mathrm T} y=1$ . Manipulation now yields $M X = N X \Lambda$ where $X$ is a matrix having as columns the generalized eigenvectors and $\Lambda$ is a diagonal matrix with the generalized eigenvalues. Now premultiplication with $X^{\mathrm T}$ gives the final result:

$X^{\mathrm T} M X = \Lambda$ and $X^{\mathrm T} N X = I$ , but note that this is no longer an orthogonal diagonalization.

Note that this result does not contradict what is said on simultaneous diagonalization in the article Diagonalizable matrix, which refers to simultaneous diagonalization by a similarity transformation. Our result here is more akin to a simultaneous diagonalization of two quadratic forms, and is useful for optimization of one form under conditions on the other. For this result see Horn&Johnson, 1985, page 218 and following.

Negative-definite, semidefinite and indefinite matrices

A Hermitian matrix is negative-definite, negative-semidefinite, or positive-semidefinite if and only if all of its eigenvalues are negative, non-positive, or non-negative, respectively.

Negative-definite

The n × n Hermitian matrix M is said to be negative-definite if

$x^{*} M x < 0\,$

for all non-zero $x \in \mathbb{C}^n$ (or, all non-zero $x \in \mathbb{R}^n$ for the real matrix).

A matrix is negative definite if all kth order leading principal minors are negative if k is odd and positive if k is even.

Positive-semidefinite

It is called positive-semidefinite (or sometimes nonnegative-definite) if

$x^{*} M x \geq 0$

for all $x \in \mathbb{C}^n$ (or, all $x \in \mathbb{R}^n$ for the real matrix), where $x^{*}$ is the conjugate transpose of $x$ .

A matrix M is positive-semidefinite if and only if it arises as the Gram matrix of some set of vectors. In contrast to the positive-definite case, these vectors need not be linearly independent.

For any matrix A, the matrix A^*A is positive semidefinite, and rank(A) = rank(A^*A). Conversely, any Hermitian positive semidefinite matrix M can be written as M = A^*A; this is the Cholesky decomposition.

Negative-semidefinite

It is called negative-semidefinite if

$x^{*} M x \leq 0$

for all $x \in \mathbb{C}^n$ (or, all $x \in \mathbb{R}^n$ for the real matrix).

Indefinite

A Hermitian matrix which is neither positive definite, negative definite, positive-semidefinite, nor negative-semidefinite is called indefinite. Indefinite matricies are also characterized by their having both positive and negative eigenvalues.

Further properties

If M is an Hermitian positive-semidefinite matrix, one sometimes writes M ≥ 0 and if M is positive-definite one writes M > 0.^[1] The notion comes from functional analysis where positive-semidefinite matrices define positive operators.

For arbitrary square matrices M,N we write M ≥ N if M − N ≥ 0; i.e., M − N is positive semi-definite. This defines a partial ordering on the set of all square matrices. One can similarly define a strict partial ordering M > N.

Every positive definite matrix is invertible and its inverse is also positive definite.^[2] If M ≥ N > 0 then N⁻¹ ≥ M⁻¹ > 0.^[3]
If M is positive definite and r > 0 is a real number, then r M is positive definite.^[4] If M and N are positive definite, then the sum M + N^[4] and the products MNM and NMN are also positive definite. If MN = NM, then MN is also positive definite.
If M = (m_ij) ≥ 0 then the diagonal entries m_ii are real and non-negative. As a consequence the trace, tr(M) ≥ 0. Furthermore^[5]

$|m_{ij}| \leq \sqrt{m_{ii} m_{jj}} \leq \frac{1}{2}(m_{ii}+m_{jj})$

and thus

$\max |m_{ij}| \leq \max|m_{ii}|$
If $M$ is a symmetric matrix of the form $m_{ij}=m(i-j)$ , and the strict inequality holds

$\sum_{j\neq 0}|m(j)|< m(0)$

then $M$ is strictly positive definite.
A matrix M is positive semi-definite if and only if there is a positive semi-definite matrix B with B² = M. This matrix B is unique,^[6] is called the square root of M, and is denoted with B = M^1/2 (the square root B is not to be confused with the matrix L in the Cholesky factorization M = LL*, which is also sometimes called the square root of M). If M > N > 0 then M^1/2 > N^1/2 > 0.
If M,N > 0 then M ⊗ N > 0, where ⊗ denotes Kronecker product.
For matrices M = (m_ij) and N = (n_ij), write M ° N for the entry-wise product of M and N; i.e., the matrix whose i,j entry is m_ijn_ij. Then M ° N is the Hadamard product of M and N. The Hadamard product of two positive-definite matrices is again positive-definite and the Hadamard product of two positive-semidefinite matrices is again positive-semidefinite (this result is often called the Schur product theorem).^[7] Furthermore, if M and N are positive-semidefinite, then the following inequality, due to Oppenheim, holds:^[8]

$\det(M\cdot N) \geq (\det N) \prod_{i} m_{ii}.$
Let M > 0 and N Hermitian. If MN + NM ≥ 0 (resp., MN + NM > 0) then N ≥ 0 (resp., N > 0).^{[citation needed]}
If M,N ≥ 0 are real positive semidefinite symmetric matrices, then $\scriptstyle\operatorname{tr}(MN) \,\geq\, 0$ (Lancaster-Tismenetsky, The Theory of Matrices, p. 218).
If M > 0 is real, then there is a δ > 0 such that M > δI, where I is the identity matrix.

Block matrices

A positive 2n × 2n matrix may also be defined by blocks:

$M = \begin{bmatrix} A & B \\ C & D \end{bmatrix}$

Where each block is n × n. By applying the positivity condition, it immediately follows that A and D are hermitian, and C = B*.

We have that z^*Mz ≥ 0 for all complex z, and in particular for z = ( v, 0)^T. Then

$\begin{bmatrix} v^* & 0 \end{bmatrix} \begin{bmatrix} A & B \\ B^* & D \end{bmatrix} \begin{bmatrix} v \\ 0 \end{bmatrix} = v^* A v \ge 0$

A similar argument can be applied to D, and thus we conclude that both A and D must be positive definite matrices, as well.

Non-Hermitian matrices

A real matrix M may have the property that x^TMx > 0 for all nonzero real vectors x without being symmetric. The matrix

$\begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix}$

satisfies this property, because for all real vectors $x = (x_1, x_2)^{\mathrm T}$ such that $x \ne 0$ ,

$\begin{bmatrix} x_1 & x_2 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = x_1^2 + x_2^2 > 0 .$

In general, we have x^TMx > 0 for all real nonzero vectors x if and only if the symmetric part, (M + M^T) / 2, is positive definite.

The situation for complex matrices may be different, depending on how one generalizes the inequality z^*Mz > 0 when considering M which aren't necessarily Hermitian. If z^*Mz is real for all complex vectors z, then the matrix M must be Hermitian. To see this, we define the Hermitian matrices A=(M+M^*)/2 and B=(M-M^*)/(2i) so that M=A+iB. Then, z^*Mz=z^*Az+iz^*Bz is real. By the Hermiticity of A and B, z^*Az and z^*Bz are individually real so z^*Bz must be zero for all z. So then B is the zero matrix and M=A, which is Hermitian.

So, if we require that z^*Mz be real and positive, then M is automatically Hermitian. On the other hand, we have that Re(z^*Mz) > 0 for all complex nonzero vectors z if and only if the Hermitian part, (M + M^*) / 2, is positive definite.

In summary, the distinguishing feature between the real and complex case is that, a bounded positive operator on a complex Hilbert space is necessarily Hermitian, or self adjoint. The general claim can be argued using the polarization identity. That is no longer true in the real case.

There is no agreement in the literature on the proper definition of positive-definite for non-Hermitian matrices.

Notes

^ This may be confusing, as sometimes nonnegative matrices are also denoted in this way. A common alternative notation is $M \succeq 0$ and $M \succ 0$ for positive semidefinite and positive definite matrices, respectively.
^ Horn & Johnson (1985), p. 397
^ Horn & Johnson (1985), Corollary 7.7.4(a)
^ ^a ^b Horn & Johnson (1985), Observation 7.1.3
^ Horn & Johnson (1985), p. 398
^ Horn & Johnson (1985), Theorem 7.2.6 with k = 2
^ Horn & Johnson (1985), Theorem 7.5.3
^ Horn & Johnson (1985), Theorem 7.8.6

References

Horn, Roger A.; Johnson, Charles R. (1990), Matrix Analysis, Cambridge University Press, ISBN 978-0-521-38632-6 .
Rajendra Bhatia. Positive definite matrices. Princeton Series in Applied Mathematics, 2007. ISBN 978-0-691-12918-1.

External links

Wolfram MathWold: Positive Definite Matrix

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

Positive-definite matrix

Top

Some good "Positive-definite matrix" pages on the web:

Math
mathworld.wolfram.com

Help us answer these

Can conjugate gradient solve a linear system when the matrix is positive semi-definite?

How prove that if A is a matrix square and symmetric positive definite then aij aii ajj12?

Is Kendall tau matrix semidefinite positive?

Why alpha-cyano-4-hydroxycinnamicacid as matrix in positive ionisation?

Post a question - any question - to the WikiAnswers community:

Copyrights:

Cite

Wikipedia on Answers.com This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article Positive-definite matrix. Read