Rank-nullity theorem — proof: Visual walkthrough

4.5.14 · D2 · Maths › Linear Algebra (Full) › Rank-nullity theorem — proof

Hum sab kuch ek idea se banayenge: ek linear map ek machine hai jo $V$ space se vectors khaati hai aur $W$ space mein vectors ugalti hai.

Step 0 — Vector space, map, aur "dimension" kya hota hai?

KYA. Ek vector space $V$ arrows ka ek collection hai jinhein aap add aur stretch kar sakte ho. Uski dimension $dim V = n$ un independent directions ki sankhya hai jo har arrow tak pahunchne ke liye chahiye — jaise $3$ axes ek room ke har point tak pahunchte hain. Dekho Dimension of a Vector Space.

Ek linear map $T : V \to W$ ek machine hai: ek arrow $v$ andar daalo, arrow $T (v)$ bahar aata hai. "Linear" matlab hai yeh adding aur stretching ko respect karta hai — koi bending nahi.

YAHAN SE KYUN SHURU KAREIN. Baad ke har symbol ( $ker$ , $im$ , rank, nullity) is machine ke baare mein ek fact hai. Jab tak hum machine ko dekh nahi sakte, tab tak inhe use nahi kar sakte.

PICTURE. Baayein taraf, input room $V$ with $n = 3$ axes. Daayein taraf, output room $W$ . Unke beech ek arrow machine $T$ hai.

Step 1 — Kernel: woh directions jinhe machine crush kar deti hai

KYA. Kernel har woh input arrow hai jo zero arrow ban ke bahar aata hai: $ker T = {input arrow v \in V : uska output T (v) = zero arrow 0} .$ Uski dimension nullity hai: $nullity (T) = dim (ker T) = k$ . Dekho Kernel and Image of a Linear Map.

KYUN. Input ki kuch directions flatten ho jaati hain — machine unhe bhool jaati hai. Hum pehle inhe identify karna chahte hain, kyunki yeh baaki sab se bilkul alag behave karti hain.

PICTURE. Input arrows ka ek poora plane (2 directions, to yahan $k = 2$ thoda chhota imagine karo) sab $W$ mein ek dot $0$ par land karta hai. Woh plane kernel hai.

Is crushed part ke liye hum ek basis ka naam rakhte hain: ${k independent crushed directions u_{1}, \dots, u_{k}} basis of ker T .$

Step 2 — $V$ ki poori basis tak extend karo

KYA. $u_{i}$ sirf crushed part ko describe karte hain. Hum naye directions add karte hain jab tak poore $V$ tak nahi pahunch jaate: ${kernel directions u_{1}, \dots, u_{k}, "survivors" v_{1}, \dots, v_{n - k}} basis of V .$

YEH TOOL KYUN. Basis Extension Theorem promise karta hai: kisi bhi subspace ki koi bhi basis ko poori space ki basis mein badhaaya ja sakta hai. Hum ise isliye use karte hain kyunki yeh $V$ ko saaf tarike se do labelled pileon mein kaatta hai — $k$ kernel directions aur $n - k$ nayi wali — bina kisi overlap ke aur kuch chhute bhi nahi. Nayi vectors exactly $n - k$ hain kyunki $n$ -dimensional space ki basis mein hamesha $n$ elements hote hain.

PICTURE. Kernel plane (blue) plus nayi orange arrows $v_{1}, \dots, v_{n - k}$ us plane se bahar nikalte hue, mil ke poora input room bharte hue.

Step 3 — Survivors ko push karo: image se milo

KYA. Har survivor par machine apply karo aur yeh set lo: $B = {survivors ke outputs T (v_{1}), \dots, T (v_{n - k})} \subseteq W .$ Image $im T = {T (v) : v \in V}$ woh sab hai jo machine produce kar sakti hai; uski dimension rank hai. Dekho Rank of a Matrix (row vs column space).

KYUN. Kernel arrows sab mar jaate hain ( $T (u_{i}) = 0$ ), to outputs banane ke liye sirf yahi survivor-outputs kaam aa sakte hain. Hamara poora plan hai: dikhao ki $B$ image ki basis hai. Agar hai, to $rank = n - k$ aur theorem nikal aata hai.

PICTURE. Baayein orange survivors daayein orange output arrows mein map hote hain; blue kernel plane dot $0$ par collapse ho jaata hai.

