Dimension — basis cardinality: Visual walkthrough

4.5.18 · D2 · Maths › Linear Algebra (Full) › Dimension — basis cardinality

Pehli line se pehle, teen words jo hum baar baar use karenge. Har ek Step 1 ki ek picture se juda hua hai.

Hum flat plane mein kaam karenge (paper pe arrows). Sab kuch higher dimensions mein bhi exactly same hoga — pictures banana mushkil ho jaata hai, sochna nahi.

Step 1 — Do teams se miliye

KYA. Hamare paas do teams of arrows hain jo same plane mein rehte hain.

Spanning team $S = {w_{1}, \dots, w_{n}}$ (gray): sab kuch banane ke liye kaafi arrows. Yeh overlap kar sakte hain ya redundant ho sakte hain — hum unhe independent hone ki zaroorat nahi hai.
Independent team $L = {v_{1}, \dots, v_{m}}$ (blue): koi waste nahi — har ek genuinely nayi jagah ki taraf point karta hai.

KYUN. Poora lemma in do numbers ko compare karne ka claim hai, isliye hume exactly pin down karna hai ki har team kya promise karti hai. $S$ coverage promise karta hai. $L$ no redundancy promise karta hai. Coverage ek resource hai; no-redundancy us resource par ek demand hai.

PICTURE.

Figure mein, gray $w$ -arrows overlap karte hain — yeh theek hai, ek spanning set ka sloppy hona allowed hai. Blue $v$ -arrows clearly distinct directions mein point karte hain — yahi independence dikhti hai.

Step 2 — Har arrow ek recipe hai (kyun spanning humein $v_{1}$ likhne deta hai)

KYA. Pehla independent arrow $v_{1}$ lo. Kyunki gray team spans karti hai, $v_{1}$ gray arrows ka combination hai: $v_{1} = how much of w_{1} a_{1} w_{1} + of w_{2} a_{2} w_{2} + \dots + of w_{n} a_{n} w_{n} .$

YEH TOOL KYUN — ek linear combination. Hum ek weighted sum use karte hain kyunki yahi ek vector space humein deta hai: arrows ko scale karo aur unhe add karo. Word "spans" ka matlab literally hai "aise sum se reachable," isliye $v_{1}$ is tarah likhna spanning promise ko cash karna hi hai. Numbers $a_{1}, \dots, a_{n}$ har ingredient ki quantities hain — $v_{1}$ ke liye ek recipe.

PICTURE.

Dashed arrows $a_{1} w_{1}$ , $a_{2} w_{2}$ , … ko head-to-tail dikhate hain; unka sum exactly $v_{1}$ ke blue tip par land karta hai.

Step 3 — Kam se kam ek ingredient real hai (pehla swap)

KYA. Saare $a_{i}$ zero nahi ho sakte. Agar hote, toh recipe padhti $v_{1} = 0$ — lekin $v_{1}$ independent team se aata hai, aur independent arrows kabhi zero arrow nahi hote. Toh koi $a_{i} \neq = 0$ hai; relabel karo taaki $a_{1} \neq = 0$ ho. Ab recipe ko backwards solve karo $w_{1}$ ke liye: $w_{1} = \frac{1}{a _{1}} (the new arrow v_{1} - the other grays a_{2} w_{2} - \dots - a_{n} w_{n}) .$

KYUN. Yeh line kehti hai ki $w_{1}$ ab redundant hai: jo bhi aap $w_{1}$ se bana sakte the, ab $v_{1}$ aur baaki grays se rebuild kar sakte hain. Yahan tool sirf equation rearrange karna hai — valid hai kyunki $a_{1} \neq = 0$ matlab hum usse divide kar sakte hain. $a_{1}$ se division wahi jagah hai jahan " $a_{1} \neq = 0$ " kaam aata hai; agar $a_{1}$ zero hota toh hum $w_{1}$ ko isolate nahi kar sakte.

PICTURE.

Hum kick out karte hain $w_{1}$ ko (faded gray, crossed) aur swap in karte hain $v_{1}$ ko (solid blue). Nayi team ${v_{1}, w_{2}, \dots, w_{n}}$ mein abhi bhi $n$ arrows hain aur — crucially — abhi bhi sab kuch spans karti hai jo purani team karta tha.

