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
**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.