Basis hone ke liye $B$ ko do kaam karne hain: image ko span karna (Step 4) aur independent hona (Step 5).

Step 4 — $B$ image ko span karta hai (har output survivor-outputs ka mix hai)

KYA. Koi bhi output $w = T (v)$ lo. Uske input $v$ ko poori basis mein likho, phir push karo:

\ \xrightarrow{\ T\ }\ w=\underbrace{\sum a_i\,T(u_i)}_{=\,0\ \text{(crushed!)}}+\sum_{j=1}^{n-k} b_j\,T(v_j).$$ Kyunki har $T(u_i)=0$, pehla sum khatam ho jaata hai: $$w=\sum_{j=1}^{n-k} b_j\,T(v_j).$$ **KYUN.** Yeh kehta hai koi bhi output *sirf* $T(v_j)$ se banta hai — kernel literally kuch contribute nahi karta. To $B$ image ke har point tak pahunchta hai: yeh **spans** karta hai. ✓ **PICTURE.** Input arrow $v$ ek blue (kernel) shadow aur ek orange (survivor) part mein split hota hai; sirf orange part survive karke $w$ banata hai. ![[deepdives/dd-maths-4.5.14-d2-s05.png]] > [!intuition] Kernel koi kiraya nahi deta > Output banate waqt, kernel directions ke coefficients $a_i$ waste hote hain — woh zero se multiply hote hain. Sirf $b_j$ matter karte hain. Yahi "crushed" ka visual matlab hai. --- ## Step 5 — $B$ independent hai (survivors secretly collapse nahi hote) **KYA.** Maano survivor-outputs ka koi mix zero hai: $$\sum_{j=1}^{n-k} c_j\,T(v_j)=0 \ \xRightarrow{\ \text{linearity}\ }\ T\!\Big(\underbrace{\sum_j c_j v_j}_{\text{koi input arrow}}\Big)=0 \ \Longrightarrow\ \sum_j c_j v_j\in\ker T.$$ Woh input arrow kernel mein hai, to woh $u_i$ ka koi mix hai: $$\sum_{j} c_j v_j=\sum_i d_i u_i \ \Longrightarrow\ \underbrace{\sum_j c_j v_j-\sum_i d_i u_i=0}_{\text{FULL basis mein ek dependence}}.$$ Lekin poora set $\{u_1,\dots,u_k,v_1,\dots,v_{n-k}\}$ ek basis hai — **independent** — to har coefficient $0$ pe force ho jaata hai: $$c_1=\dots=c_{n-k}=0\quad(\text{aur sab }d_i=0).$$ **KYUN.** $T(v_j)$ ka zero-combination humein *kernel mein* kheench ke le jaata hai; lekin survivors uske *bahar* chune gaye the. Iska ek hi rasta hai — sab $c_j=0$ — yahi independence ki definition hai. ✓ **KYUN YEH AUR "BAS $v_j$ KI INDEPENDENCE QUOTE KARO" NAHI:** ek linear map independent inputs ko collapse kar sakta hai. Hum yeh assume nahi kar sakte ki outputs independent rahenge — humein kernel mein jaana pada aur poori basis use karni padi ise prove karne ke liye. Yahi poore theorem ka subtle central point hai. **PICTURE.** Do orange survivor-outputs; red dashed loop attempted collapse dikhata hai, aur "pull-back arrow" dikhata hai yeh blue kernel mein land kar raha hai, independence ko contradict karta hai jab tak sab $c_j=0$ na hon. ![[deepdives/dd-maths-4.5.14-d2-s06.png]] --- ## Step 6 — Count karo aur conclude karo **KYA.** $B=\{T(v_1),\dots,T(v_{n-k})\}$ spans karta hai (Step 4) aur independent hai (Step 5), to yeh exactly $n-k$ elements ke saath **image ki basis** hai. Isliye $$\operatorname{rank}(T)=\underbrace{n-k}_{\dim\operatorname{im}T},\qquad \operatorname{nullity}(T)=\underbrace{k}_{\dim\ker T},$$ $$\boxed{\ \operatorname{rank}(T)+\operatorname{nullity}(T)=(n-k)+k=n=\dim V\ }.$$ **KYUN.** Har input direction exactly ek pile mein sort hui — crushed ($k$) ya kept ($n-k$). Koi dimension kho nahi gayi ya bani nahi; sirf *label* kiya gaya. **PICTURE.** Length $n$ ki ek single bar jo blue segment (nullity $k$) aur orange segment (rank $n-k$) mein split hai — dimensions ka conservation, draw kiya hua. ![[deepdives/dd-maths-4.5.14-d2-s07.png]] --- ## Step 7 — Edge aur degenerate cases Koi bhi scenario undrawn mat chhodna. Neeche "iso" [[Invertible Linear Maps and Isomorphisms]] refer karta hai aur free-variable count [[Solving Linear Systems — free variables count]] ko. **Case A — kernel sab kuch hai ($k=n$).** Zero map $T\equiv 0$ *poore* $V$ ko crush karta hai. Tab $\operatorname{nullity}=n$, aur $B$ **empty** hai (koi survivors nahi), to $\operatorname{rank}=0$. Check: $0+n=n$. ✓ Empty set zero image $\{0\}$ ki ek valid basis hai. **Case B — kernel trivial hai ($k=0$).** Kuch crush nahi hota: $\ker T=\{0\}$, $\operatorname{nullity}=0$. Har direction survive karta hai, $\operatorname{rank}=n$. Map **injective** hai, aur agar $\dim W=n$ bhi hai to yeh isomorphism hai. Check: $n+0=n$. ✓ **Case C — $2\times3$ matrix (real numbers).** $A=\begin{pmatrix}1&2&3\\2&4&6\end{pmatrix}$ as $T:\mathbb R^3\to\mathbb R^2$. Row 2 $=2\times$ row 1, to $\operatorname{rank}=1$. Theorem hume $\operatorname{nullity}=3-1=2$ **free mein de deta hai** — $x_1+2x_2+3x_3=0$ mein $2$ free variables se match karta hai. **PICTURE.** Length $n$ ki teen chhoti bars: sab-blue (Case A), sab-orange (Case B), aur mixed $1/2$ split (Case C). ![[deepdives/dd-maths-4.5.14-d2-s08.png]] > [!recall]- Edge cases khud check karo > $\mathbb R^3$ par zero map: nullity ::: $3$ (rank $0$). > $\mathbb R^3$ par identity map: rank ::: $3$ (nullity $0$). > Rank-1 map $\mathbb R^3\to\mathbb R^2$: nullity ::: $2$. --- ## Ek-picture summary Sab ek saath: input room $V$ blue **kernel** (crushed to $0$) aur orange **survivors** mein split hoti hai; survivors $W$ mein image ki genuine basis mein map hote hain; dimension bar dikhata hai $k+(n-k)=n$. ![[deepdives/dd-maths-4.5.14-d2-s09.png]] > [!recall]- Feynman retelling — poora walkthrough seedhe alfaazon mein > Input space ko $n$ directions wale ek room ki tarah socho. Hamari machine $T$ un directions ke saath do cheezein karti hai aur kuch nahi. Kuch directions woh **ignore** karti hai — unke saath push karo aur output kabhi nahi hilta; un sab ko ek flat "kernel" pile mein ikattha karo jiska size $k$ hai. Baaki $n-k$ directions main us pile ke *bahar* se chunti hoon (basis-extension theorem mujhe room ki basis is tarah complete karne deta hai). Jab main un survivors ko machine se push karti hoon, do achchi cheezein hoti hain. Pehla, woh **har** possible output banate hain — kyunki kisi bhi output ka kernel-part zero se multiply hoke mar jaata hai, sirf survivor-parts bachte hain. Doosra, woh outputs **bina waste ke** banate hain — agar koi survivor-outputs cancel hote, peeche trace karne par hum kernel mein aa jaate, lekin survivors uske bahar rehte hain, to kuch cancel nahi hota. To survivor-outputs image describe karne ka ek perfect, minimal set hai: unki count $n-k$ hi rank *hai*. Crushed pile $k$ wapas jodon aur tumhe sab $n$ directions mil jaati hain. Kuch kho nahi gaya, kuch banaya nahi gaya — $n$ input dimensions sirf "crushed" aur "kept" mein sort ki gayi. Wahi sorting rank–nullity theorem *hai*. > [!mnemonic] Yaad rakhne ki ek line > **Crushed + Kept = Saara input.** ($k + (n-k) = n$.) --- Parent: [[Rank-nullity theorem — proof]]