You need to solve Ax = b for 50 different right-hand-side vectors b, where A is a fixed 500×500 matrix. Compared to running Gaussian elimination 50 separate times, LU decomposition offers what advantage?
ALU is faster only for the first solve; subsequent solves cost the same as elimination
BLU performs one O(n³) factorization, then each of the 50 solves costs only O(n²) via forward and back substitution
CBoth approaches cost the same total work — LU is only useful when b is unknown in advance
DLU avoids all numerical errors, making it more accurate rather than faster
This is the core practical payoff of LU decomposition. Gaussian elimination on a new b costs O(n³) each time because it redoes the entire elimination. LU factors A once at O(n³), then each new b requires only forward substitution (Ly = b, O(n²)) and back substitution (Ux = y, O(n²)). For 50 right-hand sides, LU replaces 50 × O(n³) operations with 1 × O(n³) + 50 × O(n²) — a dramatic saving for large n.
Question 2 Multiple Choice
What does the lower triangular matrix L in an LU decomposition actually store?
AThe inverse of the upper triangular matrix U
BThe row echelon form of A with the pivots on the diagonal
CThe multipliers used during Gaussian elimination to zero out below-diagonal entries
DThe eigenvalues of A arranged in lower triangular form
Each entry ℓᵢⱼ below the diagonal of L is the multiplier used in Gaussian elimination to eliminate the entry in row i, column j: the ratio aᵢⱼ/aⱼⱼ at that elimination step. L is not invented separately — it is produced automatically as a byproduct of elimination. The diagonal of L is all 1s because each row trivially eliminates itself. This is the elegant insight: elimination produces both U (explicitly) and L (via the recorded multipliers) simultaneously.
Question 3 True / False
LU decomposition typically exists for any invertible matrix without requiring row interchanges.
TTrue
FFalse
Answer: False
This is a common misconception. Even invertible matrices can produce a zero pivot during elimination, which requires a row swap before proceeding. When row swaps are needed, the correct factorization is PA = LU, where P is a permutation matrix recording the row swaps. In practice, partial pivoting (swapping rows to place the largest available pivot first) is always used for numerical stability, even when pivots wouldn't be exactly zero. A = LU without P only works for matrices where elimination proceeds with no row swaps.
Question 4 True / False
Solving the triangular system Ly = b (forward substitution) costs O(n²) operations, which is cheaper than the O(n³) required for full Gaussian elimination on Ax = b.
TTrue
FFalse
Answer: True
A lower triangular system with n unknowns is solved row by row from top to bottom. Each row i requires i–1 multiplications and subtractions (for already-solved variables) plus one division — O(i) operations. Summing over all rows gives O(1 + 2 + ... + n) = O(n²). The same applies to back substitution for U. Full Gaussian elimination, which must also reduce the matrix, costs O(n³). This is why LU's value is realized when the expensive O(n³) factorization is done once and the cheap O(n²) triangular solves handle many right-hand sides.
Question 5 Short Answer
Why is LU decomposition more efficient than repeated Gaussian elimination when solving Ax = b for many different vectors b, and what is the role of each factor?
Think about your answer, then reveal below.
Model answer: LU decomposition separates the expensive part (transforming A, which costs O(n³)) from the cheap part (using the factored form to solve for each b, which costs O(n²)). L records the elimination steps and U is the resulting echelon form. For each new b, forward substitution (Ly = b) reconstructs what b would look like after those same elimination steps, and back substitution (Ux = y) solves the resulting upper triangular system — both at O(n²).
The key insight is that the structure of A doesn't change across systems with different b vectors. Gaussian elimination re-derives that structure every time. LU captures it once. The factorization is the work; subsequent solves are inexpensive lookups through the stored L and U. This is why numpy.linalg.solve and MATLAB's backslash operator use LU internally — the same factorization is reused even when you only see one call.