Visual walkthrough — LU decomposition — algorithm, applications

4.5.26 · D2 · Maths › Linear Algebra (Full) › LU decomposition — algorithm, applications

---

Step 0 — Matrix kya hoti hai aur "triangular" ka matlab kya hai?

Neeche shaded triangles dekho: zeros hi in matrices ko solve karna sasta banate hain — ek fact jise hum baad mein use karenge.

Hamaara goal, visually: ek full square grid $A$ lo aur usey ek lower-left triangle $L$ times upper-right triangle $U$ mein split karo.

$A=\underset{\text{lower, 1’s on diagonal}}{\underbrace{L}}\underset{\text{upper, pivots on diagonal}}{\underbrace{U}}$

• $A$ — original grid jo humein di gayi hai.
• $L$ — hamare moves ka record (neeche define hoga).
• $U$ — bacha hua staircase clean up ke baad (neeche define hoga).

---

Step 1 — Ek elimination move, ek arrow ki tarah draw kiya

KYA kiya humne abhi: pivot row ki ek scaled copy ko neeche wali row se subtract kiya.

KYUN exactly yeh number $m_{ik}$? Kyunki hum chahte hain ki entry $a_{ik}$ zero ban jaaye. $a_{ik}$ se $m_{ik}\times a_{kk}$ subtract karne par milta hai $a_{ik}-\frac{a_{ik}}{a_{kk}}\cdot a_{kk}=0$. Ratio specially banaaya gaya hai cancel karne ke liye. Isliye hum pivot se divide karte hain — koi aur number us entry ko ek clean step mein khatam nahi kar sakta.

• $a_{ik}$ — woh troublemaker jo hamein khatam karna hai (row $i$, column $k$).
• $a_{kk}$ — woh pivot jis se hum eliminate kar rahe hain.
• $m_{ik}$ — "troublemaker mein kitni pivot-rows fit hoti hain."

PICTURE: har row ko ek vector samjho. Yeh move row $i$ ko row $k$ ki direction mein slide karta hai jab tak uska $k$-th slot zero na ho jaaye.

---

Step 2 — Ek move ek matrix hai (elementary matrix)

Move "${\text{row}}_i\leftarrow {\text{row}}_i-m_{ik}{\text{row}}_k$" left se ek elementary matrix $E$ se multiply karke achieve hota hai: identity matrix, lekin position $(i,k)$ par $-m_{ik}$ rakha gaya.

$E=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& -m_{31}& 1\end{array}\right)(\text{example: kills entry }(3,1)\text{’s neighbour})$

• Diagonal ke neeche $1$'s matlab "har row ko waise hi rakho..."
• ...sivaay ek $-m_{ik}$ ke, jo keh raha hai "...lekin row $i$ mein se $m_{ik}$ of row $k$ bhi subtract karo."

KYUN minus sign? Kyunki hum subtract karte hain. Yeh sign yaad rakho — yeh next step mein flip hoga, aur woh flip hi asli punchline hai.

PICTURE: identity ek "kuch nahi karo" wala stamp hai; akela off-diagonal number woh ek instruction hai jo humne inject ki.

---

Step 3 — Moves stack karo: $E_k\cdots E_{1}A=U$

KYA: humne moves chain kiye. Right-to-left padho: $E_1$ pehle act karta hai, phir $E_2$, aur aage bhi.

KYUN order matter karta hai: hum pehle column 1 top-to-bottom clear karte hain, phir column 2, aur aage. Har baad wala move already-cleaned columns par kaam karta hai, isliye woh pehle wale kabhi dobara dirty nahi karta. Yahi "no interference" hai jo Step 5 mein $L$ ko simple rakhti hai.

• $A$ — shuru.
• $E_1,E_2,\dots$ — moves jis order mein perform kiye.
• $U$ — finished upper-triangular staircase; iske diagonal entries pivots hain.

PICTURE: dekho $A$ ka lower-left triangle zeros se bharta jaata hai, column by column, jab tak sirf upper staircase bachti hai.

---

Step 4 — Moves undo karo $A$ ko isolate karne ke liye

$A$ ke liye solve karte hain: $A=\underset{\text{call this }L}{\underbrace{E_1^{-1}{E}_2^{-1}\cdots E_k^{-1}}}U.$

• $E_i^{-1}$ — woh move jo $E_i$ ko reverse karta hai.
• Inverses reverse order mein aate hain (last move pehle undo hota hai) — bilkul jaise pehle shoes utaaro phir socks.
• $L$ — hum is poore product ko $L$ naam dete hain. Yahi definition hai; hamen abhi bhi check karna hai ki yeh acha dikhta hai.

Yahan ek sundar fact hai: ek elementary matrix ka inverse wahi same matrix hai jisme sign flip ho. Agar $E$ mein $-m_{ik}$ tha, toh $E^{-1}$ mein $+m_{ik}$ hai.

KYUN sirf sign flip hota hai? Kyunki "row $k$ ka $m_{ik}$ subtract karo" reverse hota hai "row $k$ ka $m_{ik}$ add karo" se — woh ulta move. Koi naya number nahi aata.

---

Step 5 — Multipliers seedha $L$ mein gir jaate hain

KYA: humne saare inverse moves ko multiply kiya aur — magically — ek aisa matrix mila jiske off-diagonal entries literally multipliers hain, $+$ signs ke saath.

KYUN koi messy cross-terms nahi? Step 3 ki ordering ki wajah se. Har $E_i^{-1}$ ka apna single number ek alag $(i,k)$ slot mein hai, aur (kyunki hum top-down, left-to-right jaate hain) inhe multiply karne par kabhi bhi do numbers nahi milte. Toh product bas har $+m_{ik}$ ko uske apne ghar mein deposit kar deta hai. Yahi parent note ka "steel-man check" hai.

