Skip to content

LU Decomposition

A square-matrix factorization into lower- and upper-triangular factors, with permutations when needed.

Version
v1 · 2026-10-03 · History
Domain-specific #
13406
Domain group
Formal Sciences
Origin domain
Mathematics
Subdomain
Numerical Linear Algebra → Mathematics
Aliases
Lu Factorization, Lower Upper Factorization

Core Idea

LU decomposition, in this entry's square-matrix sense, represents an \(n\times n\) matrix by square lower-triangular \(L\) and upper-triangular \(U\), allowing row and sometimes column permutations. In unpivoted form, \(A=LU\). LAPACK's partial-row-pivoting routine writes \(A=P_LLU\) with \(P_L\) its permutation matrix; equivalently \(P_L^{-1}A=LU\). A square sparse solver may use Li's convention \(P_S A Q_S^{T}=LU\), where \(P_S\) and \(Q_S\) reorder rows and columns. The symbols are convention-specific: one must state which product equals the actual \(A\) before solving or comparing factors. LAPACK also factors rectangular matrices, but its rectangular factors may be trapezoidal; that is a qualified extension, not the strict triangular identity developed here.[1][2]

The factorization records elimination work so that a fixed, nonsingular coefficient matrix can be used with several right-hand sides. Each \(Ax=b\) then becomes a permutation of \(b\), a lower-triangular solve, an upper-triangular solve, and any required inverse variable permutation. That use is powerful but not the definition: LAPACK can complete an LU factorization of a singular matrix and report a zero diagonal of \(U\), even though an ordinary unique solve or inverse is then unavailable.[1][3]

Structural Signature

Sig role-phrases:

  • Square coefficient matrix — An \(n\times n\) matrix \(A\) supplies the object to be factored into same-shape triangular matrices. Rectangular extensions use different factor shapes.[1]
  • Lower factor — \(L\) retains elimination multipliers in lower-triangular form, often with unit diagonal in a chosen normalization. Without it, an upper reduction alone is not a recorded LU product.[1]
  • Upper factor — \(U\) is upper triangular and pairs with \(L\) in the product identity. A zero diagonal may signal singularity of a square factorization.[1]
  • Verified product relation — \(A=LU\), LAPACK's \(A=P_LLU\), or a compatible row/column-permuted convention such as \(P_S A Q_S^T=LU\). Permutations are conditional; an arbitrary unrelated pair of triangular matrices is not a decomposition of \(A\).[1][2]

Forward/back substitution, determinant evaluation, inversion, sparse fill ordering, and reuse for multiple \(b\) are applications or implementation choices. They do not belong in the defining four-role signature. A singular matrix may still satisfy the algebraic product while defeating the usual nonsingular solve.[1]

What It Is Not

  • Not the entire Gaussian-elimination procedure. Elimination can produce \(U\); LU specifically records corresponding lower-triangular factors and an equality to the original, perhaps permuted, \(A\).
  • Not guaranteed unpivoted for every nonsingular matrix. A zero first pivot can block the chosen \(A=LU\) form even when a row permutation permits a valid factorization. Tiny nonzero pivots can also magnify rounding errors.[4]
  • Not a claim that rectangular factors are both triangular. LAPACK's M-by-N routine uses lower or upper trapezoidal factors as dimensions require; this entry's strict product and proposed Factorization parent concern square \(A\).[1]
  • Not a promise of a unique solution or inverse. A zero diagonal in \(U\) can coexist with a completed factorization and prevent standard triangular solution.[1]
  • Not Block LU or Crout alone. Block LU imposes a partitioned organization; Crout fixes a factor-diagonal normalization. Both specialize the broader lower/upper product identity.

Scope of Application

Dense numerical linear algebra uses row-pivoted LU to solve general systems. LAPACK separates DGETRF, which computes the factors and pivot record, from DGETRS, which takes those existing factors and solves one or multiple right-hand sides by row interchanges followed by lower and upper triangular solves.[1][3]

Sparse direct solvers add a different concern: elimination can turn zeros of \(A\) into nonzeros of \(L\) and \(U\), known as fill. Netlib's solver description separates ordering, symbolic analysis, numerical factorization, and solution. Li's sparse-LU analysis explicitly uses both row and column permutations \(P_S A Q_S^T=LU\). The added ordering and storage steps are practical variations of the same triangular factorization, not a new requirement for all LU.[5][2]

Clarity

The equation must be interpreted before any numerical claim. In LAPACK's documentation, \(A=P_LLU\); its stored pivot record corresponds to that routine's convention. In Li's sparse convention, \(P_S A Q_S^T=LU\); the transformed solve uses \(Ly=P_Sb\), then \(Uz=y\), then \(x=Q_S^Tz\). Confusing the two permutation orientations can produce an incorrect \(x\) even if every triangular solve is itself correct.[1][2]

