What is the Cholesky decomposition?

The Cholesky decomposition writes a symmetric positive definite matrix A as L times L transpose, where L is lower triangular with a positive diagonal. It is a matrix version of a square root, and it is the specialization of the LU decomposition to symmetric positive definite matrices: only one triangular factor is computed, the other is its transpose, and no pivoting is needed.

How do you compute the Cholesky factor?

Column by column. The diagonal entry of column j is the square root of the diagonal entry of A minus the squares of the entries already computed in row j of L. Each entry below it is the corresponding entry of A minus the products of the already computed entries in its row and in row j, divided by the diagonal entry just found. Every quantity needed is available when it is needed if the columns are done left to right.

When does the Cholesky decomposition fail?

It fails if A is not symmetric, because L times L transpose is always symmetric, or if A is symmetric but not positive definite, in which case some diagonal step demands the square root of a non-positive number. The second failure is informative: a symmetric matrix is positive definite exactly when the factorization runs to completion with all radicands positive, which makes Cholesky the standard practical test.

What is the difference between Cholesky and LU?

LU works for any square matrix and computes two different triangular factors, with row swaps when a pivot is zero. Cholesky requires symmetry and positive definiteness, computes one factor and uses its transpose as the other, never needs pivoting, and costs about half as much. For a symmetric positive definite matrix the two are related: the pivots of LU are the squares of the diagonal entries of the Cholesky factor.

What is the Cholesky decomposition used for?

Solving symmetric positive definite systems, which arise from least squares normal equations, stiffness and conductance matrices in engineering, Hessians in optimization, and covariance matrices in statistics. It is also used to generate correlated random samples, by multiplying independent samples by the factor L, and to test whether a symmetric matrix is positive definite.

Cholesky Decomposition Visualizer | A = L Lᵀ Step by Step

Key Terms

Cholesky factorization —

A = LL^T

with

L

lower triangular and a positive diagonal; exists exactly for symmetric positive definite

A

.

Symmetric —

A^T = A

; every entry equals its mirror image across the diagonal.

Positive definite —

\mathbf{x}^T A \mathbf{x} > 0

for every non-zero

\mathbf{x}

; equivalently all eigenvalues positive, equivalently all leading principal minors positive, equivalently Cholesky succeeds.

Diagonal entry —

\ell_{j,j} = \sqrt{a_{j,j} - \sum_{k<j} \ell_{j,k}^2}

, a square root of what is left of

a_{j,j}

after the earlier columns are accounted for.

Below the diagonal —

\ell_{i,j} = \left(a_{i,j} - \sum_{k<j} \ell_{i,k}\ell_{j,k}\right) / \ell_{j,j}

.

Radicand — the number under each square root; the factorization exists exactly when all of them are positive.

Matrix square root — the sense in which

L

is one:

A = LL^T

as a number is

a = \ell \cdot \ell

.

$LDL^T$ form — the variant with unit diagonal

L

and a diagonal

D

, which avoids square roots.

Getting Started with the Visualizer

Choose a matrix, then watch

L

fill column by column while its transpose fills alongside.

• Use the Preset pills for six matrices: a classic

3 \times 3

with an integer factor, a

2 \times 2

, a

4 \times 4

Pascal matrix whose factor is the Pascal triangle, one whose square roots do not simplify, one that is symmetric but not positive definite, and one that is not symmetric
• Use the Size stepper for

2 \times 2

up to

4 \times 4

• Edit any entry; edits are mirrored across the diagonal so the matrix stays symmetric, since an unsymmetric matrix has no Cholesky factorization
• Press Shuffle for a random symmetric positive definite matrix, built as

BB^T + I

so it is guaranteed to factor
• Hover the ? icon for a reminder of what the factorization is and why it doubles as a test
• Press play or step manually; the step log on the right lists every entry computed

Two presets stop early on purpose. The not-symmetric one stops before any arithmetic; the not-positive-definite one runs until a square root of a negative number is demanded and stops there with the explanation.

