Cholesky Decomposition: Algorithm & Uses

What Cholesky Decomposition Is

The Cholesky decomposition writes a symmetric positive definite matrix

A

as

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.

THEOREM

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.

A = LLᵀ, complete

The finished Cholesky factor L, lower triangular with positive diagonal entries, and its mirror image L^T. One triangle is enough to rebuild the whole symmetric matrix: L times its own transpose gives A back. That is why Cholesky costs half of LU — half of the factorization comes free by symmetry. Follow the column-by-column computation on the Cholesky decomposition visualizer.

A symmetric positive definite matrix is exactly one that can be written this way.

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

>

to

\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

THEOREM

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}

.

Pitfall: Skipping the symmetry check

Testing only positivity passes

B = \begin{pmatrix} 4 & 0 \\ 2 & 5 \end{pmatrix}

: its eigenvalues

4, 5

and leading minors

4, 20

are all positive. But

B \neq B^T

, so no

L

exists; the formulas still return an

L

, with

LL^T = \begin{pmatrix} 4 & 2 \\ 2 & 5 \end{pmatrix} \neq B

.

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

.

The Algorithm

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

.

Pitfall: Dropping the subtracted sum

Computing

l_{32} = a_{32}/l_{22} = \frac{1}{2}

leaves out

l_{31}l_{21} = -1

. Entry

(3, 2)

of

LL^T

then comes out

(-1)(1) + \frac{1}{2} \cdot 2 = 0

, not

a_{32} = 1

. With the sum,

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

.

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)

.

Pitfall: Using L in both solves

Solving

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

in the second step solves

L^2\mathbf{x} = \mathbf{b}

. For the worked example with

\mathbf{b} = (0, 6, 7)^T

, so

\mathbf{y} = (0, 3, 2)^T

, it gives

\mathbf{x} = (0, \frac{3}{2}, \frac{1}{4})^T

. Back substitution on

L^T

gives

\mathbf{x} = (0, 1, 1)^T

.

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

THEOREM

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.

Fact: The diagonal of

A

caps every entry of

L

The diagonal of

LL^T = A

reads

a_{ii} = l_{i1}^2 + l_{i2}^2 + \cdots + l_{ii}^2

, a sum of squares, so no entry in row

i

of

L

can exceed

\sqrt{a_{ii}}

in size. The numbers cannot grow out of control, which is why skipping row swaps costs no accuracy.

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.

Positive definiteness does the job that pivoting does in LU: every pivot is positive, so no row ever has to move.

Cholesky as a Positive Definiteness Test

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

THEOREM

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.

Fact: Invented for surveyors' least squares

André-Louis Cholesky, a French artillery officer and surveyor, devised the method by 1910 to solve the normal equations of least-squares adjustments in map-making. He was killed in the First World War in 1918, and a fellow officer published the method in 1924.

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 near a minimum that the second-derivative test confirms. In both cases, Cholesky is the standard solver.

Cholesky and LU: The Relationship

THEOREM

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.

DownloadPNG2×PDF

Before you read

Each form specializes the one below

For a symmetric positive definite matrix, LU without pivoting always succeeds. Absorbing structure step by step leads from LU to Cholesky.

most specializedspecializationmost general

Cholesky

A = LL^T

LDL^T

symmetric positive definite, no pivoting

LUgeneral square matrices

Takeaway

Why specialize

Cholesky exploits

A = A^T

to halve the work and storage, and positive definiteness to remove pivoting. The

LDL^T

form avoids square roots entirely.

From LU to Cholesky·/linear-algebra/decompositions/choleskyLearn Math Class

Cholesky is LU for a symmetric positive definite matrix: half the work, no pivoting, and

\sqrt{D}

folded into

L

.

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

to

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.

Zero eigenvalues stop the plain algorithm and near-zero ones spoil it; pivoting or a small shift

\epsilon I

is the repair.

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

1

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.

2

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

3

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.

4

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.

5

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.

Common Pitfalls

Three mistakes account for many wrong results with the Cholesky decomposition. Each is marked with a box where it happens in the sections above. Here each is worked through in full, with the wrong and the right working side by side.

Skipping the symmetry check

Before factoring, the eigenvalues or the leading principal minors are checked, and when they are positive the matrix is taken to be positive definite. The matrix is never compared with its transpose, although those tests describe positive definiteness only for symmetric matrices.

