Worked examples — Gram-Schmidt orthogonalization — algorithm

4.5.35 · D3 · Maths › Linear Algebra (Full) › Gram-Schmidt orthogonalization — algorithm

Aapne parent note mein ye machine dekhi hai. Yahan hum ise har tarah ke input ke saath stress-test karenge — messy angles, degenerate (dependent) vectors, weird inner products, ek real word problem, aur ek exam twist. Har example aapko scenario table ka ek "cell" cover karta hai.

Shuru karne se pehle, ek reminder plain words mein taaki kuch bhi assume na ho.

---

Scenario matrix

Gram–Schmidt ek formula jaisa lagta hai, lekin behaviour bilkul badal jaata hai depending on kya feed kiya. Yahan har case class hai jo occur ho sakti hai — hum har single row neeche cover karenge.

#	Cell / scenario	Kya special hai	Example
C1	Do clean 2-D vectors, positive overlap	shadow along $u_1$ point karta hai	Ex 1
C2	Negative overlap ($⟨v_2,u_1⟩<0$)	shadow opposite $u_1$ point karta hai; $c$ ka sign flip hota hai	Ex 2
C3	Already orthogonal input	overlap $=0$, algorithm kuch nahi karta	Ex 3
C4	Full 3-D, do subtractions	dono earlier $u_j$ clear karne padenge	Ex 4
C5	Degenerate — dependent vector	residual $u_k=0$, normalize nahi kar sakte	Ex 5
C6	Order matters — same set, swapped $v_1,v_2$	different $u$'s, same subspace	Ex 6
C7	Non-standard inner product (weighted)	$⟨\cdot ,\cdot ⟩$ change kar deta hai ki "perpendicular" ka kya matlab hai	Ex 7
C8	Word problem — measurements decorrelate karna	Gram–Schmidt as "common trend remove karo"	Ex 8
C9	Exam twist — QR decomposition ka $R$ read off karo	coefficients HI answer hain	Ex 9

---

Ex 1 — Cell C1: positive overlap in ${\mathbb{R}}^2$

Forecast (pehle guess karo!): $v_2$ thoda sa $v_1$ ke saath lean karta hai (dono up-right point karte hain), toh leftover $u_2$ up-and-slightly-left point karna chahiye. Aage padhne se pehle picture banane ki koshish karo.

1. $u_1=v_1=(4,3)$. Ye step kyun? Pehle vector ke pehle koi cheez nahi hoti jiske perpendicular hona ho, isliye hum ise untouched rakhte hain — ye humara pehla clean axis define karta hai.

2. Overlap compute karo. $⟨v_2,u_1⟩=1\cdot 4+2\cdot 3=10$, aur $⟨u_1,u_1⟩=16+9=25$. Ye step kyun? Ye do numbers scalar $c=\frac{10}{25}=0.4$ banate hain — "kitne copies of $u_1$, $v_2$ ke shadow ke andar fit hoti hain".

3. Shadow subtract karo. $u_2=(1,2)-0.4(4,3)=(1-1.6,2-1.2)=(-0.6,0.8).$ Ye step kyun? $c=0.4>0$ matlab shadow (figure mein red arrow) $u_1$ ke same direction mein point karta hai; ise remove karna $v_2$ ko perpendicular leftover (pink arrow) par wapas le jaata hai.

4. Normalize karo. $\Vert u_1\Vert =\sqrt{25}=5$, $\Vert u_2\Vert =\sqrt{0.36+0.64}=\sqrt{1}=1$ (already unit!). $e_1=\frac{1}{5}(4,3)=(0.8,0.6),e_2=(-0.6,0.8).$

Recall Verify karo

$⟨u_1,u_2⟩=4(-0.6)+3(0.8)=-2.4+2.4=0$ ✅ perpendicular. $⟨e_1,e_2⟩=0$ aur $\Vert e_1\Vert =\Vert e_2\Vert =1$ ✅ orthonormal.

