LU Decomposition: Factorization & Solving

What LU Decomposition Is

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.

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.

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

Construction from Gaussian Elimination

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

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

):

\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

):

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

.

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.

Download

PNGRaster · 2×PDFPrint quality

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

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, 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.

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.

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.

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)

.

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

kn^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.

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}

.

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

— cheaper than

n

independent eliminations.

In practice, computing

A^{-1}

explicitly is rarely the right approach. Solving

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

via LU is faster than multiplying

A^{-1}\mathbf{b}

, and 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

:

\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

:

\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 both row swaps,

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.

Download

PNGRaster · 2×PDFPrint quality

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.

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 →

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

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

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

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?

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