LU decomposition — algorithm, applications

WHAT is it?

The entries of $U$ are exactly the pivots of Gaussian elimination, and the entries of $L$ are exactly the multipliers you used to eliminate below each pivot.

HOW: deriving the algorithm from scratch

Gaussian elimination clears the column below each pivot by row operations. A row operation "subtract $m$ times row $k$ from row $i$ " is itself a matrix multiplication on the left.

To eliminate entry $a_{ik}$ using pivot $a_{kk}$ , the multiplier is $m_{ik} = \frac{a_{ik}}{a_{kk}} \quad(\text{after previous steps}).$ The elementary matrix that does "row $_i \leftarrow$ row $_i - m_{ik}\,$ row $_k$ " is the identity with $-m_{ik}$ in position $(i,k)$ .

Figure — LU decomposition — algorithm, applications

Worked Example 1 — basic factorisation

Factor $A=\begin{pmatrix} 2 & 3 \\ 4 & 7 \end{pmatrix}.$

Step 1. Pivot $=2$ . Multiplier $m_{21}=\dfrac{4}{2}=2$ . Why this step? We need to kill the $4$ below the first pivot; $m_{21}=a_{21}/a_{11}$ .

Step 2. Row $_2 \leftarrow$ Row $_2 - 2\cdot$ Row $_1$ : $(4,7)-(4,6)=(0,1)$ . So $U=\begin{pmatrix}2&3\\0&1\end{pmatrix}$ . Why? This produces the upper-triangular $U$ with pivots on its diagonal.

Step 3. Put the multiplier into $L$ : $L=\begin{pmatrix}1&0\\2&1\end{pmatrix}$ . Why? $L$ records how we got to $U$ , with $+m_{21}$ .

Check: $LU=\begin{pmatrix}1&0\\2&1\end{pmatrix}\begin{pmatrix}2&3\\0&1\end{pmatrix}=\begin{pmatrix}2&3\\4&7\end{pmatrix}=A.$ ✓

Worked Example 2 — using LU to solve $A\mathbf{x}=\mathbf{b}$

Solve $A\mathbf{x}=\mathbf{b}$ with the $A$ above and $\mathbf{b}=\begin{pmatrix}8\\18\end{pmatrix}$ .

Forward: $L\mathbf{y}=\mathbf{b}$ : $y_1=8,\qquad 2y_1+y_2=18\Rightarrow y_2=18-16=2.$ Why? Row 1 gives $y_1$ instantly; substitute into row 2.

Back: $U\mathbf{x}=\mathbf{y}$ : $2x_1+3x_2=8,\quad x_2=2 \Rightarrow 2x_1=8-6\Rightarrow x_1=1.$ Answer: $\mathbf{x}=(1,2)^\top$ . Why fast? No new elimination — just substitution.

Worked Example 3 — a $3\times3$ and the pivot warning

$A=\begin{pmatrix}1&1&1\\2&3&5\\4&6&8\end{pmatrix}.$

$m_{21}=2,\ m_{31}=4$ . After clearing column 1: $\begin{pmatrix}1&1&1\\0&1&3\\0&2&4\end{pmatrix}.$
New pivot $=1$ (row 2). $m_{32}=2$ . Clear: row $_3-2\cdot$ row $_2=(0,0,-2)$ . $U=\begin{pmatrix}1&1&1\\0&1&3\\0&0&-2\end{pmatrix},\quad L=\begin{pmatrix}1&0&0\\2&1&0\\4&2&1\end{pmatrix}.$

Applications (the 80/20 payoff)

Cost (the WHY-it-matters number)

Recall Feynman: explain to a 12-year-old

Imagine a tall messy stack of LEGO instructions. Solving the puzzle once is slow. But if you write down the steps you used (that's $L$ ) and keep the half-built model (that's $U$ ), then next time someone gives you a slightly different goal, you don't start over — you just replay your saved steps backwards and forwards. LU = "save your homework so you never redo it."