---

Ex 2 — Cell C2: negative overlap (opposite lean)

Forecast: $v_2$ up aur left ki taraf point karta hai, toh ye $u_1=(1,0)$ ke against lean karta hai. Expect karo ki scalar $c$ negative aayega — shadow backward point karega.

1. $u_1=(1,0)$. Kyun? Pehla vector, as-is rakha; ye positive-$x$ axis hai.

2. Overlap: $⟨v_2,u_1⟩=(-3)(1)+2\cdot 0=-3$; $⟨u_1,u_1⟩=1$. Toh $c=-3$. Ye step kyun? Negative $c$ koi error nahi hai — matlab bas ye hai ki shadow $c{u}_1=(-3,0)$ $-x$ direction mein point karta hai, bilkul $v_2$ ke leftward lean se match karta hai.

3. Subtract karo: $u_2=(-3,2)-(-3)(1,0)=(-3+3,2)=(0,2)$. Kyun? Ek backward shadow remove karna (negative subtract karna) residual ko $y$-axis par push kar deta hai — visibly $x$-axis ke perpendicular.

4. Normalize karo: $\Vert u_2\Vert =2$, toh $e_1=(1,0)$, $e_2=(0,1)$.

Recall Verify karo

$⟨u_1,u_2⟩=1\cdot 0+0\cdot 2=0$ ✅. Output literally standard basis hai — sense banta hai, koi bhi 2 independent 2-D vectors comb hokar ek rotated pair of axes ban jaate hain, aur yahan wo $x,y$ ke saath align karte hain.

---

Ex 3 — Cell C3: input already orthogonal hai

Forecast: ye already right angles par hain, toh Gram–Schmidt ko sirf lengths change karne chahiye.

1. $u_1=(2,0)$.
2. Overlap: $⟨v_2,u_1⟩=0\cdot 2+5\cdot 0=0$, toh $c=0$. Ye step kyun matter karta hai: jab overlap zero ho, shadow zero vector hota hai — subtract karne ke liye kuch bhi nahi. Ye degenerate-in-a-good-way case hai: comb seedha pass ho jaata hai.
3. $u_2=(0,5)-0\cdot (2,0)=(0,5)$. Unchanged.
4. Normalize karo: $e_1=(1,0)$, $e_2=(0,1)$.

Recall Verify karo

$⟨u_1,u_2⟩=0$ already pehle se tha ✅. Gram–Schmidt orthogonal input par idempotent hai — ek achha sanity check ki algorithm kabhi "over-combs" nahi karta.

---

Ex 4 — Cell C4: full ${\mathbb{R}}^3$, do subtractions

Forecast: $u_3$ ko do shadows clean karne padenge — ek $u_1$ par, ek $u_2$ par. Koi ek miss kiya toh perpendicularity proof collapse ho jaayega.

1. $u_1=(1,1,1)$. Kyun? Base direction.

2. $u_2$: $⟨v_2,u_1⟩=1+1+0=2$, $⟨u_1,u_1⟩=3$. Coefficient $\frac{2}{3}$. $u_2=(1,1,0)-\frac{2}{3}(1,1,1)=\left(\frac{1}{3},\frac{1}{3},-\frac{2}{3}\right).$ Ye step kyun? Ek earlier clean vector ⇒ ek shadow remove.

3. $u_3$ ko DONO removals chahiye. Compute karo:

   • $⟨v_3,u_1⟩=1+0+0=1$, $⟨u_1,u_1⟩=3$ ⇒ coeff $\frac{1}{3}$.
   • $⟨v_3,u_2⟩=\frac{1}{3}+0+0=\frac{1}{3}$, $⟨u_2,u_2⟩=\frac{1}{9}+\frac{1}{9}+\frac{4}{9}=\frac{6}{9}=\frac{2}{3}$ ⇒ coeff $\frac{1/3}{2/3}=\frac{1}{2}$. $u_3=(1,0,0)-\frac{1}{3}(1,1,1)-\frac{1}{2}\left(\frac{1}{3},\frac{1}{3},-\frac{2}{3}\right).$ Ye step kyun? Do already-orthogonal vectors hain, toh do shadows jaane chahiye — mnemonic hai "Subtract the Shadows of the Settled."

