LU Decomposition

Concept Overview

LU Decomposition (also known as LU factorization) is a method in linear algebra that writes a square matrix as the product of two matrices: a lower triangular matrix (L) and an upper triangular matrix (U). This factorization is fundamentally connected to Gaussian elimination, essentially capturing the sequence of row operations needed to transform a matrix into row-echelon form.

Definition

For a square matrix A, an LU decomposition is the factorization:

A = L × U

Where:

A is an n × n square matrix.
L is a lower triangular matrix, meaning all entries above the main diagonal are zero. In standard (Doolittle) factorization, the main diagonal consists of 1s (L_ii = 1).
U is an upper triangular matrix, meaning all entries below the main diagonal are zero.

Key Concepts

Doolittle vs. Crout vs. Cholesky: Various conventions exist for the decomposition. Doolittle's method ensures L has 1s on the diagonal. Crout's method ensures U has 1s on the diagonal. Cholesky decomposition is a specialized form for symmetric positive-definite matrices where U is the transpose of L (A = LL^T).
Pivoting: Not all matrices can be decomposed directly into A = LU. If a zero is encountered on the diagonal during the decomposition process (a zero pivot), row swaps are necessary. This yields the PLU factorization: PA = LU, where P is a permutation matrix.
Solving Systems of Equations: Once A is factored into L and U, solving the linear system Ax = b becomes extremely efficient. It is broken down into two simpler triangular systems:
1. Solve Ly = b for y (forward substitution)
2. Solve Ux = y for x (backward substitution)

Historical Context

The formalization of matrix decompositions gained prominence alongside the development of digital computers. Alan Turing introduced the LU decomposition in 1948 in his paper "Rounding-off Errors in Matrix Processes." Turing demonstrated that Gaussian elimination can be viewed as the matrix factorization A = LU, which became a foundational perspective in numerical linear algebra, leading to modern software libraries like LAPACK.

Applications

Numerical Solutions: Efficiently solving Ax = b when A is fixed but there are many different right-hand side vectors b. Factoring A once allows for rapid solutions for any b.
Matrix Inversion: Computing the inverse of a matrix by solving AX = I column by column.
Determinant Computation: The determinant of A is simply the product of the diagonal elements of U (and L, which is typically 1). This turns an O(n!) operation into an O(n³) operation.
Engineering Simulations: Used extensively in finite element analysis, circuit simulation, and fluid dynamics where large linear systems must be solved repeatedly.

Related Concepts

Systems of Linear Equations: The primary problem LU decomposition aims to solve.
Determinant & Area: Computing the determinant is vastly simplified via the upper triangular matrix U.
Matrix Multiplication: The reverse operation used to construct the original matrix from L and U.

LU Decomposition