# Nakafa Learning Content

> For AI agents: use [llms.txt](https://nakafa.com/llms.txt) for the site index. Markdown versions are available by appending `.md` to content URLs or sending `Accept: text/markdown`.

URL: https://nakafa.com/en/subjects/ai-ds/linear-methods/cholesky-decomposition
Source: https://raw.githubusercontent.com/nakafaai/nakafa.com/refs/heads/main/packages/contents/material/lesson/ai-ds/linear-methods/cholesky-decomposition/en.mdx

Learn Cholesky decomposition for positive definite matrices with efficient algorithms, lower triangular factorization, and computational complexity analysis.

---

## LU Decomposition for Positive Definite Matrices

For positive definite matrices, there is a special property that makes decomposition much simpler. [LU decomposition](/en/subjects/ai-ds/linear-methods/lu-decomposition) can be performed without using a permutation matrix $$P$$ because Gaussian elimination can proceed without row swapping, and all pivot elements generated are guaranteed to be positive.

Visible text: For positive definite matrices, there is a special property that makes decomposition much simpler. [LU decomposition](/en/subjects/ai-ds/linear-methods/lu-decomposition) can be performed without using a permutation matrix because Gaussian elimination can proceed without row swapping, and all pivot elements generated are guaranteed to be positive.

This means we obtain factorization in the form $$A = L \cdot U$$, where the diagonal elements of $$U$$ are positive pivot elements for all diagonal indices.

Visible text: This means we obtain factorization in the form , where the diagonal elements of are positive pivot elements for all diagonal indices.

Since $$A = A^T$$, we also have:

Visible text: Since , we also have:

Component: MathContainer
Children:

```math
A = A^T = (L \cdot U)^T = (L \cdot D \cdot \tilde{U})^T = \tilde{U}^T \cdot D \cdot L^T
```

where $$\tilde{U}$$ is a matrix whose main diagonal is normalized to $$1$$, and $$D$$ is a diagonal matrix:

Visible text: where is a matrix whose main diagonal is normalized to , and is a diagonal matrix:

Component: MathContainer
Children:

```math
\tilde{U} = \begin{pmatrix} 1 & u_{12}/u_{11} & \cdots & u_{1n}/u_{11} \\ & \ddots & \ddots & \vdots \\ & & 1 & u_{n-1,n}/u_{n-1,n-1} \\ 0 & & & 1 \end{pmatrix}
```

```math
D = \begin{pmatrix} u_{11} & & 0 \\ & \ddots & \\ 0 & & u_{nn} \end{pmatrix}
```

Since LU decomposition without $$P$$ is unique, then:

Visible text: Since LU decomposition without is unique, then:

Component: MathContainer
Children:

```math
A = L \cdot U = \tilde{U}^T \cdot (D \cdot L^T)
```

```math
L = \tilde{U}^T \quad \text{and} \quad U = D \cdot L^T
```

If we define:

```math
D^{\frac{1}{2}} = \begin{pmatrix} \sqrt{u_{11}} & & 0 \\ & \ddots & \\ 0 & & \sqrt{u_{nn}} \end{pmatrix}
```

then $$D^{\frac{1}{2}} \cdot D^{\frac{1}{2}} = D$$.

Visible text: then .

## Cholesky Decomposition

Positive definite matrices $$A \in \mathbb{R}^{n \times n}$$ allow for Cholesky decomposition:

Visible text: Positive definite matrices allow for Cholesky decomposition:

```math
A = L \cdot D \cdot L^T = \tilde{L} \cdot \tilde{L}^T
```

where $$\tilde{L} = L \cdot D^{\frac{1}{2}}$$ is a regular lower triangular matrix. This matrix can be computed using the Cholesky algorithm.

Visible text: where is a regular lower triangular matrix. This matrix can be computed using the Cholesky algorithm.

The computation of matrix $$\tilde{L}$$ is performed with:

Visible text: The computation of matrix is performed with:

```math
\tilde{L} = \begin{pmatrix} \tilde{l}_{11} & 0 \\ \vdots & \ddots \\ \tilde{l}_{n1} & \cdots & \tilde{l}_{nn} \end{pmatrix}
```

based on the relationship $$\tilde{L} \cdot \tilde{L}^T = A$$. The following algorithm produces the Cholesky factor.

Visible text: based on the relationship . The following algorithm produces the Cholesky factor.

## Cholesky Algorithm

Given a positive definite matrix $$A \in \mathbb{R}^{n \times n}$$.

Visible text: Given a positive definite matrix .

Component: MathContainer
Children:

```math
\tilde{l}_{11} := \sqrt{a_{11}}
```

```math
\tilde{l}_{j1} := \frac{a_{j1}}{\tilde{l}_{11}}, \quad j = 2, \ldots, n
```

For $$i = 2, \ldots, n$$:

Visible text: For :

Component: MathContainer
Children:

```math
\tilde{l}_{ii} := \sqrt{a_{ii} - \tilde{l}_{i1}^2 - \tilde{l}_{i2}^2 - \ldots - \tilde{l}_{i,i-1}^2}
```

```math
\tilde{l}_{ji} := \tilde{l}_{ii}^{-1} \cdot \left( a_{ji} - \tilde{l}_{j1}\tilde{l}_{i1} - \tilde{l}_{j2}\tilde{l}_{i2} - \ldots - \tilde{l}_{j,i-1}\tilde{l}_{i,i-1} \right)
```

for $$j = i + 1, \ldots, n$$.

Visible text: for .

After running this algorithm, we will obtain the Cholesky factor which is a lower triangular matrix:

```math
\tilde{L} = \begin{pmatrix} \tilde{l}_{11} & 0 \\ \vdots & \ddots \\ \tilde{l}_{n1} & \cdots & \tilde{l}_{nn} \end{pmatrix}
```

## Cholesky Algorithm Complexity

The Cholesky algorithm for computing the Cholesky factor $$\tilde{L}$$ from $$A \in \mathbb{R}^{n \times n}$$ requires:

Visible text: The Cholesky algorithm for computing the Cholesky factor from requires:

```math
\frac{1}{6}n^3 + O(n^2)
```

arithmetic operations.

This is half the number of operations required to compute LU decomposition, because the use of symmetry allows us to perform computations without row swapping in a different order.