Check if Matrix is Positive Definite

#332 · Linear Algebra · Medium

Problem

Check whether a given symmetric matrix is positive definite. A symmetric matrix is positive definite if all its eigenvalues are positive, or equivalently, if Cholesky decomposition succeeds.

Solution

from typing import List

def is_positive_definite(matrix: List[List[float]], tol: float = 1e-9) -> bool:
    n = len(matrix)
    if n == 0:
        return True

    # Check symmetry
    for i in range(n):
        for j in range(i + 1, n):
            if abs(matrix[i][j] - matrix[j][i]) > tol:
                return False

    # Attempt Cholesky decomposition
    L = [[0.0] * n for _ in range(n)]

    for i in range(n):
        for j in range(i + 1):
            s = sum(L[i][k] * L[j][k] for k in range(j))

            if i == j:
                val = matrix[i][i] - s
                if val <= tol:
                    return False
                L[i][j] = val ** 0.5
            else:
                if abs(L[j][j]) < tol:
                    return False
                L[i][j] = (matrix[i][j] - s) / L[j][j]

    return True

Explanation

First verify the matrix is symmetric (a[i][j] == a[j][i] for all i, j).
Attempt Cholesky decomposition: A = L * L^T where L is lower triangular.
For diagonal elements: L[i][i] = sqrt(A[i][i] - sum of squares of earlier L entries). If the value under the square root is non-positive, the matrix is not positive definite.
If decomposition completes successfully, the matrix is positive definite.

Complexity

Time: O(n^3) for Cholesky decomposition
Space: O(n^2) for the L matrix

← #331 #333 →