LU Decomposition: Factorization & Solving

What LU Decomposition Is

Gaussian elimination solves Ax = b — but every new right-hand side b starts the elimination over from the beginning.

When the same matrix

A

meets many different right-hand sides — the same structure under different loads, the same circuit under different voltages — the row operations on

A

are identical every time. Only

\mathbf{b}

changes, yet the whole elimination is repeated.

For A with rows (2, 1), (6, 4), one row operation does all the work: subtract 3 times row 1 from row 2.

piece	rows	where it comes from
A	(2, 1), (6, 4)	the matrix to be eliminated
row operation	row 2 − 3 · row 1	the multiplier 3 clears the 6
U	(2, 1), (0, 1)	the result of elimination: upper triangular
L	(1, 0), (3, 1)	the multiplier 3 kept below a diagonal of ones
L · U	(2, 1), (6, 4)	multiplying back returns A

The multiplier and the result are all that elimination produces — keep both, and A is rebuilt as their product.

Row 1 of

L \cdot U

is

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

; row 2 is

3 \cdot (2, 1) + 1 \cdot (0, 1) = (6, 4)

. The elimination has been stored as two triangular matrices, ready to be reused for any

\mathbf{b}

.

The definition

The LU decomposition writes a square matrix as

A = LU

, with

L

unit lower triangular, holding the elimination multipliers, and

U

upper triangular, the result of elimination.

The LU decomposition writes an

n \times n

matrix

A

as

LU Decomposition

A = LU

Lu decomposition →

where

L

is lower triangular with ones on the diagonal (unit lower triangular) and

U

is upper triangular. The matrix

U

is the row echelon form of

A

, and

L

stores the multipliers that Gaussian elimination used to produce it.

So

A

with rows

(2, 1)

,

(6, 4)

is

LU

with

L

rows

(1, 0)

,

(3, 1)

and

U

rows

(2, 1)

,

(0, 1)

.

LU is elimination saved for reuse.

The factorization captures the entire elimination process in a reusable form. Instead of performing elimination from scratch for every new right-hand side

\mathbf{b}

, the work is done once (producing

L

and

U

) and reused cheaply for each solve.

A = LU, complete

The finished factorization: L below, with ones on its diagonal and the elimination multipliers beneath; U above, the upper triangular result of elimination, with its diagonal — the pivots — marked. Multiplying the two back together returns A. Build it one elimination step at a time on the LU decomposition visualizer.

Everything elimination does is recorded in these two triangles, so it never has to be done twice.

Not every matrix has an LU decomposition without row swaps.

For the matrix with rows

(0, 1)

,

(1, 0)

the first pivot is

0

, so elimination cannot even start. Swapping the rows first fixes it, and the swap is recorded as described in partial pivoting.

The rest of the page covers notation, construction from Gaussian elimination, the structure of L and U, when LU exists without pivoting, partial pivoting, solving systems, the determinant and inverse, a worked 4×4 example, and the computational cost.

LU Notation

Notation

LU Notation

Two letters chosen for what they look like, a diagonal of ones nobody writes down as a choice, and a permutation whose meaning depends entirely on which side of

A

it stands.

The echelon form that

U

turns out to be, and the pivot vocabulary that comes with it, are set out at row echelon form. The row operations themselves, their arrow convention and the augmented bar belong to Gaussian elimination, and the general habit of naming a factorisation by its factors is described at the singular value decomposition.

A = LU

A equals L U — A written as a lower triangular matrix times an upper triangular one

The letters are mnemonic rather than arbitrary:

L

is lower,

U

is upper. That is unusual. Most factorisations pick letters for the role a factor plays, and here they name the shape instead, which is why the equation can be read off without a legend.

CasesThe two factors are not interchangeable.

UL

is a different product describing a different matrix, and the order in

A = LU

is fixed by the elimination that produced it — the lower factor records what was done, the upper factor records what was left.

Also writtenGerman-language texts write

A = LR

, keeping

L

and taking

R

from the word for the right-hand, upper triangle. The three-factor spelling

A = LDU

pulls the pivots out into a diagonal

D

so that both triangular factors carry ones.

Do not confuseTreating

LU

as an expression waiting to be multiplied out. The point of the factorisation is that the pair is kept and reused; multiplying it back to

A

is only ever a check.

Same glyph elsewhereThe letter

U

names the orthogonal left factor at the singular value decomposition, where the clash with upper triangular is set out.