4. Coordinate-by-coordinate simplify karo: $u_3=\left(1-\frac{1}{3}-\frac{1}{6},0-\frac{1}{3}-\frac{1}{6},0-\frac{1}{3}+\frac{1}{3}\right)=\left(\frac{1}{2},-\frac{1}{2},0\right).$

Recall Verify karo

$⟨u_3,u_1⟩=\frac{1}{2}-\frac{1}{2}+0=0$ ✅ $⟨u_3,u_2⟩=\frac{1}{2}\cdot \frac{1}{3}+(-\frac{1}{2})\cdot \frac{1}{3}+0=\frac{1}{6}-\frac{1}{6}=0$ ✅ Dono zero ⇒ $u_3$ saare earlier vectors ke perpendicular hai, jaise induction ne promise kiya tha.

---

Ex 5 — Cell C5: degenerate (dependent) input → zero vector

Forecast: $v_2$ bilkul exactly $v_1$ ke along hai, toh shadow remove karne ke baad kuch nahi bachega — residual $0$ hona chahiye, aur normalization mein zero se divide karna padega.

1. $u_1=(1,2)$.
2. Overlap: $⟨v_2,u_1⟩=2+8=10$, $⟨u_1,u_1⟩=1+4=5$, toh $c=2$.
3. Subtract karo: $u_2=(2,4)-2(1,2)=(0,0)=0$. Ye step kyun? Poora vector shadow hi tha. Kuch bhi perpendicular nahi nikla.

Recall Verify karo

$u_2=(0,0)$ ka norm $0$ hai, jo dependence confirm karta hai. Koi bhi dependent input offending step par zero residual deta hai.

---

Ex 6 — Cell C6: order matters (inputs swap karo)

Forecast: hume Ex 1 se different $u$'s milne chahiye, phir bhi wo same plane span karein (${\mathbb{R}}^2$ yahan) aur orthonormal rahein. Gram–Schmidt inputs ki ordering par depend karta hai.

1. $u_1=(1,2)$. (Ex 1 mein ye $u_2$ ke neighbourhood mein tha — ab ye lead karta hai.)
2. Overlap: $⟨v_2,u_1⟩=4+6=10$, $⟨u_1,u_1⟩=1+4=5$, $c=2$.
3. Subtract karo: $u_2=(4,3)-2(1,2)=(2,-1)$. Ye step kyun? Pehle vector ne axis fix ki; doosra iske against comb hota hai.
4. Normalize karo: $\Vert u_1\Vert =\sqrt{5}$, $\Vert u_2\Vert =\sqrt{5}$. $e_1=\frac{1}{\sqrt{5}}(1,2),e_2=\frac{1}{\sqrt{5}}(2,-1).$

Recall Verify karo

$⟨u_1,u_2⟩=1\cdot 2+2(-1)=0$ ✅ aur $\Vert e_1\Vert =\Vert e_2\Vert =1$ ✅.

---

Ex 7 — Cell C7: ek weighted inner product

Forecast: "perpendicular" ab weighted balance matlab hai, visual right angles nahi. Numbers change honge, lekin exact same formula chalegi — isliye parent note ne $⟨\cdot ,\cdot ⟩$ abstractly likha tha, kabhi "dot" nahi.

1. $u_1=(1,0)$.
2. Weighted overlap: $⟨v_2,u_1{⟩}_W=2(1)(1)+3(1)(0)=2$; $⟨u_1,u_1{⟩}_W=2(1)(1)+3\cdot 0=2$. Toh $c=1$. Ye step kyun? Hum weighted inner product ko exact same $c=\frac{⟨v,u⟩}{⟨u,u⟩}$ mein plug karte hain — koi nayi machinery nahi chahiye.
3. Subtract karo: $u_2=(1,1)-1\cdot (1,0)=(0,1)$.

