LU decomposition

Definition: The LU decomposition of a square matrix $A$ is a factorization:

$$A = LU$$

where $L$ is a lower triangular matrix with ones on the diagonal (unit lower triangular) and $U$ is an upper triangular matrix.

With pivoting: $PA = LU$, where $P$ is a permutation matrix.

Example:
$$\begin{pmatrix} 2 & 1 \\ 4 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix} \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}$$

Existence: LU decomposition exists iff all leading principal minors of $A$ are nonzero. With partial pivoting ($PA = LU$), it exists for any square matrix.

Uses:

• Solving $Ax = b$ in $O(n^2)$ after $O(n^3)$ factorization
• Computing determinants: $\det(A) = \pm \prod u_{ii}$
• Inverting matrices

Variants: LDU (with diagonal $D$), Cholesky (for symmetric positive-definite), and block LU.