“LU exists” and “LU solves my system” are also different propositions. A singular matrix can have factors; the ordinary unique-solution use requires nonzero diagonal pivots and suitable conditioning. Partial pivoting is standard and usually helpful, but it is not an unconditional promise against every possible growth or error.

Manages Complexity

The abstraction packages expensive elimination into reusable factors. For a fixed dense nonsingular \(n\)-by-\(n\) matrix, factorization is cubic-order work while each subsequent triangular solve is quadratic-order; repeated \(b\) vectors can therefore share the factors. If \(A\) itself changes, its old numeric factors generally no longer represent it and must be recomputed, even if a sparse Pattern or symbolic plan can be reused.[3][5]

The factor product also separates structural and numerical choices. Sparse ordering can reduce fill and memory, whereas pivot choices guard against unusable or tiny pivots. These objectives can conflict; a numerically safer row interchange may create additional fill.[2]

Abstract Reasoning

Suppose a row permutation has been chosen so the transformed matrix can be eliminated. At each step, entries below a pivot are removed using multiples of the pivot row. The multipliers populate a lower factor \(L\); the reduced result is upper triangular \(U\). One then checks the appropriate equality, for example \(P_S A Q_S^T=LU\) in Li's sparse convention. For solving \(Ax=b\), multiply by \(P_S\) and set \(z=Q_Sx\): solve \(Ly=P_Sb\), \(Uz=y\), and recover \(x=Q_S^Tz\).[2]

In exact arithmetic a nonsingular example can expose the need for a permutation: \(A=\begin{bmatrix}0&2\\1&3\end{bmatrix}\) has determinant \(-2\) but a zero top-left pivot. Swapping its rows gives \(P_SA=\begin{bmatrix}1&3\\0&2\end{bmatrix}=IU\), an LU product with \(L=I\) and no column permutation. The example distinguishes failure of unpivoted order from singularity of \(A\).[4]

Knowledge Transfer

The dense and sparse settings share the product invariant and the same mathematical split between factorization and triangular solution. A solver can transfer the idea “factor once for fixed \(A\), solve again for new \(b\)” across simulations, optimization, and other linear systems. It cannot blindly transfer a dense pivot record to a sparse row-and-column convention, nor reuse numeric factors after changing coefficient values.[3][2]

Block LU and Crout show another kind of transfer: different memory layout or diagonal normalization can instantiate the same lower/upper factorization while making distinct computational tradeoffs. Their existence is evidence for a broader LU identity, not a reason to collapse their specific algorithms into this entry.

Examples

Dense pivoted \(2\times2\) system. Take \(A=\begin{bmatrix}0&2\\1&3\end{bmatrix}\). The zero top-left entry blocks first-step no-pivot elimination (matrix and pivot condition). Swap rows with \(P_S=\begin{bmatrix}0&1\\1&0\end{bmatrix}\); then \(P_SA=LU\) with \(L=I\) (lower factor) and \(U=\begin{bmatrix}1&3\\0&2\end{bmatrix}\) (upper factor and product relation). For any new \(b\), use the same swap and triangular factors rather than re-eliminating \(A\).[4][3]

Mapped back: the original matrix remains nonsingular; the row permutation repairs the zero first pivot, the unit lower and upper matrices satisfy the exact product, and factor reuse is valid only while \(A\) stays fixed. This is not a claim that the particular example needs column ordering.

Sparse direct solve. A sparse fixed coefficient matrix is first ordered to limit fill where possible, analyzed for factor storage, and numerically factored into lower and upper triangular matrices. Under Li's convention the relation is \(P_S A Q_S^T=LU\); a changed right-hand side is transformed and handled by forward/back substitution, with the variable permutation undone afterward.[5][2]

Mapped back: \(A\) is the sparse carrier; the selected permutations and numeric \(L,U\) establish the product identity; triangular solves reuse these factors for new \(b\) values. If the numerical entries of \(A\) change during a simulation, the old \(L,U\) no longer meet the identity for that new matrix.

Negative boundary. A singular \(A\) may yield a completed factorization with a zero diagonal in \(U\). Calling it “LU” is valid, but claiming a unique \(Ax=b\) solution or an inverse solely from that output is not.[1]

