Positive Definite Matrices

POSITIVE DEFINITE MATRICES

The eigenvalues of any symmetric matrix are real. This section is about the case in which the eigenvalues are positive. These matrices, which arise whenever optimization (maximum or minimum) problem are encountered in the fields of science and engineering.

Definition: Positive definite matrices

A square matrix is called positive definite, if it is symmetric and all its eigenvalues λ are positive (ie. λ>0)

Note:

1. If A is positive definite, then it is invertible and |A|>0.

2. A symmetric matrix A is positive definite if and only if X^TAX>0 for every column X ≠0 in Rⁿ.

To know about positive definite matrices, we should familiar with normal matrices and Hermitian matrices.

Definition: Normal matrices

The Hermitian transpose of a matrix A, denoted by A^H is the complex conjugate transpose of A (ie) A^H=. A matrix A is normal if AA^H=A^HA.

Normal matrices have the following properties.

Properties

1. Every normal matrix is similar to a diagonal matrix.

2. Every normal matrix possesses a canonical basis of eigenvectors which can be arranged to form an orthonormal set.

Definition: Hermitian matrices

A matrix is Hermitian if it equals its own Hermitian transpose (or complex conjugate transpose).

 (ie) A is Hermitian if A = A^H

The sum of Hermitian matrices is Hermitian, as is the product of a Hermitian matrix with a real scalar. A Hermitian matrix is also normal because AA^H = AA = A^HA.

Properties

1. The eigenvalues of a Hermitian matrix are real.

2. If a Hermitian matrix A can be reduced to upper triangular matrix U using only elementary row operations. Then the diagonals of U contains the same number of zeros, the same number of positive values and the same number of negative values as the eigenvalues of A.

3. An n×n matrix A is Hermitian if and only if <AX, X> is real for all real and complex n−dimensional vectors X.

Definition: Real symmetric matrices

A matrix is symmetric if it equals its own transpose. A symmetric matrix that contains only real elements is Hermitian and therefore, normal. Consequently, real symmetric matrices possess all the 5 properties from normal matrices and Hermitian matrices along with

Property

1. The eigenvectors of a real symmetric matrix can be chosen to be real.

Definition: The Adjoint

The adjoint of an n×m matrix A is an m×n matrix A* having the property that

 (X, AY)_w = (A*X, Y)_w for all m−dimensional vectors Y and n−dimensional vectors X.

 A* = (W^HW)^‒1 A^H (W^H W).

For W= 1 (the Euclidean inner product), the above relation for A* reduces to A* = A^H.

1. (A*)* = A

2. (A+B)* = A* + B*

3. (AB)* = B*A*

4. (CA)* = A* for any scalar C.

Definition: Self Self Adjoint Matrices

A matrix A is self−adjoint if it equals its own adjoint. Such a matrix is a square matrix and it satisfies the identity

  <X,AY>_w = <AX, Y>_w

for all vectors X and Y. A matrix is self−adjoint with respect to the Euclidean inner product if and only if it is Hermitian.

Definite matrices

Let an n×n Hermitian matrix be A. It is said to be

(i) Positive definite: If <AX, X> > 0

(ii) Positive semi−definite: If <AX.X> ≥ 0

(iii) Negative definite: If <AX, X> < 0

(iv) Negative semi−definite: If <AX, X> ≤ 0

Note:

1. The sum two definite matrices of the same type is again a definite matrix of that type.

2. Positive or negative definite matrices are inversible and their inverses are also positive or negative definite.

1. Tests for positive definiteness

The following three tests stipulates necessary and sufficient conditions for an n×n Hermitian matrix A to be positive definite.

That means, a Hermitian matrix A is positive definite if it satisfies any one of the three tests.

Test 1: A is positive definite if and only if it can be reduced to upper triangular form using elementary row operations and the diagonal elements of the resulting matrix (the pivots) are all positive.

Test 2: A principal minor of A is the determinant of any submatrix obtained from A by deleting its last k rows and k columns (k = 0, 1, 2, 3, 4 …., n−1). A is positive definite if and only if all its principal minors are positive.

Test 3: A is positive definite if and only if all its eigenvalues are positive.

The following tests stipulate necessary condition for an n×n matrix A = [a_ij] to be positive definite. A Hermitian matrix that fails any one these tests is not positive definite.

Test 4: The diagonal elements of A must be positive.

Test 5: The elements of A having greatest absolute value must be on the diagonal of A.

Test 6: a_ija_jj > |a_ij|² (i ≠ j)

2. Tests for positive semi−definiteness

All these 6 tests may be changed to test for positive semi−definite by replacing the word positive with non−negative and replacing > with ≥.

3. Test for negative definiteness

In all the above 6 tests, the word positive is to be replaced with the word negative, and replacing > with <.

4. Test for negative semi−definiteness

In all the above 6 tests, the word positive is to be replaced with the word non−negative with non−positive and replacing > with ≤.

Definition: Square roots of matrices

The square root of a matrix A is a matrix A^1/2 having the property that A=A^1/2.A^1/2_. If A and A^1/2 are both required to be positive definite or positive semi−definite, then A^1/2 is unique and the square root is a well defined function.

5. Cholesky decomposition

 Any positive definite matrix A may be factored into

 A=LL^H

 Where L is the lower triangular matrix having positive values on its diagonal. This equation defines the Cholesky decomposition for A which is unique.

The following algorithm generates the Cholesky decomposition for an n×n matrix A = [a_ij] by sequentially identifying the columns of L on and below the main diagonal.

Step 1: Initialization

Set all elements of L above the main diagonal equal to zero, and let l₁₁=√a₁₁. The remainder of the first column of L is the first column of A divided by l₁₁. Set a counter j=2.

Step 2:

If j=n+1 stop. The algorithm is complete. Otherwise, define L'_i(i = j, j + 1, j + 2... n) to be a column vector of dimension j−1 whose components are respectively the first j−1 elements in the i^th row of L. These elements have already been computed.

Step 3:

 Compute l_ij = √ [ a_jj ‒ <L'_j, L_j'> ].

Step 4:

If j=n skip to step 5. Otherwise compute the j^th column of L below the main diagonal.

For each i = j+1, j+2, ... n, compute l_ij= [ a_jj ‒ <L _i' ‒ L_j'> ] / l_jj

Step 5:

Increase j by 1 and return to step 2.