LU decomposition, pivoting and triangular solves

Objectives and conventions

Factor a matrix by elimination, solve systems using triangular factors, and account for row permutations. Prerequisites: row operations, determinants and linear systems. We use the Doolittle convention: L is lower triangular with diagonal entries one and U is upper triangular. For pivoted factorization our equation is PA=LU, where P permutes rows. Some texts write A=PLU using a differently defined permutation; read the equation, not just the letters.

1. Elimination stores multipliers

For A=[[2,1],[6,5]], the first pivot is 2. The multiplier is l₂₁=6/2=3. Apply R₂←R₂−3R₁ to obtain U=[[2,1],[0,2]]. Store the multiplier in L=[[1,0],[3,1]]. Multiplying verifies LU=[[2,1],[6,5]]=A. L stores 3, not −3: it reverses the elimination step when rebuilding A.

More generally, at stage k use mᵢₖ=aᵢₖ/aₖₖ for each row i>k and subtract mᵢₖ times the pivot row from row i. The current entries, after earlier elimination stages, determine these ratios. The multipliers form the strict lower triangle of L. The resulting U retains the pivots and upper entries. Division by a zero pivot is invalid; do not silently continue the formula.

A 3×3 example illustrates two stages. For A=[[2,1,1],[4,3,3],[8,7,9]], first use m₂₁=2 and m₃₁=4 to obtain rows [0,1,1] and [0,3,5]. Next m₃₂=3 gives [0,0,2]. Thus L=[[1,0,0],[2,1,0],[4,3,1]] and U=[[2,1,1],[0,1,1],[0,0,2]]. Check the last row of LU: 4[2,1,1]+3[0,1,1]+[0,0,2]=[8,7,9].

2. Forward and backward substitution

If A=LU, solve Ly=b first, then Ux=y. For the 2×2 example and b=(5,17)ᵀ, forward substitution gives y₁=5 and 3y₁+y₂=17, so y₂=2. Back substitution gives 2x₂=2 and 2x₁+x₂=5, hence x=(2,1)ᵀ. Verify Ax=(5,17)ᵀ.

For unit-diagonal L, yᵢ=bᵢ−Σⱼ<ᵢ lᵢⱼyⱼ. For U with nonzero diagonal, xᵢ=(yᵢ−Σⱼ>ᵢ uᵢⱼxⱼ)/uᵢᵢ, evaluated from the last row upward. Triangular solves do not require explicitly constructing A⁻¹. If a diagonal entry of U is zero, unique back substitution is not justified; examine consistency and free variables instead.

3. An invertible matrix can need a row swap

A=[[0,1],[1,1]] has det(A)=−1, so it is invertible, but its first pivot is zero. With P=[[0,1],[1,0]], PA=[[1,1],[0,1]]. Here L=I and U=PA. Ordinary no-swap unit-lower LU cannot work for this A: the (1,1) product entry would force u₁₁=0, making the (2,1) product entry l₂₁u₁₁=0 instead of 1.

To solve Ax=b with PA=LU, first permute b: Ly=Pb, then Ux=y. For b=(2,5)ᵀ, Pb=(5,2)ᵀ, so y=(5,2)ᵀ and Ux=y gives x₂=2, x₁=3. The original A times (3,2)ᵀ is (2,5)ᵀ. Forgetting to permute b solves a different system.

4. Partial pivoting and later swaps

Partial pivoting chooses an entry of largest absolute value in the current pivot column among the remaining rows, then swaps that row into the pivot position. It avoids division by zero when a usable entry exists and usually reduces the risk from tiny pivots. It does not guarantee that every numerical error disappears. A zero entire remaining pivot column means no nonzero pivot is available there; rank and consistency need attention.

If a swap occurs after earlier columns have been eliminated, also swap the affected rows in the already-computed columns of L. Do not swap its untouched unit-diagonal structure wholesale. Accumulate every row swap into P so PA=LU remains true.

Example with a later swap: A=[[2,0,0],[1,0,1],[1,1,0]]. First-column multipliers are both 1/2. The remaining rows become [0,0,1] and [0,1,0], so rows 2 and 3 must swap. With P swapping rows 2 and 3, L=[[1,0,0],[1/2,1,0],[1/2,0,1]] and U=diag(2,1,1). The previously stored multipliers are equal in this example, so swapping them leaves their values unchanged. Multiplying LU verifies PA=[[2,0,0],[1,1,0],[1,0,1]]. In a general example those stored multipliers may differ and must be exchanged.