How the Factorization Runs

The visualizer computes

L

one column at a time, top to bottom within each column.

• Symmetry check — if any entry differs from its mirror image, the run stops: no

LL^T

can equal an unsymmetric matrix
• Diagonal —

\ell_{j,j}

is the square root of

a_{j,j}

minus the squares of the entries already in row

j

of

L

; if that radicand is not positive the run stops, because

A

is not positive definite
• Below the diagonal — each

\ell_{i,j}

is

a_{i,j}

minus the products of the entries already in rows

i

and

j

, divided by

\ell_{j,j}

• Mirror — every entry of

L

appears at once in

L^T

, drawn on the right
• Done —

LL^T = A

, the determinant is the product of the squared diagonal, and the run reports that positive definiteness has been proved

The formulas come from writing out

LL^T = A

entry by entry. Entry

(i, j)

of

LL^T

is

\sum_k \ell_{i,k}\ell_{j,k}

, and since

L

is lower triangular the sum stops at

k = \min(i, j)

; solving that equation for the last term gives the two rules.

The Opening Scene: L and Its Transpose

The player opens with

A

on the left and two empty triangles on the right:

L

with its zeros above the diagonal already drawn, and

L^T

with its zeros below. At the default preset

A

is the classic

3 \times 3

.

Nothing is computed yet. What the scene establishes is that there is only one factor to find: the second is the mirror image of the first.

Opening scene, frozen

A on the left and two empty triangles on the right: L with its zeros above the diagonal drawn, L^T with its zeros below. One factor to find; the other is its mirror image.

That single factor is the whole economy of the method, and it is possible only because

A

is symmetric. A product

LL^T

is symmetric whatever

L

is, so an unsymmetric

A

cannot equal one; the tool checks this before doing anything, and the not-symmetric preset stops here.

Symmetry is necessary but not sufficient. The second condition, positive definiteness, is not checked up front; it reveals itself during the run, in the sign of each radicand.

A Diagonal Entry

Each column begins with its diagonal entry, a square root:

\ell_{j,j} = \sqrt{a_{j,j} - \sum_{k<j} \ell_{j,k}^2}

, the diagonal entry of

A

with the squares of the earlier entries in that row of

L

subtracted.

The frozen picture below is the second diagonal entry of the classic preset:

\ell_{2,2} = \sqrt{5 - 1^2} = 2

, with the subtracted entry

\ell_{2,1}

highlighted and the value mirrored into

L^T

.

Second diagonal entry, frozen

ℓ_2,2 = √(5 − 1²) = 2, with the subtracted entry ℓ_2,1 highlighted and the value mirrored into L^T. The radicand is the pivot LU would find here.

The subtraction is what makes each column depend on the ones before it. The entry

a_{2,2}

is

\ell_{2,1}^2 + \ell_{2,2}^2

by the rule for

LL^T

, so

\ell_{2,2}^2

is what remains once the first column's contribution is removed.

The radicand is the pivot that LU would have found at this position, and its sign is the test. A positive radicand means the leading principal minor through this position is positive; the sequence of positive radicands, one per column, is exactly the statement that

A

is positive definite.

An Entry Below the Diagonal

Below each diagonal entry, the entries of the column are divisions:

\ell_{i,j} = (a_{i,j} - \sum_{k<j} \ell_{i,k}\ell_{j,k}) / \ell_{j,j}

, the entry of

A

minus the products of earlier entries in rows

i

and

j

, divided by the diagonal entry just found.

The frozen picture below is the last such entry of the classic preset:

\ell_{3,2} = (3 - 1 \cdot 1) / 2 = 1

, with the divisor and the subtracted entries highlighted.

Last off-diagonal entry, frozen

ℓ_3,2 = (3 − 1·1) / 2 = 1: the entry of A minus the products of earlier entries in rows 3 and 2, divided by the diagonal entry just found.

The pattern is the row-times-row rule for

LL^T

read backwards. Entry

(3, 2)

