Skip to main content
Home

Linear Systems Solvers

Choose a solver below

Solving Systems

Decompositions

Vector Spaces

Need Help?

Check the educational content below each solver for detailed explanations.

View all tutorials →
Calculating...
Home Linear Systems Cholesky_Decomposition

Cholesky Decomposition Calculator: LL^T Factorization for Symmetric Positive Definite Matrices

Perform Cholesky Decomposition of a symmetric positive definite matrix A into lower triangular L and its transpose: A = LL^T. Optionally solve the linear system Ax = b using forward and back substitution.

Calculator

Enter your matrix below and click "Calculate" to see the step-by-step solution.

n =
Maximum size: 6×6

Cholesky decomposition requires symmetric positive definite matrices

A Coefficient Matrix A (n × n) - Must be Symmetric Positive Definite

b Constant Vector b (Optional)

Performing Cholesky decomposition...

Enter a symmetric positive definite matrix A to compute its Cholesky decomposition A = LL^T.

Optionally provide vector b to solve the system Ax = b.

Learn About Cholesky_Decomposition

Understanding the concepts behind the calculations.

📑 Quick Navigation

What is Cholesky Decomposition?

Cholesky decomposition (or Cholesky factorization) factors a symmetric positive definite matrix A into the product of a lower triangular matrix L and its transpose:

$$ \boxed{A = LL^T} $$

Where:

  • L is a lower triangular matrix with positive diagonal entries
  • L^T is the transpose of L (upper triangular)

Named after: André-Louis Cholesky (1875-1918), a French mathematician and military officer who developed this method for geodesy and surveying. The method was published posthumously after he was killed in action during World War I.

This decomposition is like a "square root" for matrices—analogous to how a positive real number has a real square root.

Requirements for Cholesky Decomposition

For a matrix to have a Cholesky decomposition, it must satisfy all three conditions:

✅ 1. Square Matrix

Must have the same number of rows and columns (n × n).

✅ 2. Symmetric

Must equal its transpose: A = A^T

Check: aᵢⱼ = aⱼᵢ for all i, j

✅ 3. Positive Definite

All eigenvalues > 0, or equivalently:

x^T A x > 0 for all non-zero vectors x

All leading principal minors > 0

💡 Quick Check: Use our Positive Definite Checker to verify if your matrix is eligible for Cholesky decomposition!

⚠️ Note: If any condition fails, Cholesky decomposition cannot be performed. Consider LU Decomposition instead.

The Cholesky Algorithm

For a symmetric positive definite matrix A of size n×n, we compute L as follows:

Step 1: Compute Diagonal Entry

$$ l_{ii} = \sqrt{a_{ii} - \sum_{k=1}^{i-1} l_{ik}^2} $$

Step 2: Compute Off-Diagonal Entries

$$ l_{ji} = \frac{a_{ji} - \sum_{k=1}^{i-1} l_{jk} l_{ik}}{l_{ii}} \quad \text{for } j = i+1, i+2, \dots, n $$

📐 Order of Computation: Work from top-left to bottom-right, computing column by column. Once an entry is computed, it never changes.

Step-by-Step Example

Problem: Find the Cholesky decomposition of:

$$ A = \begin{bmatrix} 4 & 2 & 2 \\\\ 2 & 5 & 1 \\\\ 2 & 1 & 6 \end{bmatrix} $$

Step 1: Compute l₁₁ (first diagonal)

$$ l_{11} = \sqrt{a_{11}} = \sqrt{4} = 2 $$

Step 2: Compute l₂₁ and l₃₁ (first column below diagonal)

$$ l_{21} = \frac{a_{21}}{l_{11}} = \frac{2}{2} = 1 $$
$$ l_{31} = \frac{a_{31}}{l_{11}} = \frac{2}{2} = 1 $$

Step 3: Compute l₂₂ (second diagonal)

$$ l_{22} = \sqrt{a_{22} - l_{21}^2} = \sqrt{5 - 1^2} = \sqrt{4} = 2 $$

Step 4: Compute l₃₂ (second column below diagonal)

$$ l_{32} = \frac{a_{32} - l_{31} \cdot l_{21}}{l_{22}} = \frac{1 - (1)(1)}{2} = \frac{0}{2} = 0 $$

Step 5: Compute l₃₃ (third diagonal)

$$ l_{33} = \sqrt{a_{33} - (l_{31}^2 + l_{32}^2)} = \sqrt{6 - (1^2 + 0^2)} = \sqrt{5} $$

Result:

