LU Factorization — Mathematics Knowledge System

Overview

LU factorization decomposes a square matrix A into a lower triangular matrix L and an upper triangular matrix U, so that A = LU (or A = PLU with a permutation matrix P for numerical stability). This factorization is the foundation of Gaussian elimination and enables efficient solution of linear systems, computation of determinants, and matrix inversion.

Intuition

Gaussian elimination — the process of using row operations to reduce a matrix to upper triangular form — is exactly LU factorization. Each elimination step corresponds to multiplying on the left by a lower triangular matrix. L records all the multipliers used during elimination, and U is the upper triangular result. Once you have A = LU, solving Ax = b reduces to two triangular solves, which are fast.

Formal Definition

Definition

Given an n×n matrix A, the LU factorization (with partial pivoting) is:

A = LU, \quad L \text{ lower triangular with 1s on diagonal}, \quad U \text{ upper triangular}

LU factorization

PA = LU \quad (\text{with partial pivoting, } P \text{ a permutation matrix})

PLU factorization

\det(A) = \det(L)\det(U) = \prod_{i=1}^n u_{ii} \quad (\pm 1 \text{ from permutation})

Determinant from LU

Notation

Notation	Meaning
$L$	Lower triangular matrix with 1s on the diagonal
$U$	Upper triangular matrix
$P$	Permutation matrix for partial pivoting

Properties

Existence

\text{Every invertible matrix has an LU factorization with partial pivoting (PA = LU).}

System solving

\text{To solve } Ax=b: \text{ solve } Ly=b \text{ by forward substitution, then } Ux=y \text{ by back substitution.}

Determinant

\det(A) = (\pm 1)\prod_{i=1}^n u_{ii} \text{, sign from permutation.}

Uniqueness

\text{If all leading submatrices of } A \text{ are nonsingular, LU is unique.}

Applications

Real-world · Engineering

Solving large sparse linear systems in finite element analysis. LU factorization of the stiffness matrix is done once; then multiple right-hand sides can be solved cheaply.

Worked Examples

1
Eliminate column 1: use pivot a_{11}=2. Multipliers: l_{21}=4/2=2, l_{31}=8/2=4.
$R_2 \leftarrow R_2 - 2R_1: \quad [0,1,1]; \quad R_3 \leftarrow R_3 - 4R_1: \quad [0,3,5]$
2
Eliminate column 2: pivot a_{22}=1. Multiplier: l_{32}=3/1=3.
$R_3 \leftarrow R_3 - 3R_2: \quad [0,0,2]$
3
U is the upper triangular result; L records multipliers.
$L = \begin{pmatrix}1&0&0\\2&1&0\\4&3&1\end{pmatrix}, \quad U = \begin{pmatrix}2&1&1\\0&1&1\\0&0&2\end{pmatrix}$
4
Verify: L U = A.
$LU = \begin{pmatrix}2&1&1\\4&3&3\\8&7&9\end{pmatrix} = A \checkmark$

✓ Answer

L = [[1,0,0],[2,1,0],[4,3,1]], U = [[2,1,1],[0,1,1],[0,0,2]].

Practice Problems

Mediumfree response

Find the LU factorization of A = [[1,2],[3,4]].

Mediumfree response

Using LU factorization, find det([[2,1],[4,3]]).

Common Mistakes

Common Mistake

LU factorization always exists without pivoting.

Without pivoting, LU fails if a zero pivot is encountered (even for invertible matrices). Partial pivoting (PLU) is needed for numerical stability.

Quiz

Summary

LU factorization writes A = LU with L lower triangular (diagonal 1s) and U upper triangular.
It encodes Gaussian elimination: L records multipliers, U is the reduced form.
Solving Ax = b via LU: forward-substitute Ly = b, then back-substitute Ux = y.
det(A) = product of diagonal entries of U (times ±1 for row swaps).
Partial pivoting (PA = LU) is needed for numerical stability in practice.

References

WebsiteWikipedia — LU decomposition