Structural Tensions

  • Unpivoted simplicity versus viable pivots. Keeping the given row order makes \(A=LU\) simple, but a zero pivot can block it and a tiny pivot can amplify rounding. Pivoting adds a permutation and often improves numerical behavior. Diagnostic: Are the pivots nonzero and appropriately scaled for the intended arithmetic?[4]
  • Sparse fill reduction versus numerical pivot needs. A row/column order can reduce storage, while numerical viability may force further row swaps that create fill. Neither objective can be optimized in isolation for every matrix. Diagnostic: What fill and pivot growth result from the chosen order on this matrix?[2]
  • Reuse versus changed coefficients. Keeping factors makes repeated right-hand sides cheap, but factors are tied to \(A\), not just its dimensions or sparsity pattern. Diagnostic: Did only \(b\) change, or did any entry of \(A\) change?[3]

Structural–Framed Character

Evaluative weight. LU is a valid algebraic factorization when its product equation holds; whether a chosen pivoting and storage scheme is numerically useful is a separate assessment. Human-practice bound. Analysts select permutations, pivot policy and sparse ordering, while matrix multiplication fixes the equality to check.[1][5]

Institutional origin. Numerical linear algebra uses LU in dense and sparse solvers; no one LAPACK routine defines the mathematical object. Vocabulary travel. Factorization is broad, but lower/upper triangular matrices and permutation conventions are exact linear-algebra terms.[1][2]

Import versus recognition. A new case qualifies by exhibiting appropriately shaped triangular factors and the declared product relation. A generic task decomposed into phases merely imports the word. Its character: mixed-structural—a formal matrix identity whose computational value depends on algorithmic choices.

Structural Core vs. Domain Accent

Portable skeleton. Live Factorization is the staged strict genus for the scoped square-matrix identity: express one object as a product of same-type factors under its native multiplication. LU adds lower/upper triangular shape and may declare a permutation convention. Rectangular extensions are not silently imported into this strict edge.[1]

Domain-bound mechanism. For the declared square matrix, check \(PA=LU\) or its stated convention with lower and upper triangular factors. Dense storage, sparse symbolic ordering, partial pivoting and Crout normalization affect implementation; nonsingularity is needed for an ordinary unique solve but not for the bare factorization relation.[1][5][2]

Why not prime. Many objects factor under many operations, but only matrices have triangular factors in this sense and these row-permutation/solve implications. Generic “decomposition into parts” is weaker. The live Factorization prime carries the portable product pattern; LU remains a linear-algebra specialization.

This entry is a kind of Factorization. Square-matrix LU expresses a matrix as a product of same-shape lower- and upper-triangular factors.

Relationships to Other Abstractions

Local relationship map for LU DecompositionParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.LU DecompositionDOMAINPrime abstraction: Factorization — is a kind ofFactorizationPRIME

Current abstraction LU Decomposition Domain-specific

Parents (1) — more general patterns this builds on

  • LU Decomposition is a kind of Factorization Prime

    Square-matrix LU expresses a matrix as a product of same-shape lower- and upper-triangular factors.

Hierarchy path (1) — routes to 1 parentless root

Neighborhood in Abstraction Space

LU Decomposition sits in a sparse region of the domain-specific corpus (81st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Matrix Structures & Matroids (10 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With

Gaussian elimination is an operation sequence; LU is the retained triangular product. Schur decomposition uses a different unitary-similarity structure. Pivoting is an order-changing step, not the whole factorization. Finally, the fact that a singular matrix can be factored must not be confused with the assertion that its factorization supplies a unique linear-system solution or inverse.[1]

References

[1] LAPACK DGETRF documentation, Purpose and INFO descriptions, directly checked for the \(A=P_LLU\) convention, factor normalization, pivot record, and singular-factor warning. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q

[2] Xiaoye S. Li, Sparse Gaussian Elimination on High Performance Computers, University of California, Berkeley dissertation (1996), ch. 3 §3.1, printed pp. 9–11 / PDF pp. 19–21. Directly checked for \(P_S A Q_S^T=LU\), transformed triangular solves, and fill-versus-pivot tradeoffs. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k

[3] LAPACK DGETRS documentation, Purpose, NRHS, and implementation steps 182–197, directly checked for factor reuse, row interchanges, and lower/upper triangular solves. registry ↩a ↩b ↩c ↩d ↩e ↩f

[4] Cornell CS 4220, “LU factorization” lecture, block derivation and small-pivot example, directly checked; the \(2\times2\) pivot example above is independently computed, not copied from the source. registry ↩a ↩b ↩c ↩d

[5] Netlib Templates, “Direct Solvers for Sparse Matrices”, opening four-step solver sequence, directly checked for ordering, symbolic analysis, numerical L/U factorization, and solves. registry ↩a ↩b ↩c ↩d ↩e