$$ L = \begin{bmatrix} 2 & 0 & 0 \\\\ 1 & 2 & 0 \\\\ 1 & 0 & \sqrt{5} \end{bmatrix}, \quad L^T = \begin{bmatrix} 2 & 1 & 1 \\\\ 0 & 2 & 0 \\\\ 0 & 0 & \sqrt{5} \end{bmatrix} $$

✓ Verification: A = L·L^T. Check the (2,3) entry: row2·col3 = (1)(1) + (2)(0) + (0)(√5) = 1 ✓

Solving Linear Systems with Cholesky

To solve Ax = b using Cholesky decomposition:

$$ A = LL^T \quad\Rightarrow\quad LL^T x = b $$

Step 1: Forward Substitution

Solve Ly = b for y (easy because L is lower triangular)

Step 2: Back Substitution

Solve L^T x = y for x (easy because L^T is upper triangular)

Why this is efficient: Cholesky requires about n³/3 operations, compared to 2n³/3 for LU decomposition—twice as fast!

Example: Solve Ax = b with A from above and b = [4, 7, 8]ᵀ

Forward substitution: y₁ = 2, y₂ = 3, y₃ = 5

Back substitution: x₃ = 5/√5 ≈ 2.236, x₂ = 1.5, x₁ = -0.5

Advantages & Applications

✅ Advantages Over LU

  • 2x faster (~n³/3 vs ~2n³/3 operations)
  • 50% less memory (only store L, not L + U)
  • Always stable (no pivoting needed for SPD matrices)
  • Preserves symmetry naturally

📊 Real-World Applications

  • Numerical Optimization - Newton's method with Hessian
  • Statistics - Covariance matrix factorization
  • Machine Learning - Gaussian processes (kernel matrices)
  • Signal Processing - Kalman filters
  • Computational Finance - Portfolio optimization
  • Finite Element Methods - Solving sparse SPD systems

📈 Performance Comparison:

$$ \text{LU: } \frac{2}{3}n^3 \text{ ops} \quad \text{vs} \quad \text{Cholesky: } \frac{1}{3}n^3 \text{ ops} $$

For n = 1000, Cholesky is about 167 million operations faster!

Frequently Asked Questions

Q: Can Cholesky fail for a positive definite matrix?

A: No—theoretically, Cholesky always works for SPD matrices. However, numerical rounding errors can cause issues for nearly singular matrices (ill-conditioned).

Q: What if my matrix is symmetric but not positive definite?

A: Use LDL^T decomposition instead (similar but allows zero/negative pivots). Try our Positive Semidefinite Checker to see where your matrix stands.

Q: Can I do Cholesky on indefinite matrices?

A: No—the square root of a negative number would appear. Use LU Decomposition with pivoting instead.

Q: Why is Cholesky more stable than LU?

A: For SPD matrices, the entries of L grow no faster than the diagonal entries of A. LU pivoting can cause arbitrary growth, leading to instability.

Q: What's the relationship to square roots?

A: Just as a positive number has a real square root (a = √a·√a), a positive definite matrix has a "matrix square root" A = L·L^T.

Practice Problems

Beginner

  1. Find the Cholesky decomposition of:

    $$ A = \begin{bmatrix} 9 & 3 \\ 3 & 5 \end{bmatrix} $$

  2. Check if this matrix qualifies for Cholesky:

    $$ A = \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix} $$

Intermediate

  1. Complete the Cholesky decomposition:

    $$ A = \begin{bmatrix} 16 & 4 & 8 \\ 4 & 5 & -4 \\ 8 & -4 & 22 \end{bmatrix} $$

  2. Solve Ax = b using Cholesky where A is from problem 1 and b = [6, 4]ᵀ

Click to reveal solutions

1. L = [[3, 0], [1, 2]]

2. No - symmetric but not positive definite (det = -3)

3. L = [[4, 0, 0], [1, 2, 0], [2, -3, 3]]

4. y = [2, 1]ᵀ, x = [0.5, 0.5]ᵀ

Try It Yourself!

Use the calculator above to perform Cholesky decomposition:

  1. Enter your symmetric matrix (must be square)
  2. Click "Calculate" to see:
    • Verification of symmetry and positive definiteness
    • Step-by-step computation of L
    • Verification that A = L·L^T
    • Option to solve a system with the decomposed matrix

📐 Try these examples:

  • 2×2 SPD: [[4, 2], [2, 5]]
  • 3×3 SPD: [[4, 2, 2], [2, 5, 1], [2, 1, 6]] (from our example)
  • Not SPD: [[1, 2], [2, 1]] (see what happens!)
  • Identity: [[1, 0], [0, 1]] (L = I)

💡 Pro Tip: Cholesky is the fastest and most stable method for solving symmetric positive definite systems. Use it whenever your matrix meets the requirements!