L = \begin{pmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{pmatrix}

L is unit lower triangular — ones along the diagonal, multipliers below it

Unit here refers to the diagonal entries being

1

and to nothing else. The ones are a normalisation that has to be supplied from outside, because

A = LU

on its own does not determine the factors: for any invertible diagonal

D

, the pair

LD

and

D^{-1}U

multiplies to the same

A

. Fixing

L

to carry ones removes the freedom and makes the factorisation unique.

CasesThe three-factor form

A = LDU

makes the choice visible instead of silent, putting the pivots in

D

and leaving both triangular factors with unit diagonals.

Also writtenSome treatments normalise

U

instead, giving

U

the ones and leaving the pivots in

L

. Both conventions produce a correct

A = LU

, and they produce different

L

and

U

.

Do not confuseReading unit as unit length or orthonormal columns, neither of which is claimed. The second misreading is expecting

U

to have ones as well: the diagonal of

U

holds the pivots, and it is their product that gives the determinant.

PA = LU

P A equals L U — permute the rows of A, then factor the result

Which side

P

stands on is the whole content of the line. On the left it multiplies the rows of

A

, and the equation asserts an order of events: the swaps are decided first, and elimination runs on the reordered matrix. The factorisation belongs to

PA

, not to

A

.

CasesRearranged forms say the same thing: since

P

is a permutation,

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

, so

A = P^{T}LU

. Numerical libraries commonly return the transposed permutation and report

A = PLU

— the same letter naming the inverse matrix, which is worth checking before mixing output from two sources.

Also writtenThe row swaps are sometimes reported as a list of indices rather than a matrix, which stores the same information without committing to a side.

Do not confuseDropping

P

once the factors are in hand. Solving

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

requires the right-hand side to be permuted too, so forward substitution runs on

P\mathbf{b}

; using

\mathbf{b}

untouched silently solves a system with its rows in the wrong order.

Same glyph elsewhere

P

carries the eigenvectors at diagonalization, where it is an arbitrary invertible matrix rather than a rearrangement of rows.

l_{ij}, \quad i > j

the entry of L in row i, column j, below the diagonal

These entries are a transcript, not a computation on

A

. Each one is the multiplier that cleared position

(i, j)

during forward elimination, so

L

is a record of the procedure and

U

is its result.

CasesThe sign follows subtraction. Subtracting

2

times row

1

from row

2

stores

+2

; adding row

1

to row

3

stores

-1

. The number in

L

therefore reads with the opposite sign to the operation as it is usually spoken.

Also writtenThe multipliers are written

m_{ij}

while elimination is being described and

l_{ij}

once they have been placed in the matrix — two names for one number at two moments.

Do not confuseReading the packed storage as a matrix. Since the ones in

L

and the zeros in

U

carry no information, software keeps both factors in one

n \times n

array with the multipliers in the lower triangle and

U

in the upper. Printed, it looks like a single matrix and is neither factor.

All linear algebra symbols →↑ Matrix decompositions

DownloadPNG2×PDF

Notation · Cheat sheet

Decomposition Notation at a Glance

The marks from the notation cards across the decomposition pages: how each is read and what it means. Every group links to the full card on its page.

LU decompositionThis page

A = LU

A equals L U

Lower triangular times upper triangular.

PA = LU

permute, then factor

P

on the left reorders the rows of

A

.

l_{ij}, \; i > j

entries of L below the diagonal

The multipliers used in elimination; ones on the diagonal.

QR decomposition

A = QR

A equals Q R

Orthonormal columns times upper triangular;

Q_1R_1

is the thin form.

Q^{T}Q = I

but not always Q Q transpose

For a thin

Q

,

QQ^{T} \neq I

.

A_{k+1} = R_kQ_k

the QR iteration

Factor, then multiply back in reverse order.

Cholesky decomposition

A = LL^{T}

L times L transpose

One factor, used twice;

LL \neq A

.

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

positive definite

Required for all

\mathbf{x} \neq \mathbf{0}

.

A = LDL^{T}

L D L transpose

The diagonal carried separately; no square roots.

Spectral decomposition

A = QDQ^{T}

Q D Q transpose

For symmetric

A

:

Q^{T}

stands where

Q^{-1}

would be.

\sum \lambda_i\mathbf{q}_i\mathbf{q}_i^{T}

a sum of rank-one terms

The same matrix, written by eigenvalues.

Singular value decomposition

A = U\Sigma V^{T}

U Sigma V transpose

Orthogonal

U

and

V

, diagonal

\Sigma

.

\Sigma

capital sigma

A diagonal matrix here, not a sum.

\sigma_1 \geq \sigma_2 \geq \cdots \geq 0

the singular values

\sigma_1

always means the largest.

Same marks, different job

\Sigma

A diagonal matrix in the SVD; elsewhere the summation sign.

Q

Always orthonormal columns;

Q^{T}

then acts as the inverse.

L

Lower triangular in both LU and Cholesky, but with ones on the diagonal only in LU.

Decomposition symbols table Decompositions

Decomposition Notation at a Glance·/linear-algebra/decompositions/lower-upperLearn Math Class

Construction from Gaussian Elimination

Fact: An astronomer saw the product first

Elimination was in use for centuries before anyone wrote it as a product of two triangular matrices. The Polish astronomer Tadeusz Banachiewicz did so in 1938, and Alan Turing's 1948 paper on rounding errors recast elimination as

A = LDU

.

Gaussian elimination is usually carried out as a list of row operations on an augmented matrix, used once to reach a solution and then set aside. Read as matrix multiplications instead, the same operations turn the procedure into a statement about

A

itself: a product of two triangular matrices.

Forward elimination on

A

applies a sequence of row-addition operations, each represented by an elementary matrix

E_i

. The product

E_k \cdots E_2 E_1 A = U

reduces

A

to upper triangular form.

Rearranging:

A = E_1^{-1} E_2^{-1} \cdots E_k^{-1} U

. Each

E_i

is a lower triangular matrix that adds a multiple of one row to a row below. Its inverse simply negates the multiplier. The product

L = E_1^{-1} E_2^{-1} \cdots E_k^{-1}

is lower triangular, with the multipliers sitting in the sub-diagonal positions.

Worked Example

Construction from Gaussian Elimination

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

Subtract

2

times row

1

from row

2

(multiplier

m_{21} = 2

) and add row

1

to row

3

(multiplier

m_{31} = -1

):

Construction from Gaussian Elimination

\begin{pmatrix} 2 & 1 & -1 \\ 0 & -2 & 4 \\ 0 & 6 & 2 \end{pmatrix}

Add

3

times row

2

to row

3

(multiplier

m_{32} = -3

):

Construction from Gaussian Elimination

U = \begin{pmatrix} 2 & 1 & -1 \\ 0 & -2 & 4 \\ 0 & 0 & 14 \end{pmatrix}

The multipliers fill

L

:

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

.

Verification:

LU = \begin{pmatrix} 2 & 1 & -1 \\ 4 & 0 & 2 \\ -2 & 5 & 3 \end{pmatrix} = A

.

Pitfall: Storing the negated multiplier

Writing

-2

,

1

,

3

below the diagonal because those are the amounts added gives

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

and

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

. The entries of

L

are the multipliers

m_{21} = 2

,

m_{31} = -1

,

m_{32} = -3

.

Reading

L

off the elimination takes no extra arithmetic. Each multiplier is filed at the position of the zero it created:

m_{21}

at

(2, 1)

,

m_{31}

at

(3, 1)

and

m_{32}

at

(3, 2)

. Multiplying

L

by

U

then reverses the row operations one by one, which is why the product rebuilds

A

exactly.

To compute the LU decomposition of your own matrix, use the matrix calculator.

The multiplier stored, not discarded

Ordinary elimination throws away the multiplier once the zero is in place. Here it is kept and written into the lower factor, so L records the elimination and U records the result of it. Nothing extra is computed; the same arithmetic is simply being saved. Follow both factors filling in on the LU decomposition visualizer.

The factorisation is therefore a by-product of elimination rather than a separate algorithm with its own cost.

The Structure of L and U

The lower factor

L

is unit lower triangular: ones on the diagonal and multipliers below. Entry

l_{ij}

(with

i > j

) is the multiplier used to eliminate position

(i, j)

during forward elimination. The diagonal is always ones because no row scaling is performed — only row additions.

The upper factor

U

is the echelon form: pivots on the diagonal, zeros below, and the result of all elimination steps. The diagonal entries of

U

are the pivots, and their product gives the determinant:

\det(A) = \det(L)\det(U) = 1 \cdot u_{11}u_{22}\cdots u_{nn}

.

The factorization stores

L

and

U

compactly. Since

L

has ones on the diagonal (which need not be stored) and

U

has zeros below the diagonal (which need not be stored), both factors fit in a single

n \times n

array: the lower triangle holds the multipliers and the upper triangle holds

U

.

The two factors compare cleanly on the same set of attributes — diagonal, below diagonal, above diagonal, role — as the table below shows.

DownloadPNG2×PDF

Decompositions · LU

What each factor holds

Between them $L$ and $U$ store the whole elimination — $U$ is what was left, $L$ is what was done. Read region by region, neither factor wastes a position.

3factors

Type	Condition	on the diagonal	below it	above it
What the elimination produced
U — upper triangular§ 3	the echelon form of $A$	the pivots — $\prod u_{ii} = \pm\det A$	zeros — what elimination removed	the surviving entries
What the elimination did
L — unit lower triangular§ 3	the multipliers, in position	all ones — not stored	the multiplier $\ell_{ij} = m_{ij}$	zeros
What the pivoting recorded
P — permutation§ 5	the row swaps, if any	ones where no swap occurred	a single one per row	a single one per row

The two triangles are complementary, so both fit in one

n \times n

array with nothing overlapping:

U

on and above the diagonal,

L

strictly below, and the unit diagonal of

L

left implicit because it is known. Storing a factorization therefore costs no more memory than storing

A

did.

What each factor holds·/linear-algebra/decompositions/lower-upperLearn Math Class

The two triangles occupy complementary regions, which is not a coincidence but the reason the factorization is cheap to store.

U

owns the diagonal and everything above it;

L

owns everything strictly below; and the unit diagonal of

L

need not be written down because it is known in advance. Both factors therefore fit into the same

n \times n

array the original matrix occupied, with no position used twice and none left empty.

When LU Exists Without Pivoting

For an invertible matrix

A

, the factorization

A = LU

without row swaps exists if and only if every leading principal submatrix of

A

is nonsingular. The

k

-th leading principal submatrix is the upper-left

k \times k

block of

A

, and its determinant must be nonzero for

k = 1, 2, \dots, n

.

When a zero appears in a pivot position during elimination of an invertible matrix, no row-addition operation can produce a nonzero pivot — a row swap is required. The simple

A = LU

factorization breaks down, and the pivoted version

PA = LU

is needed.

For example,

A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}