What is the LU decomposition of a matrix A?

A factorisation

A=LU

with

L

unit lower triangular (1's on diagonal) and

U

upper triangular.

What do the entries of U represent in Gaussian elimination?

The pivots.

What do the off-diagonal entries of L represent?

The multipliers

m_{ik}=a_{ik}/a_{kk}

used to eliminate below each pivot.

Why is the diagonal of L all ones?

Because L is the product of inverse elementary elimination matrices, each leaving diagonal entries equal to 1.

To solve Ax=b via LU, what are the two steps?

Forward-solve

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

, then back-solve

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

How do you compute det(A) from LU?

\det A=\prod_i u_{ii}

(product of pivots), times

(-1)

per row swap if pivoting used.

When does plain A=LU fail and what's the fix?

When a pivot is zero/tiny; use partial pivoting giving

PA=LU

with permutation matrix P.

Cost of LU factorisation vs one triangular solve?

Factorisation

\approx \tfrac{2}{3}n^3

flops; each solve

\approx n^2

Main advantage of LU over plain Gaussian elimination?

Reuse L,U for many right-hand sides at

O(n^2)

each instead of redoing

O(n^3)

elimination.

Connections

Gaussian Elimination — LU is elimination with the steps remembered.
Permutation Matrices — used in $PA=LU$ for pivoting.
Determinants — product of pivots.
Matrix Inverse — solve against identity columns.
Cholesky Decomposition — symmetric positive-definite special case $A=LL^\top$ .
Triangular Systems & Substitution — the cheap solves.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, LU decomposition ka funda simple hai: jab tum Gaussian elimination karte ho na, tab tum bahut mehnat karte ho rows ko zero karne mein — par answer milne ke baad woh saari mehnat waste ho jaati hai. LU bolta hai "ruk, apna kaam save kar le!" Matrix $A$ ko hum do pieces mein todte hain: $L$ (lower triangular, diagonal pe 1) aur $U$ (upper triangular). $U$ mein tumhare pivots baithte hain, aur $L$ mein woh multipliers ( $m_{ik}=a_{ik}/a_{kk}$ ) jo tumne elimination ke time use kiye the.

Iska sabse bada faayda kab? Jab same matrix $A$ ke saath bahut saare alag-alag $\mathbf{b}$ solve karne ho. Ek baar $L,U$ nikaal lo (cost $\approx \frac{2}{3}n^3$ ), phir har $\mathbf{b}$ ke liye sirf do easy substitution karo: pehle $L\mathbf{y}=\mathbf{b}$ (forward substitution), phir $U\mathbf{x}=\mathbf{y}$ (back substitution) — dono $O(n^2)$ mein. Matlab kaam ek baar, fayda baar-baar.

Determinant bhi free mein mil jaata hai: $\det A = u_{11}u_{22}\cdots u_{nn}$ , yaani pivots ka product. Inverse chahiye? $A\mathbf{x}=\mathbf{e}_i$ solve karo har identity column ke liye, wahi $L,U$ reuse karke.

Ek warning yaad rakhna: agar koi pivot zero ya bahut chhota aa jaaye, toh seedha $A=LU$ fail ho jaata hai (divide by zero / rounding blast). Tab hum rows swap karte hain — isko partial pivoting kehte hain, aur factorisation ban jaata hai $PA=LU$ jahan $P$ ek permutation matrix hai. Bas yeh dhyaan rakho aur LU tumhara dost hai exam mein bhi aur real engineering mein bhi.

LU decomposition — algorithm, applications

WHAT is it?

HOW: deriving the algorithm from scratch

The multiplier matrix

Worked Example 1 — basic factorisation

Worked Example 2 — using LU to solve $A\mathbf{x}=\mathbf{b}$

Worked Example 3 — a $3\times3$ and the pivot warning

Applications (the 80/20 payoff)

Cost (the WHY-it-matters number)

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Linear Algebra (Full)

Connections