Are L and U always enough by themselves?

With pivoting, the permutation information is also needed.

Can the same factors solve several right-hand sides?

Yes, if the coefficient matrix is unchanged.

Does LU only apply to square matrices?

Rectangular factorization variants exist, but the simple unique-solution discussion here assumes a nonsingular square system.

AI Glossary / Mathematics and optimization / Intermediate

LU decomposition

Definition

LU decomposition factors a matrix into a lower-triangular matrix L and an upper-triangular matrix U, often after row permutations. It is a practical foundation for solving linear systems. In the convention used here, PA=LU, where P records the row rearrangement. Some libraries instead write A=PLU using the inverse permutation convention, so the documented equation must be checked.

What it means

A triangular system is easier to solve than a general dense system because its unknowns can be determined in sequence. LU decomposition performs the expensive elimination once, preserving the factors for later solves with the same coefficient matrix.
The factors describe algebraic operations on the matrix; they are not generally its eigenvalues or singular values. Pivoting, which rearranges rows to choose suitable elimination pivots, is important for avoiding breakdown and controlling numerical behavior. Factorization success also does not guarantee that the original problem is well-conditioned.

How it works

Gaussian elimination removes entries below successive pivots. The elimination multipliers become entries of L, while the resulting upper-triangular matrix becomes U. A common convention gives L a unit diagonal. With partial pivoting, each step selects a largest-magnitude available entry in the current column and swaps rows as needed.
To solve Ax=b under PA=LU, first apply P to b. Solve Ly=Pb by forward substitution, then Ux=y by back substitution. Preserve the pivot information along with the factors. Singular pivots, scaling, and conditioning need attention, and sparse matrices may require ordering strategies to control new nonzero entries.

Three practical examples

A simulation can reuse one factorization when the same system matrix is solved for several different loads or inputs.
A numerical optimization routine can use LU as part of solving an appropriate general linear subproblem.
A scientific-computing tool can obtain determinant information from triangular factors and row permutations, while separately assessing whether a solve is numerically reliable.

Think of it this way

Think of reorganizing a complicated set of dependencies into two sequences that can be processed one step at a time. The initial reorganization is reused for several requests. The analogy is limited because L and U are matrices whose product reproduces the permuted coefficients; they are not independent approximations or loosely ordered task lists.

Worked example

Consider an original matrix A with rows (1,2) and (3,4). We want to solve Ax=b for b=(5,11). Partial pivoting chooses 3 rather than 1 as the first pivot, so swap the two rows. The permutation P has rows (0,1) and (1,0), giving PA with rows (3,4) and (1,2).
The elimination multiplier is 1/3. Subtract one third of the first row from the second. The resulting second row is (0,2/3). Thus U has rows (3,4) and (0,2/3), while L has rows (1,0) and (1/3,1).
Verify the factorization explicitly. The first row of LU is (3,4). The second row is one third of U's first row plus its second row, giving (1,4/3+2/3)=(1,2). Therefore LU=PA exactly.
Apply the same row permutation to b: Pb=(11,5). Forward substitution in Ly=Pb gives y1=11 and y2=5-11/3=4/3. Back substitution gives x2=(4/3)/(2/3)=2, followed by x1=(11-4 times 2)/3=1. Checking the original equations gives 1+2(2)=5 and 3(1)+4(2)=11.
Now change only the right-hand side to b_new=(8,18). Reuse P, L, and U. Forward substitution gives y1=18 and y2=8-18/3=2. Back substitution gives x2=3 and x1=(18-12)/3=2. The matrix did not change, so a second factorization was unnecessary.
The determinant also illustrates why the permutation matters. The diagonal product of U is 3 times 2/3=2, and det(L)=1. Since P contains one row swap, det(P)=-1. From det(P)det(A)=det(L)det(U), the original determinant is -2, agreeing with 1 times 4 minus 2 times 3.
For contrast, a matrix with rows (1,2) and (2,4) is singular. After pivoting and elimination, its final U diagonal entry is zero. LU storage may still be produced, but ordinary back substitution cannot treat that factor as invertible. This is a different issue from merely needing a row swap.

Illustrative case study

In a fictional structural-analysis project, Redbank Engineering studies several loading scenarios that share the same coefficient matrix. Its analysts factor the matrix once, solve each right-hand side using the stored factors, and verify residuals against the original equations.
When a design change alters the matrix, the team recomputes the factorization rather than reusing stale factors. It also checks conditioning before interpreting small output differences. The scenario illustrates reuse and validation, not a measured speedup or a real engineering certification.

Common misconceptions and mistakes

Do not forget to permute the right-hand side. Do not read a compact library factor array as though it were a single ordinary matrix: many routines store parts of L and U together and omit L's known unit diagonal.
A matrix that fails elimination without pivoting is not necessarily singular. Conversely, a successful pivoted factorization does not eliminate sensitivity in an ill-conditioned system. Avoid explicitly forming a matrix inverse merely to solve Ax=b when triangular solves provide the required result more directly.

Business use

Business value is often the ability to reuse numerical work across repeated scenarios. Track matrix versions, dimensions, pivot conventions, factorization status, and solve residuals. For large sparse problems, memory use can depend heavily on fill-in rather than only the original number of nonzeros. Choose the decomposition according to matrix properties: positive-definite, symmetric, rectangular, and rank-deficient problems can call for different approaches.

Check your understanding

Why does the diagonal product of U give 2 while det(A) is -2 in the example?

Answer: One row swap has determinant -1. The permutation sign must be included when recovering the original determinant.

Related terms

Conditioning
Singular matrix
Gaussian elimination
Partial pivoting
Triangular matrix
Forward substitution
Back substitution
Permutation matrix
Fill-in
Cholesky decomposition

Learn next

Use the same factors to solve Ax=(1,1). Check the result directly in the original equations. Then explain why changing one coefficient of A generally invalidates the stored factors even if the right-hand side remains unchanged.

Sources

Primary implementation source: LAPACK DGETRF documentation and source: https://www.netlib.org/lapack/explore-html/db/d04/group__getrf_gaea332d65e208d833716b405ea2a1ab69.html . The two-system solve, determinant calculation, and singular example are original.

Previous: Low-pass filter Next: Lucas--Kanade method