LU decomposition — algorithm, applications: Question bank

This bank supports LU decomposition — algorithm, applications and links to Gaussian Elimination, Permutation Matrices, Determinants, Matrix Inverse, Cholesky Decomposition, and Triangular Systems & Substitution. Everything you need is defined right here — you should not have to leave this page.

A picture-first refresher (read before the traps)

Figure — LU decomposition — algorithm, applications

Definition Terms this page uses (no jumping to other notes)

Pivot: the diagonal entry $a_{k k}$ (after earlier steps) you divide by to clear the column below it.
Multiplier: $m_{ik} = a_{ik} / a_{k k}$ , "how many pivot-rows to subtract from row $i$ ". These become the below-diagonal entries of $L$ .
Leading principal submatrix of order $k$ : the top-left $k \times k$ block of $A$ (rows $1.. k$ , columns $1.. k$ ). Its picture is the shrinking square in the corner (see next figure). Plain $A = LU$ exists exactly when every such block, for $k = 1, \dots, n$ , is nonsingular (nonzero determinant).
Partial pivoting: at each step swap in the row with the largest-magnitude entry in the current column, and record the swap in a permutation matrix $P$ , giving $P A = LU$ . Only rows move.
Full (complete) pivoting: swap both a row and a column to bring the largest entry anywhere in the remaining block to the pivot — recorded as $P A Q = LU$ with two permutations. More stable, rarely worth the cost.

True or false — justify

