Cholesky Decomposition Calculator

Decompose a symmetric positive definite matrix A into the product LLT with step-by-step computation.

Enter Matrix A

Matrix A (must be symmetric positive definite):

Result

Decomposition A = LLT
L computed
Lower triangular matrix L
Matrix L-
Matrix LT-
Determinant of A-

Step-by-Step Solution

A = L × LT

Understanding Cholesky Decomposition

The Cholesky decomposition, named after French military officer and mathematician Andre-Louis Cholesky (1875-1918), factors a symmetric positive definite matrix A into the product of a lower triangular matrix L and its transpose LT. This decomposition is written as A = LLT, and it is roughly twice as efficient as the LU decomposition for solving linear systems.

A matrix A is positive definite if xTAx > 0 for all non-zero vectors x. Equivalently, all eigenvalues of A must be positive. For the Cholesky decomposition to exist, the matrix must be both symmetric (A = AT) and positive definite.

Cholesky Decomposition Formulas

Diagonal Elements

Each diagonal element of L is computed by subtracting the sum of squares of elements in the same row.

L[i][i] = sqrt(A[i][i] - sum(L[i][k]^2))

Off-Diagonal Elements

Off-diagonal elements use the corresponding row elements already computed.

L[i][j] = (A[i][j] - sum(L[i][k]*L[j][k])) / L[j][j]

2x2 Matrix

For a 2x2 matrix [[a,b],[b,c]], the decomposition gives specific closed-form results.

L = [[sqrt(a), 0], [b/sqrt(a), sqrt(c-b^2/a)]]

Determinant

The determinant of A equals the square of the product of diagonal elements of L.

det(A) = (L[0][0] * L[1][1] * ...)^2

Properties of the Cholesky Factor

  • Lower triangular: L is a lower triangular matrix with positive diagonal entries.
  • Uniqueness: The Cholesky decomposition is unique for a positive definite matrix.
  • Numerical stability: The algorithm is numerically stable and does not require pivoting.
  • Efficiency: Requires approximately n3/3 operations, half of what LU decomposition needs.

Applications of Cholesky Decomposition

Cholesky decomposition is widely used in numerical analysis and scientific computing. It appears in least squares problems, Monte Carlo simulations, Kalman filtering, and optimization algorithms. Its efficiency and numerical stability make it the preferred method for solving systems involving positive definite matrices.

  • Linear system solving: Solve Ax = b by first solving Ly = b (forward substitution) then LTx = y (back substitution).
  • Monte Carlo simulation: Generate correlated random variables from independent ones using the Cholesky factor of the covariance matrix.
  • Optimization: Used in Newton's method when the Hessian matrix is positive definite.
  • Kalman filters: The square-root form of the Kalman filter uses Cholesky decomposition for improved numerical stability.
  • Matrix inversion: Efficiently invert positive definite matrices through the Cholesky factor.

When Does the Decomposition Fail?

The Cholesky decomposition fails if the matrix is not positive definite. During computation, this manifests as a negative value under a square root. Common reasons include: the matrix is not symmetric, the matrix has non-positive eigenvalues, or the matrix is singular. This calculator will alert you if the decomposition cannot be performed.

Tips for Using This Calculator

  • Ensure your matrix is symmetric: A[i][j] should equal A[j][i].
  • All eigenvalues must be positive for the decomposition to exist.
  • The calculator supports both 2x2 and 3x3 matrices.
  • Results are rounded to 6 decimal places for display.