Cholesky Decomposition

What Cholesky Decomposition Is

Cholesky Notation

Existence: Symmetric Positive Definite Matrices

The Algorithm

Solving Systems with Cholesky

Computational Cost

No Pivoting Needed

Cholesky as a Positive Definiteness Test

Where Cholesky Appears

Cholesky and LU: The Relationship

The Semi-Definite and Rank-Deficient Case

Summary: Matrix Property and Cholesky Outcome

Cholesky Decomposition FAQ

The Square Root of a Symmetric Positive Definite Matrix

The Cholesky decomposition factors a symmetric positive definite matrix as A = LLᵀ, where L is lower triangular with positive diagonal entries. It exploits symmetry to achieve half the cost of LU, requires no pivoting, and doubles as a positive definiteness test. It is the fastest direct solver for the class of matrices that appears most often in optimization, statistics, and simulation.

What Cholesky Decomposition Is

The Cholesky decomposition writes a symmetric positive definite matrix

A

Cholesky Decomposition

A = LL^T

Cholesky decomposition →

where

L

is lower triangular with strictly positive diagonal entries. The matrix

L

is the Cholesky factor — the matrix "square root" of

A

in the sense that

A

is reconstructed by multiplying

L

by its own transpose.

The factorization is unique: for a given symmetric positive definite

A

, there is exactly one lower triangular

L

with positive diagonal satisfying

A = LL^T

. The convention can also be written

A = R^TR

with

R = L^T

upper triangular — the choice between lower and upper is a matter of convention.

Cholesky Notation

Notation

Cholesky Notation

One letter does the work of two, a word that sounds like a claim about entries is a claim about something else entirely, and a set of quotation marks marks the one place the wording is loose.

The habit of naming a factorisation by its factors is described at the singular value decomposition, and the unit diagonal, the multiplier entries and the one-sided permutation

PA = LU

at LU. Transpose notation itself belongs to matrix operations.

A = LL^{T}

A equals L times L transpose

Every other factorisation on this site names its factors with separate letters. Here there is one factor, written twice, and the second appearance is fully determined by the first. That is the notation carrying a fact:

LL^{T}

comes out symmetric no matter what

L

is, so the shape of the equation already restricts which matrices can appear on the left.

CasesOnly the lower triangle of

L

is ever stored. The transposed copy is the same array of numbers read in the other direction, which is where the halved storage comes from.

Also writtenThe upper-first spelling

A = R^{T}R

with

R = L^{T}

is the identical factorisation, and both are called the Cholesky decomposition. Which one a library returns is a convention, not a result.

Do not confuseReading the second factor as an independent unknown to be found. There is nothing to solve for beyond

L

— the algorithm produces one triangular matrix and the equation supplies the rest.

Same glyph elsewhere

L

is also the lower factor at LU, where it is unit lower triangular and its partner

U

is independent. The two

L

matrices of one symmetric

A

are different matrices.

\mathbf{x}^{T}A\mathbf{x} > 0 \quad \text{for all } \mathbf{x} \neq \mathbf{0}

x transpose A x is greater than zero for every nonzero vector x

The sandwich collapses to a single number: a row times a matrix times a column leaves a scalar, not a matrix. Positive in the name positive definite describes those numbers and nothing else. Definite carries the strictness — every nonzero

\mathbf{x}

, with no exceptions allowed.

CasesSemi-definite weakens

>

\geq

, admitting vectors the form sends to zero. Indefinite means both signs occur. Each weakening changes exactly one symbol and changes which factorisation exists.

Also writtenCompressed to

A \succ 0

, with the curved comparison sign chosen precisely so it cannot be read entrywise;

A \succeq 0

is the semi-definite case. Plain

A > 0

appears too and is ambiguous for that reason.

Do not confuseTaking positive to describe the entries of

A

. The worked example on this page is positive definite and contains

-2

and

-1

; a matrix whose entries are all positive need not be positive definite. The two properties are unrelated.

LL^{T} = A, \qquad LL \neq A

L times L transpose is A, but L times L is not

L

is described as a matrix square root, and the quotation marks around that phrase are doing real work. A square root normally multiplies by itself; this one multiplies by its transpose.

LL

is again lower triangular and cannot equal a full symmetric

A

CasesA genuine matrix square root exists: the unique symmetric positive definite

S

with

SS = A

, built from the eigenvalues. It is a different matrix from

L

—

S

is symmetric,

L

is triangular — and it costs far more to compute.

Also writtenThe true root is written

