LU decomposition — algorithm, applications: Foundations

This page assumes you have seen nothing. Every symbol the parent note throws at you — $A$ , $L$ , $U$ , $ℓ_{ij}$ , $x$ , $b$ , the multiplier $m_{ik}$ , "pivot", "triangular", $det$ , $P$ — is built here, from a picture, in an order where each brick rests on the last.

1. A number, a list of numbers, a grid of numbers

Before any letter with fancy subscripts, three objects.

Figure — LU decomposition — algorithm, applications

Figure 1 — Scalar vs vector vs matrix. One yellow dot is a scalar (a lone number,

7

). A blue column of dots joined by a stroke is a vector (a stacked list,

x_{1}

over

x_{2}

). A green

2 \times 2

block of dots is a matrix (the full grid). Read left to right: complexity grows from one number, to a list, to a grid.

2. Reading a matrix: rows, columns, and the subscript $a_{ij}$

Every entry of a grid needs an address.

Figure 2 — The address $a_{ij}$ . A $3 \times 3$ grid of blue dots each labelled with its address. The yellow arrows show the two counting directions: rows counted downward, columns counted rightward. The red dot marks $a_{21}$ — row $2$ , column $1$ — showing the "row first, column second" rule in action.

In the figure, $a_{21}$ (highlighted red) sits in row 2, column 1. This ordering never changes: row first, column second. The parent note writes $a_{ik}$ and $u_{ij}$ and $ℓ_{ij}$ — all of them obey this same rule.

3. The diagonal, and what "triangular" means

Draw the line from the top-left corner down to the bottom-right corner. The entries this line passes through — $a_{11}, a_{22}, a_{33}, \dots$ — are the diagonal.

Figure 3 — Lower vs upper triangular. Left grid: non-zero entries (marked $*$ ) fill the lower-left triangle, zeros sit above the yellow dashed diagonal — lower triangular. Right grid: non-zeros fill the upper-right triangle, zeros sit below the diagonal — upper triangular. The dashed yellow line in each is the diagonal that splits the grid in half.

The figure shows both. The word "triangular" is literal: the non-zero numbers fill a triangle, one half of the grid.

4. Multiplying a matrix by a vector — what $A x$ actually does

$A x$ is not "multiply everything by everything". It has a precise recipe.

For the $2 \times 2$ example ( $n = 2$ ): $(2437) (x_{1} x_{2}) = (2 x_{1} + 3 x_{2} 4 x_{1} + 7 x_{2}) .$

Matrix times matrix — for us the product $LU$ of the two half-grids defined in Section 3 — follows the same row-walks-column rule, done for every column of the second matrix. That is why the parent's check $LU = A$ makes sense: multiply the two half-grids back together and you rebuild the original.

5. The pivot and the multiplier — the two numbers elimination produces

Now the two starring symbols of the whole topic.

Figure 4 — Pivot and multiplier in action. The green dot is the pivot $a_{11} = 2$ ; the red dot below it is the entry $a_{21} = 4$ we want to erase. The yellow arrow points from pivot to target. The formula $m_{21} = a_{21} / a_{11} = 4/2 = 2$ shows the ratio, and the bottom line shows the row operation $(4, 7) - 2 (2, 3) = (0, 1)$ that zeros the red entry.

The punchline the parent relies on: these multipliers, written into a grid with $1$ 's on the diagonal by the rule above, are $L$ . The pivots, sitting on the diagonal of the cleaned-up grid, are the diagonal of $U$ . Nothing extra is computed — you just save what you already did. That saving is Gaussian Elimination with a memory, which is the whole idea of LU.

6. The determinant $det A$ and why pivots give it

7. The permutation matrix $P$ — when a row must move

Sometimes the pivot lands on a $0$ . You cannot divide by zero, so you swap rows to bring a good pivot up. Recording which rows swapped is the job of $P$ .

That is why pivoting turns $A = LU$ into $P A = LU$ . Full detail lives in Permutation Matrices.

Intuition Beyond zero pivots: partial pivoting and stability

Swapping is not only for an exactly zero pivot. Even a tiny pivot is dangerous: dividing by a number near $0$ makes the multiplier $m_{ik} = a_{ik}^{(k)} / a_{k k}^{(k)}$ enormous, and enormous multipliers magnify the small rounding errors a computer always carries — the answer can come out badly wrong. The standard cure is partial pivoting: before eliminating column $k$ , look down that column at all rows from $k$ downward, find the entry with the largest absolute value, and swap that row up to become the pivot. This keeps every multiplier at size $\leq 1$ , so errors never blow up. In practice, LU is always done with partial pivoting, giving $P A = LU$ ; plain $A = LU$ is the ideal case where no swap happened to be needed. When the matrix is symmetric positive-definite, the split simplifies even further into Cholesky Decomposition (no pivoting needed), and the inverse of $A$ can be assembled solve-by-solve as in Matrix Inverse.

a_{ij}

point to?

The entry in row

i

, column

j

— row first, column second.

What does

n

stand for?

The common count of rows and columns of a square matrix (

n \times n

); also the length of

x

and

b

What are

x

and

b

A x = b

x

is the unknown vector we solve for;

b

is the known right-hand-side vector — both length

n

Why must

A

be square for LU?

You need one diagonal pivot per column, which requires equal row and column counts (

n \times n

Where do the diagonal entries of a matrix live?

On the line from top-left to bottom-right, where row number equals column number (

a_{ii}

What makes a matrix lower triangular?

Every entry above the diagonal is zero.

What does "unit lower triangular" add to that?

The diagonal entries are all

1

How do you compute entry

i

A x

Walk row

i

A

against

x

, multiply matched pairs, sum them.

Why is

A x = b

the same as a system of equations?

Each row of the product spells out one equation exactly.

What range does the stage index

k

run over?

k = 1, \dots, n - 1

— one stage per column, stopping one short of

n

What is a pivot?

The diagonal anchor entry

a_{k k}^{(k)}

you divide by to eliminate the column below it; the diagonal of

U

What is the multiplier

m_{ik}

and why a ratio?

m_{ik} = a_{ik}^{(k)} / a_{k k}^{(k)}

; it is the only number that makes row

_{i} - m_{ik}

row

_{k}

zero out position

(i, k)

How are the entries of

L

assembled?

ℓ_{ii} = 1

ℓ_{ik} = m_{ik}

for

i > k

, and

ℓ_{ik} = 0

for

i < k

How do you read

det A

off the factors (no swaps)?

Product of the pivots

\prod_{i} u_{ii}

(since

det L = 1

How does a row swap change

det A

It multiplies by

sign (P) = (- 1)^{# swaps}

, so

det A = sign (P) \prod_{i} u_{ii}

What does a permutation matrix

P

do?

Shuffles the rows of

A

(identity with rows swapped), used when a pivot is zero or tiny.

What is partial pivoting and why do it?

Swap the row with the largest-magnitude entry into the pivot position, keeping every multiplier

\leq 1

so rounding errors do not blow up.

Connections

Gaussian Elimination — the elimination process that spits out pivots and multipliers.
Triangular Systems & Substitution — why triangular grids solve instantly.
Determinants — the product-of-pivots shortcut.
Permutation Matrices — the row-swap bookkeeping $P$ .
Matrix Inverse — assembling $A^{- 1}$ column by column from $L, U$ .
Cholesky Decomposition — the symmetric positive-definite special case.
LU decomposition — algorithm, applications — the parent topic these foundations feed.

Foundations — LU decomposition — algorithm, applications