of the product is row

3

of

L

dotted with row

2

of

L

, which is

\ell_{3,1}\ell_{2,1} + \ell_{3,2}\ell_{2,2}

; everything except

\ell_{3,2}

is known, so it is solved for.

Every off-diagonal entry divides by a diagonal entry, which is why the diagonal must be computed first and why it must be non-zero. Positive definiteness guarantees both, and it guarantees the division never amplifies error the way a small pivot in LU can.

When the Matrix Is Not Positive Definite

On the not-positive-definite preset the first column succeeds,

\ell_{1,1} = 1

and

\ell_{2,1} = 2

, and the second diagonal entry demands

\sqrt{1 - 2^2} = \sqrt{-3}

. The run stops.

The frozen picture below is that stop: the failed position muted in both

A

and

L

, the first column of

L

already in place.

Not positive definite, frozen

The first column succeeded, then ℓ_2,2 would be √(1 − 4). The run stops with the failed position muted: A is symmetric but indefinite, and that is the verdict, not an error.

This is not a failure of the method but its verdict. A symmetric matrix is positive definite exactly when all of its leading principal minors are positive, and the radicands are those minors divided by the previous ones; a non-positive radicand means a non-positive minor, and the quadratic form

\mathbf{x}^T A \mathbf{x}

takes a non-positive value somewhere.

In practice this is the standard way to test definiteness. It is cheaper than computing eigenvalues, and it either delivers the factorization or the reason none exists.

The Completed Factorization

The final scene shows

L

complete and

L^T

as its mirror image, with

A = LL^T

holding on screen.

The frozen picture below is the classic preset finished:

L

with entries

2, 1, 1, 2, 1, 2

, its transpose beside it, and the diagonal highlighted.

Completed factorization, frozen

L with entries 2, 1, 1, 2, 1, 2 and its transpose beside it: A = LL^T. Every radicand was positive, so A is positive definite; det A = (2·2·2)² = 64.

From here every use is a pair of triangular solves with the same factor:

L\mathbf{y} = \mathbf{b}

forward,

L^T\mathbf{x} = \mathbf{y}

backward. That is the same shape as LU with half the storage and half the factoring cost, and with no pivoting to organize.

Three facts are read off at once: the factorization proves

A

positive definite, the determinant is the product of the squared diagonal, and

L

is the matrix square root that turns independent random variables into correlated ones. For the symmetric positive definite matrices of statistics, optimization and physics, this is the factorization of first resort.

Reading the Scene Player

Each scene shows

A

,

L

and

L^T

with the entry being computed and the entries it depends on.

• In a diagonal scene,

a_{j,j}

is primary, the new

\ell_{j,j}

is accent in both

L

and

L^T

, and the earlier entries of row

j

of

L

that are squared and subtracted are secondary
• In an off-diagonal scene,

a_{i,j}

is primary, the new

\ell_{i,j}

is accent in

L

and mirrored in

L^T

, the divisor

\ell_{j,j}

is primary, and the earlier entries of rows

i

and

j

whose products are subtracted are secondary
• In the stop scenes, the offending entries are highlighted: mismatched pairs for an unsymmetric matrix, the failed diagonal position for a non-positive-definite one
• In the done scene, the diagonal of

L

and

L^T

is accent and the rest secondary
• The known zeros of

L

above the diagonal and of

L^T

below it are drawn in grey from the first scene; irrational entries are shown to three decimals

Choosing a Matrix

The six presets each make a different point.

• Classic $3 \times 3$ — radicands

4

,

4

and

4

, so every square root is

2

and every division is exact;

L

has entries

2, 1, 1, 2, 1, 2

• $2 \times 2$ — one square root, one division, one more square root; the whole pattern in three steps
• Pascal $4 \times 4$ — the symmetric Pascal matrix factors as the lower Pascal triangle times its transpose, a classic identity made visible
• Irrational factor — the tridiagonal matrix with

2

on the diagonal and

1

beside it; the radicands are