has no

LU

factorization without pivoting: the

(1,1)

entry is zero, and no multiple of row

1

can create a nonzero pivot. But after swapping the two rows, elimination proceeds immediately.

Row additions can never turn a zero pivot into a usable one; for an invertible matrix, only a row swap can.

Partial Pivoting: PA = LU

Partial pivoting modifies the elimination process: at each step, the row with the largest absolute value in the current pivot column (among rows at or below the pivot position) is swapped into the pivot position. All row swaps are recorded in a permutation matrix

P

.

The factorization becomes:

PA LU Partial Pivoting

PA = LU

Pa lu partial pivoting →

where

P

is the product of all row-swap permutation matrices. This factorization exists for every invertible matrix — partial pivoting eliminates the restriction on leading principal submatrices.

Pitfall: Choosing the largest signed entry

In a pivot column holding

2

and

-5

, keeping

2

because

2 > -5

gives the multiplier

-5/2

, larger than

1

in size. Partial pivoting compares

|2|

with

|-5|

, swaps the

-5

row up, and the multiplier becomes

2/(-5) = -2/5

.

Partial pivoting also improves numerical stability. Small pivots amplify rounding errors (dividing by a number near zero magnifies imprecision), and selecting the largest available pivot keeps the multipliers in

L

bounded by

