Exercises — QR decomposition

4.5.36 · D4 · Maths › Linear Algebra (Full) › QR decomposition

Kuch reminders jinpe hum rely karenge (sab parent se hain):

• $A=[{\mathbf{a}}_1\mid \cdots \mid {\mathbf{a}}_n]$ matlab matrix $A$ ko column vectors ki list ke roop mein likhna.
• ${\mathbf{q}}_i^{\top }{\mathbf{a}}_k$ dot product hai — "matching entries multiply karo aur jod do." Yeh measure karta hai ki ${\mathbf{a}}_k$ ka kitna hissa unit direction ${\mathbf{q}}_i$ ki taraf point karta hai.
• $\Vert \mathbf{u}\Vert =\sqrt{{\mathbf{u}}^{\top }\mathbf{u}}$ vector ki length hai.
• $r_{ik}={\mathbf{q}}_i^{\top }{\mathbf{a}}_k$ for $i<k$, $r_{kk}=\Vert {\mathbf{u}}_k\Vert$, aur $r_{ik}=0$ for $i>k$ (yahi last fact $R$ ko upper-triangular banata hai).

---

Level 1 — Recognition

Exercise 1.1

In mein se kaun sa matrix ek valid thin-QR $Q$ hai (orthonormal columns, $Q^{\top }Q=I_2$)?