Step 4 — Swapping jaari rakho, aur trap ke liye nazar rakho

KYA. Maano $k$ swaps ke baad hamaari spanning team ek mix hai: ${k blues already in v_{1}, \dots, v_{k}, n - k grays left w_{k + 1}, \dots, w_{n}} .$ Agla blue $v_{k + 1}$ lao. Kyunki yeh mixed team abhi bhi spans karti hai, likhte hain: $v_{k + 1} = amounts of old blues b_{1} v_{1} + \dots + b_{k} v_{k} + amounts of remaining grays c_{k + 1} w_{k + 1} + \dots + c_{n} w_{n} .$

KYUN. Same spanning promise, current team par apply ki. Recipe mein ab do flavours of ingredients hain: blues jo hum pehle rakh chuke hain ( $b$ 's) aur grays jo abhi bhi khade hain ( $c$ 's). Hum inhe purpose se alag karte hain, kyunki do flavours agle step mein opposite roles play karte hain.

PICTURE.

Blue contributions blue mein, gray contributions gray mein, $v_{k + 1}$ mein sum hoti hain.

Step 5 — Kyun grays kabhi khatam nahi hote kick karne ke liye (dil ki baat)

KYA. Gray amounts $c_{k + 1}, \dots, c_{n}$ dekho. Kam se kam ek nonzero hai.

KYUN — yahan exactly independence use hoti hai. Maano har $c_{j} = 0$ hai. Tab recipe collapse ho jaati hai: $v_{k + 1} = b_{1} v_{1} + \dots + b_{k} v_{k},$ yaani $v_{k + 1}$ poori tarah purane blues se bana hai. Lekin blue team independent hai — koi blue doosron ka combination nahi hai. Contradiction. Toh koi $c_{j} \neq = 0$ hai: ek gray abhi bhi genuinely present hai, aur hum use kick out karke $v_{k + 1}$ swap in kar sakte hain. Team ka size $n$ rehta hai, aur yeh abhi bhi spans karti hai.

PICTURE.

Left panel — woh forbidden world jahan saare $c_{j} = 0$ hain: $v_{k + 1}$ (red) blue span ke andar land karta hai, jo independence ne outlaw kiya hua hai. Right panel — real world: ek nonzero $c_{j}$ ek gray ko game mein rakhta hai (green arrow), toh swap ho jaata hai.

Step 6 — Swaps gino: inequality apne aap nikal aati hai

KYA. Har swap ek blue (added) aur ek gray (removed) use karta hai. Saare $m$ blues place karne ke liye humein $m$ grays remove karni hain. Sirf $n$ grays hain. Toh: $m \leq n .$

KYUN. Yeh pure bookkeeping hai. Independence (Step 5) ne guarantee ki thi ki ek gray hamesha remove karne ke liye available hai, isliye swapping kabhi jam nahi karti blues khatam hone se pehle. Agar $m$ , $n$ se bada hota toh hum ek $(n + 1)$ -th swap try karte bina kisi gray ke — impossible. Isliye blues grays se zyada nahi ho sakte.

PICTURE.

Ek tally: ek axis pe blues-consumed, doosre pe grays-remaining, neeche chalte chalte jab tak grays zero hit nahi kar lete — woh wall jo $m$ ko cap karti hai.

Step 7 — Edge cases: inhe skip mat karo

KYA & KYUN. Hume dikhana hai ki har input ka behavior sahi hai.

$m = 0$ (empty independent set). Empty set vacuously independent hai, aur $0 \leq n$ hamesha. Koi swap zaroorat nahi; claim trivially holds.
$m = n$ (blues exactly grays ko fill karte hain). Aakhri swap aakhri gray ko remove karta hai. Team ab poori blue hai, size $n$ , abhi bhi spanning — yahi woh case hai jo Step 8 mein Dimension Theorem force karega.
Redundant / dependent spanning team. Grays se kabhi independent hone ki zaroorat nahi thi. Do grays identical ho sakte hain; koi $w_{j}$ zero ho sakta hai. Isse ek bhi step nahi toota — humne sirf itna use kiya ki grays spans karti hain. Yahi generality lemma ko itna powerful banati hai.
$v_{k + 1} = 0$ ho hi nahi sakta. Ek zero arrow blue team ko dependent bana deta, jo hamaari hypothesis ke against hai — isliye Step 5 ka contradiction machinery kabhi zero blue ke against test bhi nahi hota.