1

in absolute value, limiting error accumulation.

In numerical software, LU with partial pivoting is the default — the unpivoted version

A = LU

is a theoretical simplification that is rarely used in practice.

A row swap recorded in the permutation

A zero, or an uncomfortably small number, has appeared where a pivot was needed, so rows have been exchanged and the exchange logged in P. This is why the honest statement of the factorisation is PA = LU: without the permutation there are perfectly ordinary matrices that have no LU at all. Trigger a swap on the LU decomposition visualizer.

In practice pivoting is used even when it is not strictly required, because small pivots damage accuracy long before they reach zero.

Fact: The doubling bound is reached

For the matrix with

1

on the diagonal and in the last column and

-1

everywhere below the diagonal, partial pivoting never swaps, and the last pivot doubles at every step to

2^{n-1}

. At

n = 60

, solving with it in double precision gives answers wrong in the first digit, although the matrix is well conditioned.

Bounding the multipliers is not the same as bounding the entries. Each elimination step replaces an entry by itself minus a multiplier times an entry of the pivot row, and with every multiplier at most

1

in size, the largest entry in the remaining rows can at most double. Over the

n - 1

steps of an

n \times n

factorization, that allows growth by a factor of up to

2^{n-1}

.

Large entries in

U

matter because rounding errors are made relative to the numbers being handled. When the entries grow, the errors committed along the way grow with them, and the computed factors reproduce

PA

less accurately.

Solving Systems with LU

Given

PA = LU

, the system

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

is solved in two steps:

LU Solve Steps

A\mathbf{x} = \mathbf{b} \;\Longleftrightarrow\; \begin{cases} L\mathbf{y} = P\mathbf{b} & (\text{forward sub}) \\ U\mathbf{x} = \mathbf{y} & (\text{back sub}) \end{cases}

Lu solve steps →

Forward substitution: solve

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

for

\mathbf{y}

. Since

L

is lower triangular, this starts at the top and works downward — each equation involves one new unknown plus previously solved values. Cost:

O(n^2)

.

Back substitution: solve

U\mathbf{x} = \mathbf{y}

for

\mathbf{x}

. Since

U

is upper triangular, this starts at the bottom and works upward. Cost:

O(n^2)

.

Pitfall: Forgetting to permute the right-hand side

For

A = \begin{pmatrix} 0 & 2 \\ 3 & 1 \end{pmatrix}

, one swap gives