• Diagonal par $1$'s: har reverse-move apni row rakhta hai, isliye diagonal sab ones rehti hai. Isliye $L$ ko unit lower triangular kehte hain.
• $m_{21},m_{31},m_{32}$ — multipliers, exactly wahan baithein jahan humne eliminate kiya.

PICTURE: har multiplier jo humne elimination ke dauran compute kiya woh, ek coin ki tarah slot mein girata hai, $L$ ke position $(i,k)$ mein.

Recall

$L$ ke diagonals exactly kyun sab $1$ hain? Kyunki har reverse elimination matrix identity plus ek off-diagonal number hai — yeh diagonal ko kabhi touch nahi karta — isliye inhe multiply karne par har diagonal entry $1$ rehti hai. $L$ ki diagonal par $1$'s kahan se aate hain? ::: Har inverse elementary matrix ke identity part se (moves kabhi ek row ko rescale nahi karte).

---

Step 6 — Dekho ek full $2\times 2$ kaise factor hota hai

Parent ka example lo $A=\left(\begin{array}{cc}2& 3\\ 4& 7\end{array}\right)$.

KYA/KYUN, step by step:

1. Pivot $a_{11}=2$. Neeche ke $4$ ko khatam karne ke liye: $m_{21}=\frac{4}{2}=2$. (Hum pivot se divide karte hain kyunki woh ratio $4$ ko cancel karta hai.)
2. Apply karo ${\text{row}}_2\leftarrow {\text{row}}_2-2{\text{row}}_1$: $(4,7)-(4,6)=(0,1)$. Pivot ke neeche column 1 ab zero hai.
3. Padh lo: $U=\left(\begin{array}{cc}2& 3\\ 0& 1\end{array}\right),L=\left(\begin{array}{cc}1& 0\\ 2& 1\end{array}\right).$ $L$ mein $2$ exactly step 1 ka multiplier hai.

• $U$ ki diagonal $(2,1)$ = do pivots.
• $L$ ka single off-diagonal $2$ = single multiplier.

PICTURE: woh entry jo $4$ thi grid mein $0$ ho jaati hai, aur saath hi saath ek "$2$" $L$ ke slot mein likha jaata hai — ek working matrix se nikalti hai, uska record $L$ mein jaata hai.

---

Step 7 — Degenerate case: ek zero pivot

Example: $A=\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)$ ka pivot $a_{11}=0$ hai. Plain $A=LU$ impossible hai jaise likha hai.

KYUN galat lagta hai: $A$ mein koi bhi problem nahi hai — yeh ek bilkul theek invertible matrix hai. Problem purely yeh hai ki is order ki elimination ne ek zero hit kar liya.

THE FIX — permutation. Pehle do rows swap karo. Swapping khud ek matrix hai, ek permutation matrix $P$: $P=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),PA=\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right),$ jo already upper triangular hai — ab factorable. Generally hume milta hai $PA=LU.$

• $P$ — record karta hai ki humne kaun si rows swap kiin (pure bookkeeping, koi arithmetic nahi lagti).
• Woh swap choose karna jo sabse badi entry ko pivot seat par laaye, partial pivoting kehlaata hai — yeh multipliers ko $\le 1$ size mein rakhta hai aur error control karta hai.

PICTURE: do rows jagah badal leti hain; woh $0$ jo humein rok raha tha pivot seat se bahar ho jaata hai.

Recall Ek row swap determinant ka sign kyun flip karta hai?

Har swap $\det A$ ko $-1$ se multiply karta hai. Toh $\det A=(-1{)}^{\#\text{swaps}}{\prod }_i{u}_{ii}$ — dekho Determinants.

---

Ek-picture summary

Upar ki sab cheezein ek single flow mein compress ho jaati hain: eliminate karo → zeros $U$ mein jaate hain, multipliers $L$ mein jaate hain, swaps $P$ mein jaate hain.

Recall Feynman retelling — poora walkthrough plain words mein

Tum ek messy number grid se start karte ho. Tum ise ek column ek time clean karte ho, pivot row ki scaled copies neeche wali rows se subtract karke — har "kitna subtract kiya?" number ek multiplier hai. Jaise-jaise grid ka lower-left zeros se bharta jaata hai, ek upper staircase $U$ khadi rehti hai (iska diagonal pivots hai). Saath hi, har multiplier jo tumne use kiya ek doosre matrix $L$ ke matching slot mein likha jaata hai, jiska diagonal sab $1$'s hai kyunki tumne kabhi poori row rescale nahi ki. $L$ times $U$ multiply karo aur tumhara original grid wapas milta hai — tumne ise "mere moves ka record" times "tidy leftover" mein split kar diya. Agar koi pivot kabhi zero par land kare, tum divide nahi kar sakte, toh us row ko ek behetar wali se swap karo aur swap yaad rakho ek permutation matrix $P$ mein, jisse milta hai $PA=LU$. Bas itna hai: elimination jo apna homework nahi bhulaati.

---

Connections

• Gaussian Elimination — yeh poora page elimination hi hai, ek picture per move ki speed se.
• Permutation Matrices — $PA=LU$ mein $P$ (Step 7).
• Determinants — $U$ ki diagonal par pivots ka product.
• Matrix Inverse — wahi $L,U$ har identity column ke against reuse karo.
• Triangular Systems & Substitution — kyun $L$ aur $U$ shapes solve karne mein saste hain.
• Cholesky Decomposition — symmetric special case $A=L{L}^{\top }$.