2, \tfrac{3}{2}, \tfrac{4}{3}

and the square roots do not simplify
• Not positive definite — symmetric, with

1

on the diagonal and

2

off it; the second radicand is

1 - 4 = -3

and the run stops
• Not symmetric — the run stops before any arithmetic, because

LL^T

is always symmetric

Shuffle never produces a failing matrix; edit an entry by hand to see the tests trip.

What the Cholesky Factorization Is

A symmetric positive definite matrix

A

can be written as

A = LL^T

with

L

lower triangular and its diagonal positive, and with those conditions the factor is unique. It is the matrix version of a square root: for a positive number,

a = \ell \cdot \ell

.

The formulas follow from multiplying out. Entry

(i, j)

of

LL^T

, for

i \geq j

, is

\sum_{k \leq j} \ell_{i,k}\ell_{j,k}

. Setting this equal to

a_{i,j}

and solving for the last term of the sum gives

\ell_{j,j} = \sqrt{a_{j,j} - \sum_{k<j} \ell_{j,k}^2}, \qquad \ell_{i,j} = \frac{a_{i,j} - \sum_{k<j} \ell_{i,k}\ell_{j,k}}{\ell_{j,j}}

Computed column by column, every quantity on the right is already known when it is needed, which is the order the tool follows.

The connection to LU is direct. For a symmetric matrix, Gaussian elimination without pivoting gives

A = LU

with

U = DL^T

, where

D

is the diagonal of pivots; positive definiteness makes every pivot positive, so

D = D^{1/2}D^{1/2}

and

A = (LD^{1/2})(LD^{1/2})^T

. Cholesky's

L

is

LD^{1/2}

, and the pivots of elimination are the squared diagonal entries of the factor. That is also why no pivoting is ever needed: positive definiteness guarantees every pivot is positive before it is reached.

For the full treatment, including the

LDL^T

variant and the equivalent characterizations of positive definiteness, see the Cholesky decomposition theory page.

Key Properties

The factorization inherits the strong properties of its class.

• Existence and uniqueness: exactly for symmetric positive definite

A

, with

L

unique once its diagonal is required positive
• Test for positive definiteness: a symmetric matrix is positive definite exactly when the factorization runs to completion with all radicands positive — the cheapest test in practice
• No pivoting: every pivot is positive, so rows are never swapped and the factorization is numerically stable as it stands
• Half the cost of LU: about

\tfrac{1}{3}n^3

operations, since only one triangular factor is computed
• Determinant:

\det A = (\det L)^2 = \prod_j \ell_{j,j}^2

, always positive
• Solving systems:

A\mathbf{x} = \mathbf{b}

becomes

L\mathbf{y} = \mathbf{b}

then

L^T\mathbf{x} = \mathbf{y}

, two triangular solves sharing one factor
• Relation to LU: the pivots of elimination are

\ell_{j,j}^2

;

L_{\text{Cholesky}} = L_{\text{LU}} D^{1/2}

• Inverse:

A^{-1} = L^{-T}L^{-1}

, and

L^{-1}

is easy because

L

is triangular
• Semidefinite case: if some radicand is exactly zero,

A

is positive semidefinite and a factorization still exists, but it is no longer unique

Why It Matters

Symmetric positive definite matrices are everywhere, and Cholesky is how they are handled.

• Normal equations:

A^TA

in least squares is symmetric positive definite whenever

A

has independent columns, and Cholesky is the classical way to solve

A^TA\mathbf{x} = A^T\mathbf{b}

• Covariance matrices: symmetric positive definite by construction; their Cholesky factors generate correlated random samples from independent ones,

\mathbf{x} = L\mathbf{z}

• Optimization: Hessians at a minimum, Newton steps, and interior-point methods all factor SPD matrices at every iteration
• Physics and engineering: stiffness, mass and conductance matrices are SPD, and finite-element solvers rely on Cholesky or its sparse variants
• Gaussian processes and Kalman filters: kernel matrices and covariance updates are factored this way for both speed and stability
• The definiteness test: asking whether a quadratic form is positive, or a critical point is a minimum, comes down to whether Cholesky succeeds

