LU decomposition (numerical): Question bank — Maths deep dive

Reminder of the vocabulary you need (all built in the parent note): $A = LU$ means we split a square matrix into a lower-triangular $L$ (only zeros above the diagonal) times an upper-triangular $U$ (only zeros below the diagonal). In the Doolittle convention $L$ carries $1$ 's on its diagonal. The entries of $L$ below the diagonal are written == $ℓ_{ij}$ == (row $i$ , column $j$ , with $i > j$ ) — these are the elimination multipliers, i.e. how much of an upper row we subtracted to zero out entry $(i, j)$ . The pivots are the diagonal entries $u_{j j}$ of $U$ . Partial pivoting (Partial Pivoting) reorders rows via a permutation matrix $P$ (Permutation Matrices) to give $P A = LU$ .

The next picture shows the real engine behind the Doolittle ordering — why solving row of $U$ , then column of $L$ , repeat never leaves you with two unknowns at once. Follow the orange highlight: each new equation touches exactly one entry you don't yet know.

True or false — justify

A = LU

always possible for any invertible square

A

, with no row swaps?

False — a leading principal submatrix (a top-left square block) can be singular, which forces a zero pivot and breaks the factorization even though

A

itself is invertible;

P A = LU

(with swaps) always exists.

In Doolittle form, is the LU factorization of a matrix unique when it exists?

True — fixing

L

's diagonal to all

1

's removes the one scaling freedom between

L

and

U

, so the entries are forced and unique.

True or false: if

A

is symmetric, then

L = U^{⊤}

automatically in the Doolittle factorization.

False — Doolittle forces

1

's on

L

's diagonal, so

L \neq = U^{⊤}

in general; the symmetric analogue is Cholesky Decomposition

A = L L^{⊤}

, which needs

A

symmetric positive-definite.

Is it true that

det L = 1

in every LU decomposition?

Only in the Doolittle convention — the

1

's on

L

's diagonal make its product-of-diagonal determinant equal

1

; in Crout Decomposition the

1

's sit on

U

instead, so there

det U = 1

True or false: a lower-triangular times an upper-triangular matrix is always triangular.

False — the product

LU

generally fills every entry; that is exactly why

A

(a full matrix) can equal

LU

Is it true that partial pivoting can change which matrix you factor but never changes the final solution

x

True — swapping rows of

A

and the matching entries of

b

is just reordering equations, which never alters the solution set; it only reorders the arithmetic for stability.

True or false: computing

A^{- 1}

and forming

A^{- 1} b

gives the same accuracy as an LU-solve.

False — explicit inversion does more arithmetic and amplifies rounding more, so LU-solve is both faster and more accurate (see Condition Number and Numerical Stability).

Is the number of row swaps used in an LU with pivoting uniquely determined?

No — different valid pivoting choices can swap differently, but the parity (even vs odd) of swaps is fixed because it must match the sign of

det A

via Determinants.

Spot the error

"Since

L

and

U

are both triangular, I'll put the

1

's on

U

AND on

L

to be safe." — what's wrong?