L = I

and

U = \begin{pmatrix} 3 & 1 \\ 0 & 2 \end{pmatrix}

. Solving with

\mathbf{b} = (2, 4)

instead of

P\mathbf{b}

gives

\mathbf{x} = (0, 2)

, but

A\mathbf{x} = (4, 2)

. With

P\mathbf{b} = (4, 2)

,

\mathbf{x} = (1, 1)

.

The factorization itself costs

\frac{2}{3}n^3

operations. Each subsequent solve costs

O(n^2)

. For

k

systems with the same coefficient matrix but different right-hand sides

\mathbf{b}_1, \dots, \mathbf{b}_k

: factor once at cost

\frac{2}{3}n^3

, then solve

k

times at cost

2kn^2

. When

k

is large, the per-system cost drops to essentially

O(n^2)

— far cheaper than

k

independent eliminations at

\frac{2}{3}n^3

each.

The cubic cost is paid once per matrix; every right-hand side after that costs only two triangular solves.

LU and the Determinant

The determinant of

A

is a free byproduct of the LU factorization. Since

\det(L) = 1

(the diagonal is all ones) and

\det(U) = u_{11}u_{22}\cdots u_{nn}

(the product of the diagonal for a triangular matrix), with pivoting each row swap flips the sign:

Determinant via LU

\det(A) = (-1)^s \prod_{i=1}^{n} u_{ii}

Determinant via lu →

where

s

is the number of row swaps recorded in

P

. Without pivoting (

s = 0

), the sign factor drops and

\det(A) = u_{11}u_{22}\cdots u_{nn}

.

Pitfall: Dropping the sign of the row swaps

For

A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}

, one swap gives

U = I

, and multiplying its pivots alone gives

\det A = 1

. With

s = 1

,

\det A = (-1)^1 \cdot 1 = -1

, which matches

0 \cdot 0 - 1 \cdot 1

.

This makes determinant computation essentially free once LU is available — just multiply the diagonal of

U

and account for the sign. It is far more efficient than cofactor expansion, and it is the method every numerical library uses.

LU and the Inverse

To compute

A^{-1}

, solve

A\mathbf{x}_j = \mathbf{e}_j

for each standard basis vector

\mathbf{e}_j

,

j = 1, \dots, n

. The solutions

\mathbf{x}_1, \dots, \mathbf{x}_n

are the columns of

A^{-1}

.

With LU: factor

A

once (

\frac{2}{3}n^3

), then solve

n

systems (

n \times O(n^2) = O(n^3)

). Total cost: roughly

\frac{8}{3}n^3

counted directly, or

2n^3

when the zeros in the columns of

I

are used — cheaper than

n

independent eliminations.

In practice, computing

A^{-1}

explicitly is rarely the right approach. Solving

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

via LU costs about the same per right-hand side as multiplying

A^{-1}\mathbf{b}

(about

2n^2

each), but it never forms

A^{-1}

, which costs about

2n^3

against

\frac{2}{3}n^3

for the factorization, and it is more numerically stable. The inverse formula is primarily a theoretical tool; for computation, LU solves are preferred.

Worked Example: 4×4 with Pivoting

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

The

(1,1)

entry is zero — a row swap is needed. The largest entry in column

1

is

3

in row

3

. Swap rows

1

and

3

:

Worked Example: 4×4 with Pivoting

\begin{pmatrix} 3 & 1 & 0 & 2 \\ 1 & 0 & 3 & -1 \\ 0 & 2 & 1 & 3 \\ 2 & 3 & 1 & 0 \end{pmatrix}

Eliminate below the

(1,1)

pivot. Multipliers:

m_{21} = 1/3

,

m_{31} = 0

,

m_{41} = 2/3

:

Worked Example: 4×4 with Pivoting

\begin{pmatrix} 3 & 1 & 0 & 2 \\ 0 & -1/3 & 3 & -5/3 \\ 0 & 2 & 1 & 3 \\ 0 & 7/3 & 1 & -4/3 \end{pmatrix}

The largest entry in column

2

below position

(2,2)

is

7/3

in row

4

. Swap rows

2

and

4

. Continue elimination on columns

2

and

3

with the appropriate multipliers.

After completing all steps, the factorization

PA = LU

is assembled with

P

recording all three row swaps (column

3

needs one too, since

22/7 > 1/7

),

L

storing all multipliers, and

U

storing the final upper triangular result. Verification:

LU = PA

.

Computational Cost

The LU factorization of an

n \times n

matrix requires roughly

\frac{2}{3}n^3

arithmetic operations (multiplications and additions). Each triangular solve (forward or back substitution) requires roughly

n^2

operations.

For a single system

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

, LU costs about the same as Gaussian elimination applied directly. The advantage appears with multiple right-hand sides:

k

systems sharing the same