5. Existence, determinants and reuse

For a nonsingular square matrix, no-swap Doolittle elimination has nonzero pivots exactly when all leading principal minors are nonzero. A leading principal minor of order k is the determinant of the top-left k×k block. This is a criterion for the nonsingular no-swap case, not a claim that every singular matrix lacks an LU factorization. With row pivoting, every nonsingular square matrix admits PA=LU with nonzero pivots. Under the unit-diagonal convention the no-swap nonsingular factorization, when it exists, is unique.

For PA=LU, det(L)=1 and det(U)=∏ᵢuᵢᵢ. If P represents s row swaps, det(A)=(−1)ˢ∏ᵢuᵢᵢ. In the 3×3 no-swap example the determinant is 2×1×2=4. In the 2×2 swapped example it is −1×1×1=−1.

Dense elimination costs O(n³) arithmetic operations. Once factors are available, each new right-hand side costs O(n²) for two triangular solves. This reuse is why LU is useful when the same A appears with many b vectors. A singular system may still have solutions, but the automatic unique-solve pipeline requires nonsingularity.

Checklist

State A=LU or PA=LU and the diagonal convention. Record current pivots and multipliers, handle swaps in P and earlier columns of L, and verify by multiplication. Permute the right-hand side exactly as in PA=LU, solve lower then upper, and substitute in the original system. Keep determinant swap signs separate from elimination multipliers.

Original practice: six single-correct MCQs

These are original questions, not previous-year questions. Choose exactly one option.

LU01. Using unit-diagonal L, what is the elimination multiplier l₂₁ for A=[[2,1],[6,5]] without pivoting?

A. −3 B. 3 C. 6 D. 1/3

Answer: B

A: The row operation subtracts 3 times row 1, but L stores positive multiplier 3.

B: l₂₁=a₂₁/a₁₁=6/2=3.

C: Divide by the pivot 2.

D: This reverses the ratio.

LU02. For L=[[1,0],[3,1]], U=[[2,1],[0,2]], what is LU?

A. [[2,1],[6,5]] B. [[2,1],[3,2]] C. [[2,0],[6,2]] D. [[2,3],[1,5]]

Answer: A

A: Row-column multiplication gives bottom row (6,5).

B: This copies entries without the required dot products.

C: The upper-right entry is 1 and lower-right is 5.

D: The entries are not obtained by the stated product order.

LU03. Why does A=[[0,1],[1,1]] require a row swap for ordinary first-column elimination?

A. A is singular B. The first pivot is zero although A is invertible C. Both rows are zero D. Its determinant is zero

Answer: B

A: det(A)=−1, so A is invertible.

B: The multiplier 1/0 is undefined; swapping rows supplies a nonzero pivot.

C: Neither row is zero.

D: The determinant is −1.

LU04. Given PA=LU, which two systems solve Ax=b?

A. Ly=b, Ux=y B. Uy=Pb, Lx=y C. Ly=Pb, Ux=y D. Ly=Pb, Ux=Py

Answer: C

A: The right-hand side must undergo the same row permutation.

B: This reverses the factor order.

C: PAx=Pb becomes LUx=Pb; let y=Ux.

D: The permutation has already been applied to b; no extra P belongs here.

LU05. PA=LU, L has unit diagonal, diag(U)=(2,−3,4), and P represents one row swap. What is det(A)?

A. −24 B. 24 C. −5 D. 9

Answer: B

A: −24 is det(U)=det(PA), not det(A) after accounting for the swap.

B: det(P)=−1 and det(L)=1, so −det(A)=−24 and det(A)=24.

C: Multiply the diagonal entries of U and include the row-swap sign; this gives 24, not −5.

D: The product and permutation sign must both be included.

LU06. In partial pivoting at column k, which pivot row is selected from rows k,…,n?

A. A row with largest absolute entry in column k B. A row with largest signed entry anywhere in A C. Always row k without inspection D. A row with smallest absolute entry in column k

Answer: A

A: Partial pivoting maximizes |aᵢₖ| in the current remaining column.

B: The search is restricted to the current column, and uses absolute value.

C: A swap may be needed for zero or small pivots.

D: Small pivots can produce large multipliers and amplify roundoff.

Source and scope

Directly supports the official LU decomposition heading and connects it to systems of linear equations. Pivoting conventions and triangular solves are included; all six questions are original.

Official GATE 2026 CS syllabus (verified 2026-10-14).