Remember the setup: $A = LU$ means $L$ is unit lower triangular (1's on its diagonal, zeros above it) and $U$ is upper triangular (zeros below its diagonal). Judge each claim, then reveal.

The diagonal entries of

L

can be any nonzero numbers

False — in the standard (Doolittle) LU the diagonal of

L

is forced to be all 1's; those 1's are what make the factorisation unique for a given

A

U

always has the pivots of Gaussian elimination on its diagonal

True — clearing each column leaves the pivot untouched on the diagonal, so

u_{ii}

is the

i

-th pivot.

Every square matrix has an

A = LU

factorisation without any row swaps

False — if a pivot position hits a zero (e.g.

a_{11} = 0

), plain

A = LU

breaks; you need

P A = LU

with a permutation

P

A

is invertible then

A = LU

(no permutation) is guaranteed

False — invertibility is not enough; you also need every leading principal submatrix (each top-left

k \times k

block) to be nonsingular.

(0110)

is invertible but its

1 \times 1

block is

0

, so it has no plain LU.

det A

equals the product of the diagonal entries of

L

times those of

U

True but trivial —

det L = 1

(product of 1's), so

det A = \prod_{i} u_{ii}

, the product of pivots.

Swapping two rows during pivoting never changes the value of

det A

False — each row swap multiplies the determinant by

- 1

, so

det A = (- 1)^{# swaps} \prod_{i} u_{ii}

The product

LU

of a lower- and an upper-triangular matrix is always triangular

False — that product is generally a full matrix (that's the whole point:

LU

rebuilds the dense

A

). Only

L \cdot L^{'}

U \cdot U^{'}

stay triangular.

For a symmetric positive-definite matrix,

L

and

U

carry no shared information

False — for SPD matrices

U = D L^{⊤}

for a diagonal

D

, which is exactly the Cholesky factorisation

A = L L^{⊤}

up to scaling;

U

is essentially

L

transposed.

An LU factorisation of a given

A

(once you fix "1's on

L

's diagonal") is unique

True — with the diagonal of

L

pinned to 1's and all pivots nonzero,

L

and

U

are uniquely determined.

Only square matrices can be LU-factorised

False — rectangular

A

factors too, with a trapezoidal

L

U

; this is why least-squares problems can lean on LU (or Cholesky of

A^{⊤} A

Spot the error

Each line states a plausible-sounding move. Find the flaw.

"To solve

A x = b

, first back-solve

L y = b

, then forward-solve

U x = y

Backwards —

L

is lower triangular so it needs forward substitution;

U

is upper triangular so it needs back substitution. The names are tied to which corner is known first.

"I have

A = LU

, so to solve

A x = b

I invert

L

and

U

and compute

U^{- 1} L^{- 1} b

Correct in symbols but self-defeating on two fronts — forming inverses costs

O (n^{3})

(destroying the speed win), and an explicit inverse spreads and amplifies round-off: multiplying by

A^{- 1}

magnifies input error by the condition number of

A

, whereas triangular substitution keeps that growth far smaller. Never invert; substitute.

"The multiplier is

m_{ik} = a_{ik} / a_{ii}

Wrong index — you divide by the pivot

a_{k k}

(the diagonal entry of the column being cleared), not

a_{ii}

m_{ik} = a_{ik} / a_{k k}

L

stores

- m_{ik}

because elimination subtracts

m_{ik}

times a row."

Wrong sign — the elimination matrix holds

- m_{ik}

, but

L

is its inverse, which flips the sign back to

+ m_{ik}

L

stores the multipliers with a plus.

"When a pivot is exactly zero I should just add a tiny

ε

to it and carry on."

Dangerous — dividing by a near-zero pivot makes some multiplier

m_{ik} = a_{ik} / ε

enormous, and that huge factor injects magnified round-off into every later entry. The correct fix is partial pivoting (a row swap recorded in

P

), which is exact and free.

"Because

det A = \prod u_{ii}

, a zero pivot means I picked the wrong algorithm."

No — a zero pivot mid-elimination for a singular

A

is honest information:

det A = 0

. The algorithm is right; the matrix simply has no inverse.

"Partial pivoting changes the answer

x

, so avoid it when possible."

False — permuting rows of

A

and

b

together yields the same solution

x

; only the numerical rounding path changes, and for the better.

"After factoring once, solving with a new

b

requires re-running Gaussian elimination."

That defeats LU's purpose — the elimination (the

O (n^{3})

work) is already baked into

L, U

. A new

b

needs only the two

O (n^{2})

substitutions.

Why questions

Why do we keep

L

and

U

instead of just storing the row-reduced

U

U

alone loses the record of how you got there;

L

holds the multipliers, letting you re-apply the elimination to any new

b

via

L y = b

without redoing the reduction.

Why does eliminating "top-down, left-to-right" let us just write the multipliers into

L

with no extra work?

Because each later elimination step touches columns to the right of, or rows below, the earlier ones — the inverse elementary matrices don't overlap, so their product just deposits each

m_{ik}

into slot

(i, k)

Why is the diagonal of

L

all 1's rather than the pivots?

Each elimination step leaves the pivot row unscaled (we subtract multiples of it, never rescale it), so the corresponding elementary matrices — and their product

L

— keep 1's on the diagonal. The pivots live in

U

instead.

Why is LU decomposition preferred over computing

A^{- 1}

explicitly for solving systems?

Forming

A^{- 1}

is more arithmetic and numerically worse — multiplying by an explicit inverse amplifies error by the condition number of

A

, while triangular solves stay tighter. LU gives the solve cheaply and more accurately.

Why does partial pivoting choose the largest candidate entry as the new pivot?

Dividing

a_{ik}

by the largest available entry forces every multiplier

∣ m_{ik} ∣ \leq 1

; small multipliers can't blow up existing round-off, so accumulated error (and the effective conditioning of the solve) stays controlled — it's about stability, not correctness.

Why can we read

det A

straight off the pivots?

Triangular determinants are just diagonal products, and

det (LU) = det L \cdot det U = 1 \cdot \prod u_{ii}

; elimination is engineered so the pivots equal that product (adjusted by

- 1

per swap).

Why does having many right-hand sides make LU so much cheaper than repeated Gaussian elimination?

The expensive factorisation (

\approx \frac{2}{3} n^{3}

) happens once; each extra

b

is two substitutions at

\approx n^{2}

each, so

k

solves cost

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

instead of

k \cdot O (n^{3})

Why do least-squares problems reach for LU or Cholesky even though

A

is rectangular?

You don't factor the tall

A

to solve directly; you form the square symmetric positive-definite

A^{⊤} A

and LU- (or Cholesky-) factor that to solve the normal equations

A^{⊤} A x = A^{⊤} b

Edge cases

Every diagonal of

A

is nonzero — does that guarantee no permutation is needed?

No — a pivot can become zero mid-elimination even when the original diagonal is fine, because later entries are updated. Only the running pivots matter.

What is the LU factorisation of a matrix that is already upper triangular?

L = I

(no elimination needed, all multipliers are 0) and

U = A

. The identity is the degenerate unit-lower-triangular matrix.

What are

L

and

U

when

A

is already lower triangular (not diagonal)?

Elimination above the diagonal does nothing (those entries are already 0), so

U

comes out diagonal, holding

A

's diagonal entries, and

L

equals

A

with each column divided by its diagonal pivot (so

L

's diagonal becomes 1's). Concretely

A = LU

with

U = diag (a_{11}, \dots, a_{nn})

and

ℓ_{ik} = a_{ik} / a_{k k}

. Only when

A

is diagonal do these collapse to

L = I, U = A

Can a singular matrix ever have a valid

A = LU

Yes — a zero can appear as a late pivot (

u_{nn} = 0

) while earlier pivots are fine, giving a legitimate

LU

with

det A = \prod u_{ii} = 0

. It just can't be used to solve for a unique

x

What happens to the two substitutions if

U

has a zero on its diagonal?

Back-substitution hits a division by that zero pivot — signalling

A

is singular, so either no solution or infinitely many exist.

For the

1 \times 1

matrix

A = (a)

with

a \neq = 0

, what are

L

and

U

L = (1)

and

U = (a)

— the unit-diagonal convention forces

L

's single entry to 1, so the lone pivot

a

sits in

U

For a tall

3 \times 2

matrix, what shapes are

L

and

U

L

3 \times 2

unit-lower-trapezoidal (1's on its two diagonal spots) and

U

2 \times 2

upper triangular — the general rectangular case with

m \geq n

A

is symmetric but not positive-definite, can we still use Cholesky instead of LU?

Not safely — Cholesky (

A = L L^{⊤}

) needs positive pivots (it square-roots them); without positive-definiteness a pivot can be negative or zero and the square root fails, so you fall back to LU with pivoting.

A

has a whole zero column, what does elimination reveal?

The pivot in that column is 0 and cannot be fixed by any row swap (the entire column is zero), so

A

is singular — no unique

LU

solve exists, matching

det A = 0

Recall One-line takeaways

$L$ is lower ⇒ forward-solve. $U$ is upper ⇒ back-solve. $L$ stores $+ m_{ik}$ with 1's on its diagonal, $U$ stores the pivots. A zero pivot means permute (if fixable) or singular (if not). Rectangular $A$ still factors — trapezoidal $L$ or $U$ — powering least-squares via $A^{⊤} A$ .