A

cost

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

, versus

\frac{2}{3}kn^3

for

k

independent eliminations.

Compared to alternatives: Cramer's rule costs

O(n \cdot n!)

— absurdly expensive. Explicit inverse computation costs roughly

2n^3

. The Cholesky factorization costs

\frac{1}{3}n^3

but requires symmetry and positive definiteness. LU is the general-purpose baseline — the standard direct solver for dense linear systems in scientific computing.

These options can be set side by side on cost per system, cost amortized over many systems, and the matrix conditions each requires.

Method	Cost for one system	Cost for k systems (same A)	Restrictions
LU with partial pivoting	≈ 2n³/3 + O(n²)	2n³/3 + 2kn²	A square and invertible
Cholesky	≈ n³/3 + O(n²)	n³/3 + 2kn²	A symmetric positive definite
Explicit inverse A⁻¹b	≈ 8n³/3 to form A⁻¹, then 2n² per multiply	8n³/3 + 2kn²	numerically less stable; rarely the right choice
Cramer's rule	O(n · n!) — impractical beyond n ≈ 4	k × O(n · n!)	theoretical only; not used in computation

Summary: What LU Computes

Once

PA = LU

is in hand, three of the most common matrix-level computations — solving a system, taking the determinant, and forming the inverse — collapse to cheap operations on the factors. The table below collects each task with the procedure it reduces to, the cost given the factorization, and the cost of doing the same task from scratch for comparison.

The split below is between paying once and paying per use. The factorization is the expensive step and happens a single time; everything after it is a triangular solve or a product along a diagonal. Reading the cost column downward shows why the decomposition is stored rather than recomputed — the first row is cubic, the rest are quadratic or less.

DownloadPNG2×PDF

Decompositions · LU

What LU computes, and at what cost

The factorization costs $\tfrac{2}{3}n^3$ once. Everything below reuses it, and the cost column is the reason the decomposition exists at all — each task afterwards is cheaper than redoing the elimination.

4tasks

The factorization itself1

1

Compute PA = LU§ 5

once per matrix

\tfrac{2}{3}n^3

flops

Gaussian elimination with the multipliers kept rather than discarded —

L

holds what was subtracted,

U

holds what remained,

P

records the row swaps. The elimination was being done anyway; LU is the observation that its byproducts are worth storing.

Reusing it — cost per use3

2

Solve a system§ 6

forward solve

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

, then back solve

U\mathbf{x} = \mathbf{y}

2n^2

per right-hand side

Two triangular solves, each

n^2

. The saving arrives on the second right-hand side: a fresh elimination would cost

\tfrac{2}{3}n^3

again, while reusing the factors costs

n^2

— which is why LU is what a solver stores when the matrix is fixed and

\mathbf{b}

varies.

3

Determinant§ 7

s

= number of row swaps in

P

\det A = (-1)^{s} \prod u_{ii}

Multiply the diagonal of

U

and correct the sign for the swaps —

O(n)

once the factorization exists. Cofactor expansion is

O(n!)

for the same number, which is the gap between a definition and a method.

4

Inverse§ 8

solve

A\mathbf{x}_i = \mathbf{e}_i

for each

i

2n^3

total

n

solves at

2n^2

each. Worth doing only when the inverse is genuinely wanted as an object — if the goal is solving systems, the triangular solves above are three times cheaper and numerically better behaved.

The economics are the whole argument. One elimination at

\tfrac{2}{3}n^3

, then

n^2

per right-hand side — so ten systems sharing a matrix cost barely more than one. Compare recomputing from scratch each time, and the saving is a factor of

n

; compare inverting, and LU is three times cheaper and more accurate besides.

What LU computes, and at what cost·/linear-algebra/decompositions/lower-upperLearn Math Class

The break-even point arrives immediately. Solving one system by elimination costs

\tfrac{2}{3}n^3

whether or not the factors are kept, so keeping them is free; the second right-hand side then costs

2n^2

instead of another

\tfrac{2}{3}n^3

. For a

1000 \times 1000

matrix that is two million operations against roughly seven hundred million — a factor of several hundred, on the same matrix, for a different

\mathbf{b}

.

The last row is the one to read as a warning. Computing

A^{-1}

through LU is perfectly possible and rarely the right thing to do: it costs three times a single solve, and using the inverse afterwards is both slower and less accurate than the two triangular solves it replaced. The inverse is worth forming when it is the answer, not when it is a step toward one.

Common Pitfalls

Four mistakes account for many wrong factorizations and wrong answers obtained from correct ones. Each is marked with a box where it happens in the sections above; here each is worked through in full.

Storing the negated multiplier

The row operation is written as "row

2

minus

2

times row

1

", and the

-2

from that operation is copied into

L

. The same is done for every step, so every entry below the diagonal of

L