A^{1/2}

. The Cholesky factor is written

L

and should not inherit that exponent.

Do not confuseWriting

A^{1/2}

for the Cholesky factor. Both reproduce

A

through a product, and they are not the same matrix; substituting one for the other silently changes any result that depends on symmetry.

PAP^{T} = LL^{T}

P A P transpose equals L L transpose

P

stands on both sides because one side alone would break the symmetry the method depends on. Multiplying on the left reorders the rows; multiplying by

P^{T}

on the right applies the same reordering to the columns, so an entry and its mirror image move together and the result is still symmetric.

CasesSince

P

is a permutation,

P^{T} = P^{-1}

, so

PAP^{T}

is similar to

A

: the eigenvalues are untouched, and with them positive definiteness. Reordering is safe here in a way that is not obvious from the symbols.

Also writtenWritten

P^{T}AP

when the permutation is defined in the opposite direction, which describes the same reordering with

P

replaced by its inverse.

Do not confuseThe one-sided

PA = LU

at LU. There the swaps act on rows only, because nothing about

LU

requires symmetry; copying that form here would produce a matrix with no Cholesky factorisation at all.

A = LDL^{T}, \qquad L_{\text{Chol}} = L_UD^{1/2}

A equals L D L transpose, and the Cholesky factor is the unit lower triangular L times the square root of D

The two factorisations differ only in whether the diagonal is carried separately. In

LDL^{T}

the triangular factor has ones on its diagonal and

D

holds the positive numbers; the Cholesky factor absorbs

\sqrt{D}

and gives up the ones.

Cases

D^{1/2}

means the diagonal matrix of square roots of the entries. For a diagonal matrix that happens to agree with the genuine matrix square root, which is why the exponent passes here without comment and would not for a general matrix.

Also written

LDL^{T}

is the square-root-free variant, computing

D

and the unit factor separately. It survives some semi-definite matrices that break the standard algorithm.

Do not confuseThe two lower triangular factors of one

A

. They differ by a diagonal scaling and sources write

L

for both, so a factor taken from one formula and used in the other is wrong by exactly

D^{1/2}

Same glyph elsewhere

D

holds eigenvalues at diagonalization and pivots here. Both are diagonal matrices of positive numbers for a positive definite

A

, and they are not the same numbers.

All linear algebra symbols →↑ Matrix decompositions

Existence: Symmetric Positive Definite Matrices

The Cholesky factorization exists if and only if

A

is symmetric and positive definite. Symmetry means

A = A^T

. Positive definiteness means

\mathbf{x}^TA\mathbf{x} > 0

for every nonzero vector

\mathbf{x}

.

Several equivalent conditions characterize positive definiteness: all eigenvalues of

A

are strictly positive; all leading principal minors (the determinants of the upper-left

k \times k

submatrices) are positive; all pivots in Gaussian elimination (without pivoting) are positive.

If either symmetry or positive definiteness fails, the Cholesky algorithm breaks down. A non-symmetric matrix has no

LL^T

form. A symmetric matrix that is positive semi-definite (some eigenvalue is zero) produces a zero on the diagonal of

L

. An indefinite matrix (eigenvalues of both signs) produces a negative number under the square root, halting the algorithm.

These equivalent characterizations differ in computational cost and in when each is the practical tool of choice.

Download

PNGRaster · 2×PDFPrint quality

Decompositions · positive definiteness

Four criteria, four prices

All four decide the same question and any of them could serve as the definition. What separates them is cost — from not computable at all to cheaper than anything else on the page.

4criteria

Type	Condition	condition	cost	use it when
Not a computation
The definition§ 2	the statement itself	$\mathbf{x}^{\mathsf{T}}A\mathbf{x} > 0$ for every $\mathbf{x} \neq \mathbf{0}$	not directly testable	proofs and derivations
Computable, expensive
Eigenvalue signs§ 2	all $\lambda_i > 0$	every eigenvalue strictly positive	$O(n^3)$ , iterative	the eigenvalues are wanted anyway
Leading principal minors§ 2	every upper-left $k \times k$ determinant $> 0$	$\det A_k > 0$ for $k = 1, \ldots, n$	$n$ determinants	small or symbolic matrices
Computable, cheapest
Cholesky attempt§ 7	the algorithm runs to completion	no negative under a square root	$\tfrac{1}{3}n^3$ , terminating	whenever the answer is needed