You cannot fix both diagonals: that over-constrains the system and destroys the factorization. You choose exactly one convention (Doolittle:

1

's in

L

; Crout:

1

's in

U

"I solved

P A = LU

but plugged the original

b

straight into

L y = b

." — the bug?

The row swaps stored in

P

must be applied to the right-hand side too; you must solve

L y = P b

, otherwise the equations no longer match their reordered rows.

u_{11} = a_{11} = 0

, so I set

ℓ_{21} = a_{21} / u_{11}

and got a huge number — the matrix must be singular." — is the diagnosis right?

Not necessarily — a zero pivot can occur in a perfectly invertible matrix (like

(0111)

); the cure is a row swap, not declaring

A

singular. (Here

ℓ_{21}

is the multiplier that would zero the

(2, 1)

entry — dividing it by the zero pivot is what exploded.)

"To get

det A

I multiplied the diagonal of

U

and stopped there." — what did you forget?

The sign from pivoting:

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

. If any rows were swapped, omitting

(- 1)^{# swaps}

gives the wrong sign.

"I did back substitution on

L y = b

starting from the bottom row." — why does this fail?

L

is lower-triangular, so its first row has a single unknown; you must go top-to-bottom (forward substitution). Bottom-first is for the upper-triangular

U

"The multipliers I discard during Gaussian elimination are irrelevant to LU." — correct?

Wrong — those discarded multipliers are the entries

ℓ_{ij}

L

(row

i

, column

j

); LU's whole trick is keeping them instead of throwing them away.

"Partial pivoting picks the largest entry in the whole remaining matrix as the pivot." — accurate?

No — partial pivoting searches only the current column (below the diagonal) for the largest magnitude; searching the whole submatrix is complete pivoting, a different, costlier scheme.

Why questions

Why does having triangular factors make solving so cheap?

A triangular system reveals one unknown per row in order, so each equation is solved by a single division after back-substituting knowns — no elimination sweep is needed.

Why do we choose the largest available pivot rather than just any nonzero one?

A large pivot keeps every multiplier

∣ ℓ_{ij} ∣ \leq 1

, which prevents small rounding errors from being multiplied into large ones during elimination.

Why does LU pay off only when we resolve with many right-hand sides?

The expensive elimination is done once to build

L

and

U

; each new

b

then costs only two cheap triangular substitutions, so the setup cost is amortised across solves.

Why is the determinant of a triangular matrix just the product of its diagonal?

Expanding by the column (or row) that has a single nonzero entry each time leaves only the diagonal factors multiplied together, with all off-diagonal cofactors zero.

Why does the row-by-

U

, column-by-

L

ordering in Doolittle work so smoothly?

Picture matching

A = LU

one entry at a time (see the second figure): each new entry equation is a sum of already-known products plus one brand-new unknown, because everything "earlier" in the row/column snake has already been solved. So instead of a tangled simultaneous system you get a clean chain, solving one variable per equation — exactly like knocking over dominoes in order.

Why can a nearly-zero pivot be almost as bad as an exactly-zero one?

Dividing by a tiny pivot produces enormous multipliers that amplify floating-point rounding, so accuracy collapses even though no literal division-by-zero occurs.

Why is

P A = LU

(with

P

a permutation) enough to guarantee a factorization for every invertible

A

Because for any invertible

A

there is always a row ordering that keeps every leading pivot nonzero, and

P

records exactly that reordering.

Edge cases

What is the LU decomposition of the identity matrix

I

L = U = I

: it is already both lower- and upper-triangular with unit diagonal, so no elimination is needed and

I = I \cdot I

What happens when you LU-factor a matrix that is already upper-triangular?

U = A

and

L = I

: there is nothing below the diagonal to eliminate, so all multipliers

ℓ_{ij}

are zero.

If a matrix is

1 \times 1

, say

A = (a)

with

a \neq = 0

, what are

L

and

U

L = (1)

and

U = (a)

in Doolittle form; there are no off-diagonal entries, so the factorization is trivial.

What does a zero on the diagonal of

U

tell you about

A

(assuming you have already pivoted as much as possible)?

After all valid row swaps, if a pivot is still forced to zero then

\prod u_{ii} = 0

, so

det A = 0

and

A

is genuinely singular — no swap can rescue it because the rows are linearly dependent. (A zero pivot before pivoting is different: that one a row swap can fix.)

For a diagonal matrix

D

with nonzero entries, what are its LU factors?

L = I

and

U = D

: a diagonal matrix is simultaneously lower- and upper-triangular, so all off-diagonal multipliers vanish.

What is the smallest change to

(0111)

that makes Doolittle work without any swap, and what does the factorization become?

Replace the

(1, 1)

zero by any nonzero value

ε

, giving

(ε 1 11)

; then

u_{11} = ε

ℓ_{21} = 1/ ε

u_{22} = 1 - 1/ ε

, so it factors — but as

ε \to 0

the multiplier

1/ ε

blows up, showing that "just non-zero" fixes the breakdown yet a tiny

ε

still wrecks numerical accuracy (why we prefer a swap).

Recall One-line summary to lock it in

LU is Gaussian elimination saved as data: $L$ holds the multipliers $ℓ_{ij}$ , $U$ holds the pivots $u_{j j}$ , $P$ (when needed) holds the swaps — and every "trap" above is either a convention slip (whose diagonal gets the $1$ 's), a bookkeeping slip (permute $b$ too), or a stability slip (avoid tiny pivots).