Wrong working:

B = \begin{pmatrix} 4 & 0 \\ 2 & 5 \end{pmatrix}

is triangular, so its eigenvalues are

4

and

5

, and its leading minors are

4

and

4 \cdot 5 - 0 \cdot 2 = 20

. All are positive, so

B = LL^T

is expected. The formulas read only

b_{11}

,

b_{21}

and

b_{22}

:

l_{11} = \sqrt{4} = 2, \quad l_{21} = 2/2 = 1, \quad l_{22} = \sqrt{5 - 1^2} = 2, \qquad L = \begin{pmatrix} 2 & 0 \\ 1 & 2 \end{pmatrix}

Right working: compare

B

with

B^T

first.

B^T = \begin{pmatrix} 4 & 2 \\ 0 & 5 \end{pmatrix} \neq B

Since

LL^T

is symmetric for every

L

, no Cholesky factor exists. The

L

found above gives

LL^T = \begin{pmatrix} 4 & 2 \\ 2 & 5 \end{pmatrix}

, which differs from

B

in the entry above the diagonal.

Why it happens: the list of equivalent conditions is quoted without its standing assumption that

A

is symmetric. The formulas use only the entries on and below the diagonal, so they run without any warning.

How to check: compare

a_{ij}

with

a_{ji}

before anything else. After factoring, multiply out

LL^T

and compare every entry with

A

, including those above the diagonal.

Dropping the subtracted sum

In the off-diagonal formula, the sum

\sum_{k=1}^{j-1} l_{ik}l_{jk}

is left out once

j > 1

, and the entry is computed as

a_{ij}/l_{jj}

, the way the first column is.

Wrong working: in the worked example,

l_{32} = \frac{a_{32}}{l_{22}} = \frac{1}{2}

Entry

(3, 2)

of

LL^T

is row

3

of

L

times row

2

of

L

:

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

The error spreads:

l_{33} = \sqrt{6 - (-1)^2 - (\frac{1}{2})^2} = \frac{\sqrt{19}}{2} \approx 2.18

instead of

2

.

Right working: subtract the products already available.

l_{32} = \frac{a_{32} - l_{31}l_{21}}{l_{22}} = \frac{1 - (-1)(1)}{2} = 1, \qquad l_{31}l_{21} + l_{32}l_{22} = -1 + 2 = 1 = a_{32}

Why it happens: in the first column the sum is empty, so the first entries are plain divisions, and that pattern is carried over to the later columns.

How to check: rebuild one entry at a time. Entry

(i, j)

of

LL^T

is row

i

of

L

times row

j

of

L

, and it must equal

a_{ij}

.

Using L in both solves

After forward substitution, the second triangular solve is done with

L

again instead of

L^T

. Only

L

is stored, and the array is read in the same order twice.

Wrong working: with the worked example and

\mathbf{b} = (0, 6, 7)^T

, forward substitution gives

\mathbf{y}

:

y_1 = \frac{0}{2} = 0, \quad y_2 = \frac{6 - 1 \cdot 0}{2} = 3, \quad y_3 = \frac{7 - (-1) \cdot 0 - 1 \cdot 3}{2} = 2

Then

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

is solved from the top:

x_1 = 0, \quad x_2 = \frac{3 - 0}{2} = \frac{3}{2}, \quad x_3 = \frac{2 + 0 - \frac{3}{2}}{2} = \frac{1}{4}

and

A(0, \frac{3}{2}, \frac{1}{4})^T = (\frac{5}{2}, \frac{31}{4}, 3)^T \neq \mathbf{b}

. This

\mathbf{x}

solves

L^2\mathbf{x} = \mathbf{b}

.

Right working: solve

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

from the bottom, with

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

.

x_3 = \frac{2}{2} = 1, \quad x_2 = \frac{3 - 1}{2} = 1, \quad x_1 = \frac{0 - 1 + 1}{2} = 0

and

A(0, 1, 1)^T = (0, 6, 7)^T = \mathbf{b}

.

Why it happens: the second factor is not stored as a separate matrix, so it is easy to run the same routine on the same array twice.

How to check: forward substitution starts at the top with

y_1

, back substitution at the bottom with

x_n

. If both solves start at the top,

L

was used twice. Multiplying

A\mathbf{x}

and comparing with

\mathbf{b}

settles it.

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

Common Pitfalls

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$ ?