They are equivalent, so the choice is purely practical: the definition for proving, the eigenvalues when they are wanted anyway, the minors for small symbolic matrices, and Cholesky whenever the answer is actually needed. That the cheapest test also produces a useful factorization is what makes it the standard one.

Four criteria, four prices·/linear-algebra/decompositions/choleskyLearn Math Class

Reading down the cost column is the argument for the last row. The definition cannot be evaluated at all, being quantified over infinitely many vectors; the eigenvalue test converges rather than terminating and returns numbers that must then be compared against zero; the minors need

n

determinants. Cholesky settles the question in

\tfrac{1}{3}n^3

operations, terminates, and hands back the factorization when the answer is yes — so the test is free whenever the answer was the one you wanted.

The Algorithm

The Cholesky factor

L

is computed column by column, from left to right.

For column

j

, the diagonal entry is

Cholesky Diagonal Formula

l_{jj} = \sqrt{a_{jj} - \sum_{k=1}^{j-1} l_{jk}^2}

Cholesky diagonal formula →

and the sub-diagonal entries (for

i > j

) are

Cholesky Off-Diagonal Formula

l_{ij} = \frac{1}{l_{jj}}\left(a_{ij} - \sum_{k=1}^{j-1} l_{ik}l_{jk}\right)

Cholesky off diagonal formula →

The square root in the diagonal formula is always real and positive because positive definiteness guarantees that the expression under the root is strictly positive at every step.

Worked Example

For

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

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

l_{21} = 2/2 = 1

l_{31} = -2/2 = -1

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

l_{32} = (1 - (-1)(1))/2 = 2/2 = 1

l_{33} = \sqrt{6 - (-1)^2 - 1^2} = \sqrt{4} = 2

L = \begin{pmatrix} 2 & 0 & 0 \\ 1 & 2 & 0 \\ -1 & 1 & 2 \end{pmatrix}

Verification:

LL^T = \begin{pmatrix} 4 & 2 & -2 \\ 2 & 5 & 1 \\ -2 & 1 & 6 \end{pmatrix} = A

A diagonal entry taken as a square root

Each diagonal entry of the factor is the square root of what is left after the entries already computed in that row have been subtracted off. The whole algorithm alternates between these roots and simple divisions, and it touches only half the matrix because symmetry makes the other half redundant. Run it entry by entry on the Cholesky decomposition visualizer.

Working on half the matrix is what makes this roughly twice as fast as the LU factorisation it specialises.

Solving Systems with Cholesky

Given

A = LL^T

, the system

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

is solved in two steps:

Forward substitution: solve

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

for

\mathbf{y}

. Cost:

O(n^2)

.

Back substitution: solve

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

for

\mathbf{x}

. Cost:

O(n^2)

.

The structure is identical to LU, but only one triangular factor needs to be stored. The other is its transpose, which costs nothing extra — the same array of numbers is read in reverse order.

Computational Cost

The Cholesky factorization requires roughly

\frac{1}{3}n^3

arithmetic operations — exactly half the cost of LU factorization (

\frac{2}{3}n^3

). The saving comes from symmetry: the lower triangle of

A

determines the upper triangle (

a_{ij} = a_{ji}

), so only half the entries need processing.

Each triangular solve costs

O(n^2)

. For a single system, the total is

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

. For

k

systems sharing the same coefficient matrix, the cost is

\frac{1}{3}n^3 + 2kn^2

.

