Foundations — LU decomposition (numerical)

This page assumes you know nothing. We will earn every symbol — $A$, $\mathbf{x}$, $\mathbf{b}$, "triangular", $L$, $U$, ${\ell }_{ij}$, $u_{ij}$, $P$ — before the parent note is allowed to use it.

1. What is a "linear system"? ($A\mathbf{x}=\mathbf{b}$)

Suppose two mystery numbers, call them $x_1$ and $x_2$, obey two rules:

$2x_1+3x_2=5,6x_1+13x_2=35.$

Each rule is linear: the unknowns appear only multiplied by fixed numbers and added — no squares, no products of unknowns. Finding the pair $(x_1,x_2)$ that satisfies both is solving a linear system.

Writing the multipliers, unknowns and answers separately gives three objects.

For our example: $A=\left(\begin{array}{cc}2& 3\\ 6& 13\end{array}\right),\mathbf{x}=\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right),\mathbf{b}=\left(\begin{array}{c}5\\ 35\end{array}\right).$

The whole system compresses to the single line $A\mathbf{x}=\mathbf{b}$.

What the picture shows: row $i$ of $A$ paired with $\mathbf{x}$ reproduces the left side of equation $i$; the red column $\mathbf{b}$ holds the answers. So $A\mathbf{x}=\mathbf{b}$ is exactly the two equations, just tidied up.

Row-then-column ordering matters — say it aloud as "row $i$, column $j$" every time.

2. Multiplying a matrix by a vector — the "row dot" picture

Before we can factor $A$ we must know what $A\mathbf{x}$ means as an operation.

Row 1 of our $A$ gives $2x_1+3x_2$ — the left side of equation 1. That is the whole reason the matrix form is faithful.

Matrix-times-matrix ($LU$, coming up) is the same move repeated: entry $(i,j)$ of the product is row $i$ of the first matrix dotted with column $j$ of the second.

What the picture shows: the red row slides across the black column; each aligned pair is multiplied and the products summed to a single output slot. Master this one motion and every LU formula becomes readable.

3. What does "triangular" mean, and why do we crave it?

What the picture shows: black cells = numbers that may be nonzero, white cells = forced zeros. $L$ fills the lower wedge, $U$ the upper wedge; where they overlap (the diagonal) both carry numbers.

Why we crave triangular systems. Look at an upper-triangular system: $\begin{array}{rl}4x_2& =20\\ 2x_1+3x_2& =5\end{array}$ The last equation has only one unknown: $x_2=5$ instantly. Feed it upward and the next equation also has one unknown. No grinding — just read off, one variable at a time. That process is called back substitution (bottom-up for $U$) and its twin forward substitution (top-down for $L$). See Forward and Back Substitution.

So if we could rewrite the hard matrix $A$ as two triangular matrices, solving would become effortless. That wish is precisely LU decomposition.

4. The elimination move (where ${\ell }_{ij}$ is born)

To make a triangle we use the one legal move of Gaussian Elimination:

Example: row 2 is $(6,13)$, row 1 is $(2,3)$. To zero the leading $6$ we need $m=6/2=3$, giving new row 2 $=(6,13)-3(2,3)=(0,4)$. The system is now triangular.

That is why the parent note can say "${\ell }_{ij}$ are the Gaussian-elimination multipliers." Now the phrase carries a picture: a table of the $m$'s.

5. When the move fails: the zero pivot and $P$

If that pivot is $0$, the division explodes. But an all-zero column is not required — sometimes we just picked the rows in an unlucky order. The cure is to swap rows so a nonzero (ideally the largest) number sits on the pivot. See Partial Pivoting.

With swaps the honest statement becomes $PA=LU$: first reorder, then factor. Choosing the biggest pivot also keeps every $|{\ell }_{ij}|\le 1$, which stops rounding errors from ballooning — the accuracy concern of Condition Number and Numerical Stability.

6. Two free gifts these symbols hand us

• Determinant. A triangular matrix's determinant is just the product of its diagonal. Since Doolittle's $L$ has all-1 diagonal ($\det L=1$), $\det A=(-1{)}^{\text{swaps}}{\prod }_i{u}_{ii}$.
• Reuse. Because $L$ and $U$ depend only on $A$ (not on $\mathbf{b}$), a new right-hand side costs only two triangular solves. Factor once, solve many.

Prerequisite map

Equipment checklist

Cover the right side and test yourself. If any answer is fuzzy, reread that section before the parent note.

Connections

• Parent topic ↑
• Gaussian Elimination · Forward and Back Substitution · Partial Pivoting · Permutation Matrices
• Determinants · Condition Number and Numerical Stability · Crout Decomposition · Cholesky Decomposition