LU Decomposition — Definition, Formula & Examples

LU Decomposition is a way of breaking a square matrix

A

into the product of a lower triangular matrix

L

and an upper triangular matrix

U

, so that

A = LU

. This factorization makes solving systems of linear equations faster, especially when you need to solve multiple systems with the same coefficient matrix.

Given a square matrix $A \in \mathbb{R}^{n \times n}$ , an LU decomposition (when it exists) expresses $A$ as the product $A = LU$ , where $L$ is a lower triangular matrix with ones on its diagonal (unit lower triangular) and $U$ is an upper triangular matrix. The entries of $L$ and $U$ are determined by Gaussian elimination without row swaps; if row swaps are needed, a permutation matrix $P$ is introduced so that $PA = LU$ .

Key Formula

A = LU

Where:

$A$ = The original square matrix being decomposed
$L$ = Lower triangular matrix (1s on the diagonal)
$U$ = Upper triangular matrix (the row-echelon form of A)

How It Works

You perform Gaussian elimination on

A

to reach an upper triangular form

U

. Each multiplier used to eliminate an entry below the pivot is stored in the corresponding position of

L

, and the diagonal of

L

is set to 1. To solve

A\mathbf{x} = \mathbf{b}

, you first solve

L\mathbf{y} = \mathbf{b}

by forward substitution, then solve

U\mathbf{x} = \mathbf{y}

by back substitution. Because

L

and

U

are triangular, each substitution step is fast —

O(n^2)

instead of

O(n^3)

Worked Example

Problem: Find the LU decomposition of A = [[2, 1], [6, 4]].

Step 1: Eliminate the entry below the pivot in column 1. The multiplier is 6/2 = 3. Subtract 3 times row 1 from row 2.

R_2 \leftarrow R_2 - 3R_1: \quad [6,\;4] - 3[2,\;1] = [0,\;1]

Step 2: The upper triangular matrix U is the result of elimination, and L stores the multiplier 3 below the diagonal.

L = \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix}, \quad U = \begin{bmatrix} 2 & 1 \\ 0 & 1 \end{bmatrix}

Step 3: Verify by multiplying L and U.

LU = \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix}\begin{bmatrix} 2 & 1 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 6 & 4 \end{bmatrix} = A \;\checkmark

Answer: L = [[1, 0], [3, 1]] and U = [[2, 1], [0, 1]].

Why It Matters

LU Decomposition is essential in numerical linear algebra and scientific computing. Engineers and physicists use it to solve large systems of equations efficiently — for instance, in finite element analysis or circuit simulation, where the same coefficient matrix appears with many different right-hand sides.

Common Mistakes

Mistake: Assuming every square matrix has an LU decomposition without row swaps.

Correction: If a zero pivot is encountered during elimination, you must introduce a permutation matrix P so that PA = LU. Not every matrix can be factored as A = LU directly.