has the wrong sign.

Wrong working: for the worked example, the operations add

-2

times row

1

to row

2

,

1

times row

1

to row

3

and

3

times row

2

to row

3

. Storing those amounts gives

LU = \begin{pmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 1 & 3 & 1 \end{pmatrix}\begin{pmatrix} 2 & 1 & -1 \\ 0 & -2 & 4 \\ 0 & 0 & 14 \end{pmatrix} = \begin{pmatrix} 2 & 1 & -1 \\ -4 & -4 & 6 \\ 2 & -5 & 25 \end{pmatrix} \neq A

Right working:

L

holds the multipliers

m_{21} = 2

,

m_{31} = -1

,

m_{32} = -3

, the numbers that were subtracted.

LU = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 \end{pmatrix}\begin{pmatrix} 2 & 1 & -1 \\ 0 & -2 & 4 \\ 0 & 0 & 14 \end{pmatrix} = \begin{pmatrix} 2 & 1 & -1 \\ 4 & 0 & 2 \\ -2 & 5 & 3 \end{pmatrix} = A

Why it happens: the elementary matrix

E_1

of the first step really does carry

-2

in position

(2, 1)

. But

L

is built from the inverses

E_i^{-1}

, and each inverse negates its multiplier.

How to check: the first column of

LU

is

u_{11}

times the first column of

L

, and it must equal the first column of

A

. Here

2 \cdot (1, 2, -1) = (2, 4, -2)

is correct, while

2 \cdot (1, -2, 1) = (2, -4, 2)

is not.

Choosing the largest signed entry

Partial pivoting is applied by picking the largest number in the pivot column, comparing signed values instead of absolute values. A negative entry of large size is passed over.

Wrong working: for

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

,

2 > -5

, so row

1

stays as the pivot row. The multiplier is

m_{21} = -5/2

, and

L = \begin{pmatrix} 1 & 0 \\ -5/2 & 1 \end{pmatrix}, \quad U = \begin{pmatrix} 2 & 1 \\ 0 & 11/2 \end{pmatrix}

This is a valid

A = LU

, but not the partial-pivoting factorization: the multiplier exceeds

1

in size.

Right working:

|-5| > |2|

, so the rows are swapped and

PA = \begin{pmatrix} -5 & 3 \\ 2 & 1 \end{pmatrix}

. The multiplier is

m_{21} = 2/(-5) = -2/5

, and

L = \begin{pmatrix} 1 & 0 \\ -2/5 & 1 \end{pmatrix}, \quad U = \begin{pmatrix} -5 & 3 \\ 0 & 11/5 \end{pmatrix}

Why it happens: "largest" is read as the largest number. When all entries in the column are positive the two readings agree, so the difference shows up only with negative entries.

How to check: every multiplier stored in

L

must satisfy

|l_{ij}| \le 1

. A multiplier of larger size means a larger pivot was available and was skipped.

Forgetting to permute the right-hand side

After computing

PA = LU

, forward substitution is run on

\mathbf{b}

itself. The rows of

A

were reordered, but the entries of

\mathbf{b}

were not.

Wrong working: for

A = \begin{pmatrix} 0 & 2 \\ 3 & 1 \end{pmatrix}

and

\mathbf{b} = (2, 4)

, one swap gives

P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}

,

L = I

and

U = \begin{pmatrix} 3 & 1 \\ 0 & 2 \end{pmatrix}

. Solving

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

gives

\mathbf{y} = (2, 4)

. Back substitution gives

2x_2 = 4

, so

x_2 = 2

, and

3x_1 + 2 = 2

, so

x_1 = 0

. But

A(0, 2) = (4, 2) \neq \mathbf{b}

.

Right working:

P\mathbf{b} = (4, 2)

, so

\mathbf{y} = (4, 2)

. Then

2x_2 = 2

gives

x_2 = 1

, and

3x_1 + 1 = 4

gives

x_1 = 1

. Check:

A(1, 1) = (2, 4) = \mathbf{b}

.

Why it happens:

P

is used during the factorization and then put aside, and

L

and

U

look as if they factor

A

itself. They factor

PA

.

How to check: substitute the answer into the original system

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

, not into

LU\mathbf{x} = \mathbf{b}

.

Dropping the sign of the row swaps

The determinant is taken as the product of the pivots on the diagonal of

U

, and the row swaps recorded in

P

are ignored.

Wrong working: for

A = \begin{pmatrix} 0 & 2 \\ 3 & 1 \end{pmatrix}

, one swap gives

U = \begin{pmatrix} 3 & 1 \\ 0 & 2 \end{pmatrix}

, and the product of the pivots is

3 \cdot 2 = 6

.

Right working: with

s = 1

swap,

\det A = (-1)^1 \cdot 3 \cdot 2 = -6

. Directly,