Worked Example

Take the classic preset,

A = \begin{pmatrix} 4 & 2 & 2 \\ 2 & 5 & 3 \\ 2 & 3 & 6 \end{pmatrix}

Column 1.

\ell_{1,1} = \sqrt{4} = 2

. Then

\ell_{2,1} = 2 / 2 = 1

and

\ell_{3,1} = 2 / 2 = 1

.

Column 2.

\ell_{2,2} = \sqrt{5 - \ell_{2,1}^2} = \sqrt{5 - 1} = 2

. Then

\ell_{3,2} = (3 - \ell_{3,1}\ell_{2,1}) / \ell_{2,2} = (3 - 1) / 2 = 1

.

Column 3.

\ell_{3,3} = \sqrt{6 - \ell_{3,1}^2 - \ell_{3,2}^2} = \sqrt{6 - 1 - 1} = 2

.

L = \begin{pmatrix} 2 & 0 & 0 \\ 1 & 2 & 0 \\ 1 & 1 & 2 \end{pmatrix}, \qquad LL^T = \begin{pmatrix} 4 & 2 & 2 \\ 2 & 5 & 3 \\ 2 & 3 & 6 \end{pmatrix} = A

Check row

3

of

LL^T

against row

3

of

A

:

(1, 1, 2) \cdot (2, 0, 0) = 2

,

(1, 1, 2) \cdot (1, 2, 0) = 3

,

(1, 1, 2) \cdot (1, 1, 2) = 6

. The determinant is

(2 \cdot 2 \cdot 2)^2 = 64

, and every radicand was positive, so

A

is positive definite.

For contrast, the not-positive-definite preset has

\ell_{1,1} = 1

,

\ell_{2,1} = 2

, and then

\ell_{2,2} = \sqrt{1 - 4}

, which does not exist. Its eigenvalues are

3

and

-1

: symmetric, but indefinite.

Common Mistakes

A few mistakes recur.

• Applying it to an unsymmetric matrix —

LL^T

is symmetric no matter what

L

is, so there is nothing to find; use LU
• Skipping the subtraction — from column

2

on, the radicand and the numerators include the contributions of earlier columns; using

a_{j,j}

alone gives wrong entries
• Using the wrong rows in the products —

\ell_{i,j}

subtracts

\sum_k \ell_{i,k}\ell_{j,k}

, entries from row

i

paired with entries from row

j

, over the columns already done
• Taking the negative square root — either sign gives a valid factor, but the convention is positive, and it is what makes

L

unique
• Reading a negative radicand as an arithmetic slip — it may well be the correct conclusion: the matrix is not positive definite
• Confusing positive entries with positive definiteness — a matrix of positive numbers can fail the test, and a matrix with negative off-diagonal entries can pass it

Related Concepts

LU decomposition — the general factorization that Cholesky specializes; the pivots of LU are the squared diagonal of

L

.

Symmetric matrices — the class this applies to, and whose transpose invariance makes one factor enough.

Positive definiteness — the condition, tested by the factorization itself.

Determinant — the product of the squared diagonal, always positive here.

Least squares — the normal equations are the classic SPD system.

Eigenvalues — all positive for an SPD matrix, though Cholesky never computes them.

QR decomposition — the other route to least squares, avoiding

A^TA

altogether.

Matrix square root — the idea Cholesky makes concrete for triangular factors.

Cholesky Decomposition

Step explanations

Key Terms

Getting Started with the Visualizer

How the Factorization Runs

The Opening Scene: L and Its Transpose

A Diagonal Entry

An Entry Below the Diagonal

When the Matrix Is Not Positive Definite

The Completed Factorization

Reading the Scene Player

Choosing a Matrix

What the Cholesky Factorization Is

Key Properties

Why It Matters

Worked Example

Common Mistakes

Related Concepts