PICTURE.

Teen mini-panels: empty $L$ (kuch karna nahi), ek duplicated gray (swap abhi bhi theek), aur $m = n$ (saare grays consumed, all-blue team survive karti hai).

Step 8 — Do bases, dono taraf apply ⇒ equal size

KYA. Maano $B_{1}$ (size $p$ ) aur $B_{2}$ (size $q$ ) dono same space $V$ ki basis hain. Ek basis dono independent aur spanning hoti hai, isliye har ek lemma mein koi bhi role play kar sakti hai.

$B_{1}$ ko blue team (independent) aur $B_{2}$ ko gray team (spanning) maano: $p \leq q .$
Ab roles swap karo: $B_{2}$ blue, $B_{1}$ gray: $q \leq p .$

Do arrows $p$ aur $q$ ko dono sides se squeeze karte hain: $p \leq q aur q \leq p ⟹ p = q .$

KYUN. Lemma akela sirf ek inequality deta hai. Yeh basis ki double life hai — independent aur spanning ek saath — jo humein lemma ko do baar, opposite directions mein fire karne deti hai, do counts ko equality mein trap karte hue. Woh equal number $V$ ka dimension hai.

PICTURE.

Ek see-saw: $p \leq q$ ek side ko push karta hai, $q \leq p$ doosri ko, $p = q$ par balance karta hua.

Ek-picture summary

Left se right padhiye: gray spanning pile → blues ek ek karke andar aate hain, har swap ek gray ko kick karta hai (independence guarantee karti hai ki ek gray hamesha available hai) → tally blues ko grays se cap karta hai, $m \leq n$ deta hai → do bases par dono directions mein fire karo → see-saw $p = q = dim V$ par balance karta hai.

Recall Feynman: poora walkthrough simple words mein

Aapke paas gray sticks ka ek messy pile hai jo koi bhi shape banane ke liye kaafi hai (yahi spanning hai — pile mein duplicates ho sakte hain, koi baat nahi). Aapke paas blue sticks ka ek neat set bhi hai, koi do same direction mein nahi (yahi independence hai). Ab ek game khelo: ek ek karke, ek blue stick pile mein daalo aur ek gray nikalo, hamesha pile ko itna bada rakhte hue ki sab kuch build ho sake. Magic move yeh hai: jab bhi tum blue add karo, kya tum force ho sakte ho kisi gray ki jagah doosra blue nikalne ke liye? Nahi — kyunki agar sirf blues hi kaam kar rahe hote, toh tumhara naya blue purane blues ki copy hota, aur blues kabhi copies nahi hote. Toh hamesha ek gray hota hai throw karne ke liye. Kyunki har round mein ek blue aur ek gray khatam hota hai, aapke paas jitne grays se start kiya us se zyada blues nahi ho sakte: independent ≤ spanning. Aakhir mein, ek basis ek stick set hai jo dono neat aur kaafi hai — isliye yeh blue team ya gray team koi bhi ho sakti hai. Do bases ko dono directions mein ek doosre ki taraf point karo aur aapko milega "yeh wala ≤ woh wala" aur "woh wala ≤ yeh wala." Dono ka sach hone ka ek hi tarika hai ki woh equal hoon. Woh equal number dimension hai — space ka fixed brick-count, chahe aap kaunse bhi colours use karo.

Connections

Steinitz Exchange Lemma — woh engine jo humne swap-by-swap dekha.
Linear Independence — "some gray coefficient ≠ 0" step (Step 5).
Spanning Sets — Steps 2 aur 4 mein recipe provide karta hai.
Basis of a Vector Space — woh both-at-once object jo Step 8 mein measure hota hai.
Dimension — basis cardinality — parent result jise yeh page derive karta hai.
Rank-Nullity Theorem — dimension counting linear maps par apply ki.
Coordinates and Change of Basis — different bases, same size, action mein.