# LU decomposition

Put content here**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.

# Parents

* Factorization of matrices