Main Content

Determine Whether Matrix Is Symmetric Positive Definite

This topic explains how to use the chol and eig functions to determine whether a matrix is symmetric positive definite (a symmetric matrix with all positive eigenvalues).

Method 1: Attempt Cholesky Factorization

The most efficient method to check whether a matrix is symmetric positive definite is to simply attempt to use chol on the matrix. If the factorization fails, then the matrix is not symmetric positive definite. This method does not require the matrix to be symmetric for a successful test (if the matrix is not symmetric, then the factorization fails).

A = [1 -1 0; -1 5 0; 0 0 7]
A = 3×3

     1    -1     0
    -1     5     0
     0     0     7

try chol(A)
    disp('Matrix is symmetric positive definite.')
catch ME
    disp('Matrix is not symmetric positive definite')
end
ans = 3×3

    1.0000   -1.0000         0
         0    2.0000         0
         0         0    2.6458

Matrix is symmetric positive definite.

The drawback of this method is that it cannot be extended to also check whether the matrix is symmetric positive semi-definite (where the eigenvalues can be positive or zero).

Method 2: Check Eigenvalues

While it is less efficient to use eig to calculate all of the eigenvalues and check their values, this method is more flexible since you can also use it to check whether a matrix is symmetric positive semi-definite. Still, for small matrices the difference in computation time between the methods is negligible to check whether a matrix is symmetric positive definite.

This method requires that you use issymmetric to check whether the matrix is symmetric before performing the test (if the matrix is not symmetric, then there is no need to calculate the eigenvalues).

tf = issymmetric(A)
tf = logical
   1

d = eig(A)
d = 3×1

    0.7639
    5.2361
    7.0000

isposdef = all(d > 0)
isposdef = logical
   1

You can extend this method to check whether a matrix is symmetric positive semi-definite with the command all(d >= 0).

Numerical Considerations

The methods outlined here might give different results for the same matrix. Since both calculations involve round-off errors, each algorithm checks the definiteness of a matrix that is slightly different from A. In practice, the use of a tolerance is a more robust comparison method, since eigenvalues can be numerically zero within machine precision and be slightly positive or slightly negative.

For example, if a matrix has an eigenvalue on the order of eps, then using the comparison isposdef = all(d > 0) returns true, even though the eigenvalue is numerically zero and the matrix is better classified as symmetric positive semi-definite.

To perform the comparison using a tolerance, you can use the modified commands

tf = issymmetric(A)
d = eig(A)
isposdef = all(d > tol)
issemidef = all(d > -tol)

The tolerance defines a radius around zero, and any eigenvalues within that radius are treated as zeros. A good choice for the tolerance in most cases is length(d)*eps(max(d)), which takes into account the magnitude of the largest eigenvalue.

See Also

|

Related Topics