For large symmetric positive definite systems, Cholesky is the fastest direct solver available. It is roughly twice as fast as LU and requires roughly half the storage (only the lower triangle of

L

No Pivoting Needed

Unlike LU, the Cholesky algorithm never requires row swaps. Positive definiteness guarantees that the quantity under the square root is strictly positive at every step — no zero or negative pivots can occur.

This makes the algorithm simpler (no permutation matrix to track), more stable (no near-zero pivots to amplify errors), and more predictable (the algorithm either runs to completion or breaks down, with no ambiguity).

If the algorithm encounters a non-positive value under the square root, the matrix is not positive definite. The breakdown happens at the first index

j

where the leading

j \times j

principal submatrix fails to be positive definite. This makes Cholesky an efficient positive definiteness test: attempt the factorization and check whether it succeeds.

Cholesky as a Positive Definiteness Test

The Cholesky algorithm tests positive definiteness as a side effect of factoring. If

A = LL^T

completes with all diagonal entries of

L

strictly positive,

A

is positive definite. If the algorithm breaks down at any step,

A

is not positive definite.

This is often more practical than computing all eigenvalues (also

O(n^3)

but with a larger constant) or checking all leading principal minors (which requires

n

determinant computations).

The test is binary: the factorization either succeeds or fails. When it succeeds,

L

is available for immediate use in system solving. When it fails, the index at which it breaks indicates which leading submatrix is the first to lose positive definiteness.

A negative value under the square root

The quantity about to be square-rooted has come out negative, and the algorithm stops. That failure is not a numerical accident: it happens precisely when the matrix is not positive definite, which makes attempting the decomposition the standard test for the property. Feed in a matrix that fails on the Cholesky decomposition visualizer.

Testing by attempting the factorisation is cheaper than computing eigenvalues and gives a definite answer either way.

Where Cholesky Appears

Symmetric positive definite matrices appear throughout applied mathematics, and Cholesky is the default solver for all of them.

The normal equations

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

produce a symmetric positive definite matrix

A^TA

(when

A

has full column rank). Cholesky on

A^TA

solves least squares, though QR is preferred for numerical stability.

Covariance matrices in statistics are symmetric positive semi-definite (positive definite when no variable is a linear combination of the others). Cholesky is used to sample from multivariate normal distributions: if

\Sigma = LL^T

, then

L\mathbf{z}

(with

\mathbf{z}

standard normal) has distribution

\mathcal{N}(\mathbf{0}, \Sigma)

.

Stiffness matrices in finite element analysis are symmetric positive definite. Newton's method in optimization solves

H\mathbf{d} = -\nabla f

where

H

(the Hessian) is positive definite at a strict local minimum. In both cases, Cholesky is the standard solver.

Cholesky and LU: The Relationship

For a symmetric positive definite matrix, LU factorization without pivoting always succeeds and produces

A = L_U D L_U^T

, where

L_U

is unit lower triangular and

D

is diagonal with positive entries. This is the

LDL^T

decomposition.

The Cholesky factor is

L_{\text{Chol}} = L_U D^{1/2}

— the unit lower triangular factor with

\sqrt{D}

absorbed into it. Equivalently,

A = (L_U D^{1/2})(L_U D^{1/2})^T = LL^T

.

Cholesky is the symmetric-positive-definite specialization of LU. It exploits

A = A^T

to halve the work and the storage, and it exploits positive definiteness to eliminate the need for pivoting. The

LDL^T

variant avoids square roots entirely (computing

D

and

L_U

separately) and is sometimes preferred when the square roots are expensive or when the matrix is only positive semi-definite.

The Semi-Definite and Rank-Deficient Case

A symmetric positive semi-definite matrix (

\mathbf{x}^TA\mathbf{x} \geq 0

with equality for some nonzero

\mathbf{x}

) has at least one zero eigenvalue. The standard Cholesky factorization breaks down when it encounters the corresponding zero diagonal entry.

Pivoted Cholesky handles this case:

PAP^T = LL^T

with a permutation matrix

P

and

L

possibly having some zero diagonal entries. The permutation reorders the rows and columns to push the rank deficiency to the end.

In practice, numerical near-singularity — eigenvalues very close to zero but not exactly zero — is more common than exact singularity. A condition-number-based threshold determines which eigenvalues are treated as zero. Adding a small regularization

\epsilon I

A

(making it

A + \epsilon I

, which is positive definite for any

\epsilon > 0

) is a common remedy that restores the standard Cholesky factorization at the cost of a controlled perturbation.

Summary: Matrix Property and Cholesky Outcome

The behavior of the Cholesky algorithm depends entirely on what kind of matrix it is asked to factor — positive definite, positive semi-definite, indefinite, non-symmetric, or merely near-singular. The table below collects each scenario, what the algorithm does in each case, and the standard remedy when the straightforward

A = LL^T

form does not apply. The "positive semi-definite" row links back to the pivoted-Cholesky treatment above.

Read the table below as a diagnostic rather than a list of caveats. Cholesky is unusual among algorithms in that its failure modes are informative: it does not merely stop, it stops in a way that identifies what is wrong with the matrix. The split is between the cases that run to completion and the cases where the halt itself is the answer.

Download

PNGRaster · 2×PDFPrint quality

Decompositions · Cholesky

What the algorithm does with each matrix

The algorithm is also a test. Feed it a matrix and how it terminates classifies the matrix — completion means positive definite, and each way of failing identifies a different reason.

5cases

The algorithm completes2

Symmetric positive definite§ 2

all

\lambda_i > 0

A = LL^{\mathsf{T}}

, all

\ell_{ii} > 0

The intended case. Every square root is taken of a strictly positive number, the diagonal of

L

comes out positive, and the factorization is unique. Half the cost of LU because symmetry means only one triangle is computed.

Near-singular but definite§ 7

smallest

\lambda

near zero

runs;

\ell_{ii}

very small

Completes without complaint while the accuracy quietly degrades — small pivots amplify rounding into

L

. The failure is silent, so the smallest diagonal entry is worth monitoring; adding

\varepsilon I

regularizes at the cost of solving a slightly different problem.

The algorithm halts — and the halt is the answer3

Positive semi-definite§ 10

some

\lambda_i = 0

zero appears on the diagonal of

L

Rank-deficient rather than wrong. Pivoted Cholesky,

P^{\mathsf{T}}AP = LL^{\mathsf{T}}

, handles it by reordering so the zeros arrive last — the factorization exists but is no longer unique.

Symmetric indefinite§ 7

some

\lambda_i < 0

negative under the square root

No real

L

exists, and the algorithm discovers this the moment it tries. Use

LDL^{\mathsf{T}}

, which permits negative entries in

D

and so handles any symmetric matrix — at the price of no longer testing definiteness.

Not symmetric§ 9

fails before it starts

A = LL^{\mathsf{T}}

is impossible

Any product

LL^{\mathsf{T}}

is symmetric by construction, so a non-symmetric

A

has no such factorization whatever its eigenvalues are. This is a precondition rather than an outcome — check symmetry first and use LU if it fails.

This is why Cholesky is the standard positive-definiteness test. Computing eigenvalues to check they are all positive costs

O(n^3)

with an iterative method and gives approximate answers; running Cholesky costs

\tfrac{1}{3}n^3

, terminates in finitely many steps, and answers exactly — with the factorization in hand as a byproduct when the answer is yes.

What the algorithm does with each matrix·/linear-algebra/decompositions/choleskyLearn Math Class

That property is what makes it the standard definiteness test. The alternative is computing every eigenvalue and checking the signs, which costs more, converges iteratively rather than terminating, and returns approximations that then have to be judged against zero. Cholesky answers in

\tfrac{1}{3}n^3

operations, finishes in a fixed number of steps, and hands back the factorization as well when the answer is yes.

One case deserves separate attention because it does not announce itself. A matrix that is positive definite but nearly singular runs to completion — no error, no halt — while the small pivots quietly amplify rounding error through

L

. The result looks like a successful factorization and is not a reliable one, which is why the smallest diagonal entry of

L

is worth reading rather than assuming.

Cholesky Decomposition FAQ

Does positive definite mean all the entries are positive?

No, the two properties are unrelated. Positive definiteness is a statement about the quadratic form

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

being positive for every nonzero

\mathbf{x}

, not about the numbers in the array. A positive definite matrix can contain negative entries, and a matrix of entirely positive entries need not be positive definite.Read more →

Is the Cholesky factor the same as the matrix square root?

No, though both reproduce

A

through a product. A genuine square root exists as the unique symmetric positive definite

S

with

SS = A

, built from the eigenvalues, whereas the Cholesky factor

L

is triangular. Writing

A^{1/2}

for

L

silently changes any result that depends on symmetry, and

S

costs far more to compute.Read more →

Why is the pivoting written $PAP^{T}$ here rather than $PA$ ?

Because symmetry has to survive. The one-sided form used for LU swaps rows only, which destroys the symmetry Cholesky depends on and can leave a matrix with no factorisation at all. Applying the permutation on both sides reorders rows and columns together, and since

P^{T} = P^{-1}

the result is similar to

A

, preserving eigenvalues and definiteness.Read more →

Cholesky Decomposition

The Square Root of a Symmetric Positive Definite Matrix

What Cholesky Decomposition Is

Cholesky Notation

Cholesky Notation

Existence: Symmetric Positive Definite Matrices

Four criteria, four prices

The Algorithm

Worked Example

Solving Systems with Cholesky

Computational Cost

No Pivoting Needed

Cholesky as a Positive Definiteness Test

Where Cholesky Appears

Cholesky and LU: The Relationship

The Semi-Definite and Rank-Deficient Case

Summary: Matrix Property and Cholesky Outcome

What the algorithm does with each matrix

Cholesky Decomposition FAQ

Does positive definite mean all the entries are positive?

Is the Cholesky factor the same as the matrix square root?

Why is the pivoting written PAPTPAP^{T}PAPT here rather than PAPAPA?

Why is the pivoting written $PAP^{T}$ here rather than $PA$ ?