S=\begin{bmatrix}\tfrac{1}{\sqrt2}&0\\ \tfrac{1}{\sqrt2}&0\\ 0&1\end{bmatrix}.$$ > [!recall]- Solution > Ek valid $Q$ ke liye har column ki **length 1** honi chahiye aur har distinct columns ki pair **perpendicular** honi chahiye (dot product $0$). > - $P$: column 1 hai $(1,1,0)$ jiska length $\sqrt{1^2+1^2+0^2}=\sqrt2\ne1$ hai. ❌ unit length nahi hai. > - $S$: column 1 $(\tfrac1{\sqrt2},\tfrac1{\sqrt2},0)$ ka length $\sqrt{\tfrac12+\tfrac12+0}=1$ hai ✅. Column 2 $(0,0,1)$ ka length $1$ hai ✅. Dot product $=\tfrac1{\sqrt2}\cdot0+\tfrac1{\sqrt2}\cdot0+0\cdot1=0$ ✅ perpendicular hai. > - **Answer: $S$** ek valid thin-QR $Q$ hai. ### Exercise 1.2 Kya $R=\begin{bmatrix}2&5\\0&3\end{bmatrix}$ ek valid QR $R$ factor hai? Aur $R'=\begin{bmatrix}2&0\\5&3\end{bmatrix}$ ke baare mein kya? > [!recall]- Solution > $R$ ko **upper-triangular with positive diagonal** hona chahiye (diagonal ke *neeche* zeros, diagonal entries $>0$). > - $R$: below-diagonal entry $0$ hai ✅, diagonal $2,3>0$ ✅ → **valid** hai. > - $R'$: row 2, column 1 mein entry $5\ne0$ hai — yeh diagonal ke *neeche* baith rahi hai, isliye $R'$ **lower**-triangular hai → valid QR $R$ **nahi** hai. > [!mistake] L1 trap: "orthogonal columns kaafi hain." > **Kyun sahi lagta hai:** "Orthonormal" sunne mein lagta hai sirf "right angles par hona." **Fix:** iska matlab hai **dono** perpendicular **aur** unit length. Ek matrix jiske columns perpendicular-but-long hain (jaise upar wala $P$) $Q^\top Q=I$ fail karta hai kyunki $Q^\top Q$ ki diagonal entries squared lengths hain, aur woh $1$ hone chahiye. --- ## Level 2 — Application ### Exercise 2.1 $A=\begin{bmatrix}3&1\\4&7\end{bmatrix}$ ka thin QR nikalo (positive diagonal ke saath). > [!recall]- Solution > **Column 1.** $\mathbf u_1=\mathbf a_1=(3,4)$, $\|\mathbf u_1\|=\sqrt{9+16}=5=r_{11}$. > $\mathbf q_1=\tfrac15(3,4)$. > **Coefficient.** $r_{12}=\mathbf q_1^\top\mathbf a_2=\tfrac15(3\cdot1+4\cdot7)=\tfrac15(3+28)=\tfrac{31}{5}$. > **Column 2.** Shadow hatao: > $$\mathbf u_2=\mathbf a_2-r_{12}\mathbf q_1=(1,7)-\tfrac{31}{5}\cdot\tfrac15(3,4)=(1,7)-\tfrac{31}{25}(3,4).$$ > $\tfrac{31}{25}(3,4)=(\tfrac{93}{25},\tfrac{124}{25})$, toh $\mathbf u_2=(1-\tfrac{93}{25},\,7-\tfrac{124}{25})=(-\tfrac{68}{25},\tfrac{51}{25})$. > $\|\mathbf u_2\|=\tfrac1{25}\sqrt{68^2+51^2}=\tfrac1{25}\sqrt{4624+2601}=\tfrac1{25}\sqrt{7225}=\tfrac{85}{25}=\tfrac{17}{5}=r_{22}$. > $\mathbf q_2=\tfrac{1}{17/5}\cdot(-\tfrac{68}{25},\tfrac{51}{25})=\tfrac{5}{17}(-\tfrac{68}{25},\tfrac{51}{25})=(-\tfrac45,\tfrac35)$. > **Result.** > $$Q=\begin{bmatrix}\tfrac35&-\tfrac45\\[2pt]\tfrac45&\tfrac35\end{bmatrix},\qquad R=\begin{bmatrix}5&\tfrac{31}{5}\\[2pt]0&\tfrac{17}{5}\end{bmatrix}.$$ > **Check:** $Q$ ke columns unit aur perpendicular hain; $QR=A$. ### Exercise 2.2 2.1 ke $Q,R$ use karke $Rx=Q^\top b$ se $Ax=b$ solve karo jahan $b=(2,1)$ hai. > [!recall]- Solution > $A$ square aur invertible hai, isliye least squares = exact solve hai. > $Q^\top b=\begin{bmatrix}\tfrac35&\tfrac45\\-\tfrac45&\tfrac35\end{bmatrix}\begin{bmatrix}2\\1\end{bmatrix}=\big(\tfrac{6}{5}+\tfrac45,\;-\tfrac85+\tfrac35\big)=(2,-1).$ > Back-substitute $Rx=Q^\top b$: > Row 2: $\tfrac{17}{5}x_2=-1\Rightarrow x_2=-\tfrac{5}{17}.$ > Row 1: $5x_1+\tfrac{31}{5}x_2=2\Rightarrow 5x_1=2-\tfrac{31}{5}\cdot(-\tfrac{5}{17})=2+\tfrac{31}{17}=\tfrac{65}{17}\Rightarrow x_1=\tfrac{13}{17}.$ > **Answer:** $x=(\tfrac{13}{17},-\tfrac{5}{17})$. > [!mistake] L2 trap: projection ko galat scaling ke saath subtract karna. > **Kyun sahi lagta hai:** Students likhte hain $\mathbf u_2=\mathbf a_2-(\mathbf q_1^\top\mathbf a_2)\mathbf a_1$ — **unit** $\mathbf q_1$ ki jagah **raw** $\mathbf a_1$ ka multiple subtract karte hain. **Fix:** ek *unit* vector par projection hai $(\mathbf q_1^\top\mathbf a_2)\mathbf q_1$. Agar raw $\mathbf a_1$ use karo toh $\|\mathbf a_1\|^2$ se divide karna padega: $\dfrac{\mathbf a_1^\top\mathbf a_2}{\mathbf a_1^\top\mathbf a_1}\mathbf a_1$. Dono mix karne se length double-count ho jaati hai. --- ## Level 3 — Analysis ### Exercise 3.1 $Q$ compute kiye bina, $A=\begin{bmatrix}3&1\\4&7\end{bmatrix}$ ka $\det(A)$ **sirf uske $R$ factor se** kya hoga? Rule explain karo. > [!recall]- Solution > Kyunki $A=QR$ hai, $\det A=\det Q\cdot\det R$. Ek thin/square real $Q$ jiske orthonormal columns hain, uske liye $\det Q=\pm1$ hota hai (yeh ek rotation ya reflection hai, jo area preserve karta hai). $R$ triangular hai, isliye $\det R=$ diagonal ka product $=r_{11}r_{22}$ hai. > Positive diagonal convention se $\det Q=+1$ yahan (proper rotation), isliye > $$|\det A|=r_{11}r_{22}=5\cdot\tfrac{17}{5}=17.$$ > Direct check: $\det A=3\cdot7-1\cdot4=21-4=17$. ✅ > **Rule:** $|\det A|=\prod_k r_{kk}=\prod_k\|\mathbf u_k\|$ — column parallelepiped ka volume *perpendicular leftovers* ke product ke barabar hai. ### Exercise 3.2 Dikhao ki agar $A$ mein pehle se ek orthogonal column pair hai (maano $\mathbf a_1\perp\mathbf a_2$), toh $r_{12}=0$ hoga. Isse $R$ kaisi ban jaati hai? > [!recall]- Solution > $r_{12}=\mathbf q_1^\top\mathbf a_2$ aur $\mathbf q_1=\mathbf a_1/\|\mathbf a_1\|$ hai, isliye > $$r_{12}=\frac{\mathbf a_1^\top\mathbf a_2}{\|\mathbf a_1\|}.$$ > Agar $\mathbf a_1\perp\mathbf a_2$ hai toh $\mathbf a_1^\top\mathbf a_2=0$ hai, isliye $r_{12}=0$. Off-diagonal pehle se zero hone par, $R$ **diagonal** ban jaati hai: $R=\operatorname{diag}(\|\mathbf a_1\|,\|\mathbf a_2\|)$. Pehle se orthogonal matrix ka QR sirf **normalize** karta hai: $Q$ har column ko length 1 tak scale karta hai, $R$ original lengths record karta hai. > [!mistake] L3 trap: "$\det Q$ kuch bhi ho sakta hai kyunki $Q$ generally square nahi hoti." > **Kyun sahi lagta hai:** Thin $Q$ tall hoti hai ($m\times n$), aur non-square matrices ka determinant nahi hota. **Fix:** determinant argument tab hi apply hota hai jab $A$ **square** ho ($m=n$), toh $Q$ bhi square hogi aur $\det Q=\pm1$ hoga. Tall $A$ ke liye tum instead $\det(A^\top A)=\det(R^\top R)=(\prod r_{kk})^2$ use karte ho, jahan "product of diagonals" volume interpretation phir bhi survive karti hai. --- ## Level 4 — Synthesis ### Exercise 4.1 Points $(t,y)=(0,1),(1,3),(2,4)$ se guzarne wali best line $y=c_0+c_1 t$ QR use karke fit karo (least squares). Model matrix hai $$A=\begin{bmatrix}1&0\\1&1\\1&2\end{bmatrix},\qquad b=\begin{bmatrix}1\\3\\4\end{bmatrix}.$$ > [!recall]- Solution > **Column 1.** $\mathbf u_1=(1,1,1)$, $\|\mathbf u_1\|=\sqrt3=r_{11}$, $\mathbf q_1=\tfrac1{\sqrt3}(1,1,1)$. > **Coefficient.** $r_{12}=\mathbf q_1^\top\mathbf a_2=\tfrac1{\sqrt3}(0+1+2)=\tfrac{3}{\sqrt3}=\sqrt3$. > **Column 2.** $\mathbf u_2=\mathbf a_2-r_{12}\mathbf q_1=(0,1,2)-\sqrt3\cdot\tfrac1{\sqrt3}(1,1,1)=(0,1,2)-(1,1,1)=(-1,0,1)$. > $\|\mathbf u_2\|=\sqrt{1+0+1}=\sqrt2=r_{22}$, $\mathbf q_2=\tfrac1{\sqrt2}(-1,0,1)$. > Toh $R=\begin{bmatrix}\sqrt3&\sqrt3\\0&\sqrt2\end{bmatrix}$. > **Right-hand side.** > $\mathbf q_1^\top b=\tfrac1{\sqrt3}(1+3+4)=\tfrac{8}{\sqrt3}$. > $\mathbf q_2^\top b=\tfrac1{\sqrt2}(-1\cdot1+0+1\cdot4)=\tfrac{3}{\sqrt2}$. > **Back-substitute** $Rx=Q^\top b$, jahan $x=(c_0,c_1)$ hai: > Row 2: $\sqrt2\,c_1=\tfrac{3}{\sqrt2}\Rightarrow c_1=\tfrac{3}{2}$. > Row 1: $\sqrt3\,c_0+\sqrt3\,c_1=\tfrac{8}{\sqrt3}\Rightarrow c_0+c_1=\tfrac{8}{3}\Rightarrow c_0=\tfrac{8}{3}-\tfrac32=\tfrac{16-9}{6}=\tfrac{7}{6}$. > **Best line:** $y=\tfrac{7}{6}+\tfrac32 t$. (Classic least-squares formula se compare karo: slope $=\tfrac32$, intercept $=\tfrac76$. ✅) ![[deepdives/dd-maths-4.5.36-d4-s02.png]] ### Exercise 4.2 Exercise 4.1 ke liye residual (bacha hua error) $\|Ax-b\|$ **$Q^\top b$ use karke** predict karo, bina $Ax$ dubara compute kiye. > [!recall]- Solution > $Q$ ko ek teesre unit vector $\mathbf q_3\perp\mathbf q_1,\mathbf q_2$ ke saath full orthonormal basis tak extend karo. Kyunki $Q$ length preserve karta hai, > $$\|b\|^2=(\mathbf q_1^\top b)^2+(\mathbf q_2^\top b)^2+(\mathbf q_3^\top b)^2.$$ > Fitted part sirf $\mathbf q_1,\mathbf q_2$ use karta hai; **unexplained** part $(\mathbf q_3^\top b)^2$ hai, aur yahi squared residual ke barabar hai. > $\|b\|^2=1^2+3^2+4^2=26$. Explained $=(\tfrac{8}{\sqrt3})^2+(\tfrac{3}{\sqrt2})^2=\tfrac{64}{3}+\tfrac{9}{2}=\tfrac{128+27}{6}=\tfrac{155}{6}$. > Residual$^2=26-\tfrac{155}{6}=\tfrac{156-155}{6}=\tfrac16$. > $$\|Ax-b\|=\sqrt{\tfrac16}=\tfrac{1}{\sqrt6}\approx0.408.$$ > [!mistake] L4 trap: $b$ ke saath dot karne se pehle $Q$ ke columns ko **normalize** karna bhool jaana. > **Kyun sahi lagta hai:** Line fit ke projection formula mein, log raw columns $(1,1,1)$ aur $(0,1,2)$ ko $Q^\top b$ mein plug kar dete hain. **Fix:** $Q^\top b$ ki entries **unit** $\mathbf q_i$ ke saath dot products hain, raw $\mathbf a_i$ ke saath nahi. $\tfrac1{\sqrt3}$ aur $\tfrac1{\sqrt2}$ factors wahi hain jo length-preservation identity (aur residual formula) ko sahi rakhte hain. --- ## Level 5 — Mastery ### Exercise 5.1 Thin QR ki **uniqueness** prove karo: agar $A=Q_1R_1=Q_2R_2$ hai jahan dono $Q_i$ ke orthonormal columns hain aur dono $R_i$ upper-triangular hain **positive diagonal** ke saath, toh $Q_1=Q_2$ aur $R_1=R_2$ hoga. > [!recall]- Solution > $Q_1R_1=Q_2R_2$ se, left mein $Q_2^\top$ aur right mein $R_1^{-1}$ multiply karo (invertible hai kyunki $r_{kk}>0$ hai): > $$Q_2^\top Q_1=R_2R_1^{-1}.$$ > Is matrix ko $M$ kaho. $M$ ke baare mein do facts: > 1. **$M$ upper-triangular hai.** $R_2$ upper-triangular hai aur ek upper-triangular matrix ka inverse upper-triangular hota hai, aur upper-triangular matrices ka product upper-triangular hota hai. Toh right side $R_2R_1^{-1}=M$ upper-triangular hai. > 2. **$M$ orthogonal hai.** $M^\top M=(Q_2^\top Q_1)^\top(Q_2^\top Q_1)=Q_1^\top Q_2Q_2^\top Q_1$. Thin setting mein jahan column spaces coincide karte hain, $Q_2Q_2^\top$ us space par identity ki tarah act karta hai, giving $M^\top M=Q_1^\top Q_1=I$. > Ek **upper-triangular orthogonal** matrix **$\pm1$ entries wala diagonal** hona chahiye: orthogonality force karta hai ki columns unit aur mutually perpendicular hon, aur triangular structure force karta hai ki saare off-diagonal entries vanish ho jaayein. Isliye $M=\operatorname{diag}(\pm1)$ hai. > Ab positivity use karo: $M=R_2R_1^{-1}$ ke diagonal entries $(r_2)_{kk}/(r_1)_{kk}>0$ hain (positive numbers ka ratio). Ek diagonal $\pm1$ matrix jiska positive diagonal ho, woh $I$ hai. Isliye $M=I$ hai, giving $R_2=R_1$ aur phir $Q_2^\top Q_1=I\Rightarrow Q_1=Q_2$. $\blacksquare$ ### Exercise 5.2 Maano $A$ ek $n\times n$ invertible matrix hai. Dikhao ki $A^\top A=R^\top R$ hai (yeh $A^\top A$ ki **Cholesky factorization** hai), aur explain karo ki yeh QR ko normal equations se kaise link karta hai. > [!recall]- Solution > $A=QR$ substitute karo: > $$A^\top A=(QR)^\top(QR)=R^\top Q^\top Q\,R=R^\top I\,R=R^\top R,$$ > $Q^\top Q=I$ use karke. Yahan $R^\top$ **lower**-triangular hai positive diagonal ke saath aur $R$ upper-triangular hai positive diagonal ke saath, isliye $R^\top R$ bilkul symmetric positive-definite matrix $A^\top A$ ki Cholesky factorization hai. > **Normal equations se link:** normal equations $A^\top A\,x=A^\top b$ ban jaate hain $R^\top R\,x=R^\top Q^\top b$. Invertible $R^\top$ cancel karne par milta hai $Rx=Q^\top b$ — wahi stable triangular solve jo parent note mein hai. QR **hai hi** normal-equations solve jahan dangerous $A^\top A$ squaring ki jagah already-computed $R$ use hoti hai. > [!mistake] L5 trap: directly yeh claim karna ki "upper-triangular + orthogonal ⇒ identity." > **Kyun sahi lagta hai:** Yeh *almost* sahi hai — lekin tum ek case miss karte ho. Ek upper-triangular orthogonal matrix diagonal hoti hai $\pm1$ entries ke saath, aur **sign convention ke bina yeh $I$ nahi bhi ho sakti** (jaise $\operatorname{diag}(1,-1)$ orthogonal aur triangular hai). **Fix:** positive-diagonal requirement exactly wahi hai jo $-1$ possibility ko khatam karti hai. QR ki uniqueness us convention par *depend* karti hai — use hatao aur $Q,R$ sirf column sign flips tak determine hoti hain. --- ## Connections - [[Gram-Schmidt process]] — upar ke har solution ne yahi recipe chalai. - [[Orthonormal bases and projections]] — 4.2 mein residual trick orthogonal projection hai. - [[Least squares and normal equations]] — Exercises 4.1 aur 5.2 iska payoff hain. - [[Householder reflections]] — L2 trap mein hint kiya gaya stable production route. - [[Eigenvalues and the QR algorithm]] — jahan uniqueness (5.1) iterations ko well-defined rakhti hai. - [[LU decomposition]] — 5.2 ke Cholesky link ko us sibling factorization se compare karo. --- ## Active Recall > [!recall]- Quick self-check > - $R$ se $\det A$ kaise padte hain (square case mein)? ::: $|\det A|=\prod_k r_{kk}$. > - $Q^\top b$ ke terms mein squared residual kya hai? ::: $\|b\|^2-\sum_{i\le n}(\mathbf q_i^\top b)^2$. > - Kaun si identity QR = normal equations banati hai? ::: $A^\top A=R^\top R$. > - QR ko unique kaun sa convention banata hai? ::: $r_{kk}>0$.