Elementary Matrices and LU Factorization

Elimination, from echelon form, can be recorded as a factorization $A = LU$: $L$ is lower triangular and stores the multipliers, $U$ is the upper triangular echelon form. Computers solve most systems this way. The idea uses inverses of very simple matrices.

Row operations are matrix multiplications

An elementary matrix is the identity with one row operation done to it. Multiplying $A$ on the left by an elementary matrix $E$ performs that same operation on $A$. For example, with $E = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$, the product $EA$ is $A$ with $R_2 \to R_2 - 2R_1$. Each $E$ is invertible, and $E^{-1}$ is the opposite operation (here, put $+2$ in the same spot).

Why it works

Why does $L$ just hold the multipliers? If elimination uses only replacements of a lower row by a multiple of a higher one, then $E_k \cdots E_2E_1A = U$, so $A = E_1^{-1}E_2^{-1}\cdots E_k^{-1}U$. Each $E_i^{-1}$ is lower triangular with one entry below the diagonal, and when you multiply them in this order the entries simply drop into place without interfering. So $L$ has $1$s on the diagonal and, in position $(i, j)$, the multiplier $\ell_{ij}$ that was subtracted: $R_i \to R_i - \ell_{ij}R_j$.

Worked example: Finding L and U

Factor $A = \begin{bmatrix} 2 & 1 & 1 \\ 4 & -1 & 3 \\ -2 & 5 & 2 \end{bmatrix}$ as $LU$.

$R_{2} \to R_{2} - 2R_{1}$ (multiplier $\ell_{21} = 2$) and $R_{3} \to R_{3} + R_{1}$ (multiplier $\ell_{31} = -1$): $\begin{bmatrix} 2 & 1 & 1 \\ 0 & -3 & 1 \\ 0 & 6 & 3 \end{bmatrix}$.
$R_{3} \to R_{3} + 2R_{2}$ (multiplier $\ell_{32} = -2$, since we subtracted $-2$ times row 2): $U = \begin{bmatrix} 2 & 1 & 1 \\ 0 & -3 & 1 \\ 0 & 0 & 5 \end{bmatrix}$.
$L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -2 & 1 \end{bmatrix}$.
Check: $LU = \begin{bmatrix} 2 & 1 & 1 \\ 4 & -1 & 3 \\ -2 & 5 & 2 \end{bmatrix} = A$. ✓

Answer: $L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -2 & 1 \end{bmatrix}$, $U = \begin{bmatrix} 2 & 1 & 1 \\ 0 & -3 & 1 \\ 0 & 0 & 5 \end{bmatrix}$

Elimination on $A$ without swaps. The log lists the multipliers; the final matrix is $U$.

Solving with LU

To solve $A\mathbf{x} = \mathbf{b}$, write it as $L(U\mathbf{x}) = \mathbf{b}$ and solve two triangular systems: first $L\mathbf{y} = \mathbf{b}$ from the top down, then $U\mathbf{x} = \mathbf{y}$ from the bottom up. When many right-hand sides share the same $A$ (common in engineering), the elimination is done once and each new $\mathbf{b}$ costs only the two quick triangular solves.

Worked example: Two triangular solves

Use the factorization above to solve $A\mathbf{x} = \begin{bmatrix} 3 \\ 11 \\ -3 \end{bmatrix}$.

$L\mathbf{y} = \mathbf{b}$, top down: $y_1 = 3$; then $2y_1 + y_2 = 11$ gives $y_2 = 5$; then $-y_1 - 2y_2 + y_3 = -3$ gives $y_3 = -3 + 3 + 10 = 10$.
$U\mathbf{x} = \mathbf{y}$, bottom up: $5x_3 = 10$ gives $x_3 = 2$; $-3x_2 + x_3 = 5$ gives $x_2 = -1$; $2x_1 + x_2 + x_3 = 3$ gives $x_1 = 1$.
Check in the original second equation: $4(1) - (-1) + 3(2) = 11$. ✓

Answer: $\mathbf{x} = (1, -1, 2)$

If a zero pivot forces a row swap, the factorization becomes $PA = LU$, where the permutation matrix $P$ records the swaps.

Key idea

Elimination without swaps is the factorization $A = LU$: $U$ is the echelon form and $L$ is unit lower triangular, holding the multipliers. Solve $A\mathbf{x} = \mathbf{b}$ by $L\mathbf{y} = \mathbf{b}$, then $U\mathbf{x} = \mathbf{y}$.

Elementary Matrices and LU Factorization

Row operations are matrix multiplications

Solving with LU

Practice

Builds on

Leads to

Sources and further reading