Recall Verify karo

Weighted product se check karo: $⟨u_1,u_2{⟩}_W=2(1)(0)+3(0)(1)=0$ ✅. Note: ordinary dot product ke under $(1,0)\cdot (0,1)=0$ bhi yahan — lekin generally weighted-orthogonal vectors paper par perpendicular nahi dikhne chahiye. Orthogonality us inner product se define hoti hai jo aapne choose ki.

---

Ex 8 — Cell C8: word problem (trends decorrelate karna)

Forecast: B mein clearly "flat baseline" ka ek chunk hai. B ka shadow A par subtract karne se ek pure rising residual bachna chahiye jo average zero hoga.

1. $u_1=a=(2,2,2)$ — baseline direction. Kyun? Baseline ko hum "settled" reference maante hain.
2. Overlap: $⟨b,u_1⟩=2+4+6=12$; $⟨u_1,u_1⟩=4+4+4=12$; $c=1$. Ye step kyun? $c=1$ kehta hai B mein exactly ek poori copy baseline ki hai.
3. Residual: $u_2=(1,2,3)-1\cdot (2,2,2)=(-1,0,1)$. Kyun? Ye B hai baseline remove karke — pure day-to-day change.

Recall Verify karo

$⟨u_2,u_1⟩=-2+0+2=0$ ✅ baseline se independent. Interpretation check: residual $(-1,0,1)$ sum to zero karta hai ⇒ ye koi average level carry nahi karta, sirf rising trend. Bilkul wahi jo "common baseline remove karo" ka matlab hona chahiye. (Ye Least squares regression ka seed idea hai: jo model aapke paas already hai uska projection subtract karo.)

---

Ex 9 — Cell C9: exam twist — QR decomposition se $R$ read off karo

Forecast: har $R$ entry sirf ek inner product $⟨v_k,e_j⟩$ hai jo aapne already compute kiya tha — koi nayi kaam nahi, yahi toh poora trick hai.

1. $R_{11}=⟨v_1,e_1⟩=(4,3)\cdot (0.8,0.6)=3.2+1.8=5$. (Ye $\Vert v_1\Vert$ hai.)
2. $R_{12}=⟨v_2,e_1⟩=(1,2)\cdot (0.8,0.6)=0.8+1.2=2$.
3. $R_{22}=⟨v_2,e_2⟩=(1,2)\cdot (-0.6,0.8)=-0.6+1.6=1$. (Ye Ex 1 se $\Vert u_2\Vert$ hai.)
4. $R_{21}=0$ — hamesha, kyunki $v_1$ ka koi $e_2$ component nahi ($e_2$ baad mein aaya tha). $R=\left(\begin{array}{cc}5& 2\\ 0& 1\end{array}\right).$

Recall Verify karo

Reconstruct karo: $QR$ pehla column $=5e_1=5(0.8,0.6)=(4,3)=v_1$ ✅. Doosra column $=2e_1+1e_2=(1.6,1.2)+(-0.6,0.8)=(1,2)=v_2$ ✅. Toh $A=QR$ exactly.

---

Connections

• Orthogonal projection — har example mein use hone wala shadow
• Inner product spaces — Ex 7 inner product change karta hai aur machine phir bhi chalti hai
• Linear independence — Ex 5 dikhata hai dependence zero vector ke roop mein surface hoti hai
• Orthonormal basis — Ex 1, 2, 6 ka output
• QR decomposition — Ex 9 projections se seedha $R$ read karta hai
• Least squares — Ex 8 "jo already model hai usse remove karo" ka seed hai
• Gram-Schmidt orthogonalization — algorithm — parent jise ye deep-dive expand karta hai