LU decomposition, also known as LU factorization, is a matrix decomposition technique in linear algebra wherein a given square matrix $A$ is expressed as the product of a lower triangular matrix $L$ and an upper triangular matrix $U$, i.e.,
$$ A = L,U . $$
The matrices $L$ and $U$ have the following properties:
- Lower triangular matrix $L$ – All entries above the main diagonal are zero. In many formulations, the diagonal entries of $L$ are taken to be 1 (unit lower triangular), though alternative conventions allow arbitrary non‑zero diagonal entries.
- Upper triangular matrix $U$ – All entries below the main diagonal are zero.
When a permutation matrix $P$ is incorporated to account for row exchanges required for numerical stability, the decomposition is written as
$$ P A = L,U, $$
or, when both row and column permutations are used, as
$$ P A Q = L,U, $$
where $Q$ is a column permutation matrix.
Existence and Uniqueness
- For a nonsingular (invertible) matrix $A$ that admits an LU decomposition without pivoting, the factorization is unique if the unit‑diagonal convention for $L$ is adopted.
- Not every matrix admits an LU decomposition without pivoting; partial pivoting (row exchanges) is generally required for matrices that are singular or poorly conditioned. With appropriate pivoting, a decomposition exists for any square matrix.
Algorithms
- Doolittle algorithm – Produces an $L$ with unit diagonal entries and computes $U$ directly.
- Crout algorithm – Produces a $U$ with unit diagonal entries and computes $L$ directly.
- Cholesky decomposition – A special case for symmetric, positive‑definite matrices, where $A = L L^{T}$ with $L$ lower triangular.
- Block LU decomposition – Extends the method to block matrices, facilitating efficient implementation on modern computer architectures.
All of these algorithms are variants of Gaussian elimination, reorganized to separate the multipliers (stored in $L$) from the transformed rows (forming $U$).
Applications
- Solving linear systems – Once $A = L U$ is known, the system $A x = b$ can be solved by forward substitution with $L$ followed by backward substitution with $U$.
- Computing determinants – For a triangular matrix, the determinant is the product of its diagonal entries; thus $\det(A) = \det(L)\det(U)$. With unit diagonal $L$, $\det(A) = \prod_{i} U_{ii}$.
- Inverting matrices – Inverse computation can be performed efficiently by solving $A X = I$ using the LU factors.
- Eigenvalue algorithms – Iterative methods such as the QR algorithm employ LU factorizations as intermediate steps.
- Numerical analysis – LU decomposition underlies many numerical linear‑algebra libraries (e.g., LAPACK, MATLAB, NumPy) due to its computational efficiency and stability when combined with pivoting.
Historical Notes
The concept of factorizing matrices into triangular components traces back to early work on Gaussian elimination in the 19th century. The formal naming of “LU decomposition” and systematic algorithmic development emerged in the mid‑20th century, notably with contributions from mathematicians such as Alan J. Wilkinson and the development of computer‑based linear‑algebra software.
References
- G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, 2013.
- J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford University Press, 1965.
- T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM, 2006.
(For further reading, consult standard texts on numerical linear algebra.)