\det A = 0 \cdot 1 - 2 \cdot 3 = -6

.

Why it happens: without pivoting the determinant is exactly the product of the pivots, and that is the form most often remembered. The sign factor only appears once

P

is in play.

How to check: count the swaps, or compute

\det P

, which is

+1

or

-1

. For a

2 \times 2

matrix, compare with

ad - bc

.

LU Decomposition FAQ

Do both $L$ and $U$ have ones on the diagonal?

+

Only

L

does. The unit diagonal is a normalisation chosen to make the factorisation unique, and

U

instead carries the pivots along its diagonal, whose product gives the determinant. Note that unit here means the entries equal one, with no claim about unit length or orthonormal columns.Read more →

Can you drop the permutation $P$ once you have $L$ and $U$ ?

+

No, because

P

recorded the row swaps and those swaps must reach the right-hand side too. Solving

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

from

PA = LU

means running forward substitution on

P\mathbf{b}

, not on

\mathbf{b}

. Using the untouched vector silently solves a system whose rows are in the wrong order.Read more →

Is $UL$ the same as $LU$ ?

+

No, they are different products describing different matrices, and the order in

A = LU

is fixed by the elimination that produced it: the lower factor records what was done, the upper factor what was left. The pair is also meant to be kept and reused, so multiplying back to

A

is only ever a check.Read more →

What is the difference between LU decomposition and Gaussian elimination?

+

None in the arithmetic: LU is Gaussian elimination with the multipliers kept instead of thrown away.

U

is the echelon form that elimination reaches, and

L

stores each multiplier at the position of the zero it created. For a single system both cost about

\frac{2}{3}n^3

operations. The difference shows with the next right-hand side, which costs only two triangular solves, about

2n^2

, instead of a fresh elimination.Read more →

Does partial pivoting guarantee an accurate LU factorization?

+

No, though it rarely fails in practice. Pivoting keeps every multiplier in

L

at most

1

in size, but an entry can still double at each step, so the entries of

U

can grow by a factor of up to

2^{n-1}

, and rounding errors grow with them. The bound is reached by the matrix with ones on the diagonal and in the last column and

-1

below the diagonal; at

n = 60

that growth ruins a double-precision solution.Read more →

Should you compute the inverse to solve $A\mathbf{x} = \mathbf{b}$ ?

+

No, solve with the LU factors unless the inverse itself is the answer wanted. Forming

A^{-1}

costs about

2n^3

operations, three times the

\frac{2}{3}n^3

of the factorization, and multiplying

A^{-1}\mathbf{b}

afterwards costs as much as the two triangular solves it replaces while being less accurate. With the factors stored, every new right-hand side is just a forward and a back substitution.Read more →

Lower-Upper Decomposition

Gaussian Elimination as a Matrix Factorization

What LU Decomposition Is

LU Notation

LU Notation

Construction from Gaussian Elimination

Worked Example

The Structure of L and U

What each factor holds

When LU Exists Without Pivoting

Partial Pivoting: PA = LU

Solving Systems with LU

LU and the Determinant

LU and the Inverse

Worked Example: 4×4 with Pivoting

Computational Cost

Summary: What LU Computes

What LU computes, and at what cost

Common Pitfalls

LU Decomposition FAQ

Do both $L$ and $U$ have ones on the diagonal?

Can you drop the permutation $P$ once you have $L$ and $U$ ?

Is $UL$ the same as $LU$ ?

What is the difference between LU decomposition and Gaussian elimination?

Does partial pivoting guarantee an accurate LU factorization?

Should you compute the inverse to solve $A\mathbf{x} = \mathbf{b}$ ?

Lower-Upper Decomposition

Gaussian Elimination as a Matrix Factorization

What LU Decomposition Is

LU Notation

LU Notation

Construction from Gaussian Elimination

Worked Example

The Structure of L and U

What each factor holds

When LU Exists Without Pivoting

Partial Pivoting: PA = LU

Solving Systems with LU

LU and the Determinant

LU and the Inverse

Worked Example: 4×4 with Pivoting

Computational Cost

Summary: What LU Computes

What LU computes, and at what cost

Common Pitfalls

LU Decomposition FAQ

Do both LLL and UUU have ones on the diagonal?

Can you drop the permutation PPP once you have LLL and UUU?

Is ULULUL the same as LULULU?

What is the difference between LU decomposition and Gaussian elimination?

Does partial pivoting guarantee an accurate LU factorization?

Should you compute the inverse to solve Ax=bA\mathbf{x} = \mathbf{b}Ax=b?

Do both $L$ and $U$ have ones on the diagonal?

Can you drop the permutation $P$ once you have $L$ and $U$ ?

Is $UL$ the same as $LU$ ?

Should you compute the inverse to solve $A\mathbf{x} = \mathbf{b}$ ?