Exercises — QR decomposition

Reminders we will lean on (all from the parent):

• $A=[{\mathbf{a}}_1\mid \cdots \mid {\mathbf{a}}_n]$ means the matrix $A$ written as a list of column vectors.
• ${\mathbf{q}}_i^{\top }{\mathbf{a}}_k$ is the dot product — "multiply matching entries and add." It measures *how much of ${\mathbf{a}}_k$ points along the unit direction ${\mathbf{q}}_i$."
• $\Vert \mathbf{u}\Vert =\sqrt{{\mathbf{u}}^{\top }\mathbf{u}}$ is the length of a vector.
• $r_{ik}={\mathbf{q}}_i^{\top }{\mathbf{a}}_k$ for $i<k$, $r_{kk}=\Vert {\mathbf{u}}_k\Vert$, and $r_{ik}=0$ for $i>k$ (that last fact is what makes $R$ upper-triangular).

---

Level 1 — Recognition

Exercise 1.1

Which of these matrices is a valid thin-QR $Q$ (orthonormal columns, $Q^{\top }Q=I_2$)?

S=\begin{bmatrix}\tfrac{1}{\sqrt2}&0\\ \tfrac{1}{\sqrt2}&0\\ 0&1\end{bmatrix}.$$ > [!recall]- Solution > A valid $Q$ needs every column of **length 1** and every pair of distinct columns **perpendicular** (dot product $0$). > - $P$: column 1 is $(1,1,0)$ with length $\sqrt{1^2+1^2+0^2}=\sqrt2\ne1$. ❌ not unit length. > - $S$: column 1 $(\tfrac1{\sqrt2},\tfrac1{\sqrt2},0)$ has length $\sqrt{\tfrac12+\tfrac12+0}=1$ ✅. Column 2 $(0,0,1)$ has length $1$ ✅. Dot product $=\tfrac1{\sqrt2}\cdot0+\tfrac1{\sqrt2}\cdot0+0\cdot1=0$ ✅ perpendicular. > - **Answer: $S$** is a valid thin-QR $Q$. ### Exercise 1.2 Is $R=\begin{bmatrix}2&5\\0&3\end{bmatrix}$ a valid QR $R$ factor? What about $R'=\begin{bmatrix}2&0\\5&3\end{bmatrix}$? > [!recall]- Solution > $R$ must be **upper-triangular with positive diagonal** (zeros *below* the diagonal, diagonal entries $>0$). > - $R$: below-diagonal entry is $0$ ✅, diagonal $2,3>0$ ✅ → **valid**. > - $R'$: the entry in row 2, column 1 is $5\ne0$ — that sits *below* the diagonal, so $R'$ is **lower**-triangular → **not** a valid QR $R$. > [!mistake] L1 trap: "orthogonal columns is enough." > **Why it feels right:** "Orthonormal" sounds like it just means "at right angles." **Fix:** it means **both** perpendicular **and** unit length. A matrix with perpendicular-but-long columns (like $P$ above) fails $Q^\top Q=I$ because the diagonal entries of $Q^\top Q$ are the squared lengths, and those must be $1$. --- ## Level 2 — Application ### Exercise 2.1 Find the thin QR of $A=\begin{bmatrix}3&1\\4&7\end{bmatrix}$ (positive diagonal). > [!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.** Remove the shadow: > $$\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})$, so $\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$'s columns are unit and perpendicular; $QR=A$. ### Exercise 2.2 Using the $Q,R$ from 2.1, solve $Ax=b$ for $b=(2,1)$ via $Rx=Q^\top b$. > [!recall]- Solution > $A$ is square and invertible, so least squares = exact solve. > $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: subtracting the projection with the wrong scaling. > **Why it feels right:** Students write $\mathbf u_2=\mathbf a_2-(\mathbf q_1^\top\mathbf a_2)\mathbf a_1$ — subtracting a multiple of the **raw** $\mathbf a_1$ instead of the **unit** $\mathbf q_1$. **Fix:** the projection onto a *unit* vector is $(\mathbf q_1^\top\mathbf a_2)\mathbf q_1$. If you use the raw $\mathbf a_1$ you must divide by $\|\mathbf a_1\|^2$: $\dfrac{\mathbf a_1^\top\mathbf a_2}{\mathbf a_1^\top\mathbf a_1}\mathbf a_1$. Mixing the two double-counts the length. --- ## Level 3 — Analysis ### Exercise 3.1 Without computing $Q$, what is $\det(A)$ for $A=\begin{bmatrix}3&1\\4&7\end{bmatrix}$ **from its $R$ factor alone**? Explain the rule. > [!recall]- Solution > Since $A=QR$, $\det A=\det Q\cdot\det R$. For a thin/square real $Q$ with orthonormal columns, $\det Q=\pm1$ (it is a rotation or reflection, which preserves area). $R$ is triangular, so $\det R=$ product of the diagonal $=r_{11}r_{22}$. > With positive diagonal convention $\det Q=+1$ here (proper rotation), so > $$|\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\|$ — the volume of the column parallelepiped equals the product of the *perpendicular leftovers*. ### Exercise 3.2 Show that if $A$ has an orthogonal column pair already (say $\mathbf a_1\perp\mathbf a_2$), then $r_{12}=0$. What does that make $R$? > [!recall]- Solution > $r_{12}=\mathbf q_1^\top\mathbf a_2$ and $\mathbf q_1=\mathbf a_1/\|\mathbf a_1\|$, so > $$r_{12}=\frac{\mathbf a_1^\top\mathbf a_2}{\|\mathbf a_1\|}.$$ > If $\mathbf a_1\perp\mathbf a_2$ then $\mathbf a_1^\top\mathbf a_2=0$, hence $r_{12}=0$. With the off-diagonal already zero, $R$ is **diagonal**: $R=\operatorname{diag}(\|\mathbf a_1\|,\|\mathbf a_2\|)$. QR of an already-orthogonal matrix just **normalizes**: $Q$ scales each column to length 1, $R$ records the original lengths. > [!mistake] L3 trap: "$\det Q$ could be anything since $Q$ isn't square in general." > **Why it feels right:** Thin $Q$ is tall ($m\times n$), and non-square matrices have no determinant. **Fix:** the determinant argument only applies when $A$ is **square** ($m=n$), so $Q$ is square too and $\det Q=\pm1$. For tall $A$ you instead use $\det(A^\top A)=\det(R^\top R)=(\prod r_{kk})^2$, which is where the "product of diagonals" volume interpretation still survives. --- ## Level 4 — Synthesis ### Exercise 4.1 Fit the best line $y=c_0+c_1 t$ (least squares) through the points $(t,y)=(0,1),(1,3),(2,4)$ using QR. The model matrix is $$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)$. > So $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$, with $x=(c_0,c_1)$: > 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$. (Compare the classic least-squares formula: slope $=\tfrac32$, intercept $=\tfrac76$. ✅) ![[deepdives/dd-maths-4.5.36-d4-s02.png]] ### Exercise 4.2 Predict the residual (leftover error) $\|Ax-b\|$ for Exercise 4.1 **using $Q^\top b$**, without recomputing $Ax$. > [!recall]- Solution > Extend $Q$ to a full orthonormal basis with a third unit vector $\mathbf q_3\perp\mathbf q_1,\mathbf q_2$. Because $Q$ preserves length, > $$\|b\|^2=(\mathbf q_1^\top b)^2+(\mathbf q_2^\top b)^2+(\mathbf q_3^\top b)^2.$$ > The fitted part uses only $\mathbf q_1,\mathbf q_2$; the **unexplained** part is $(\mathbf q_3^\top b)^2$, and that equals the squared residual. > $\|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: forgetting $Q$'s columns must be **normalized** before dotting with $b$. > **Why it feels right:** In the projection formula for a line fit, people plug the raw columns $(1,1,1)$ and $(0,1,2)$ into $Q^\top b$. **Fix:** the entries of $Q^\top b$ are dot products with the **unit** $\mathbf q_i$, not the raw $\mathbf a_i$. The $\tfrac1{\sqrt3}$ and $\tfrac1{\sqrt2}$ factors are exactly what keep the length-preservation identity (and the residual formula) honest. --- ## Level 5 — Mastery ### Exercise 5.1 Prove the **uniqueness** of thin QR: if $A=Q_1R_1=Q_2R_2$ with both $Q_i$ orthonormal-columned and both $R_i$ upper-triangular with **positive diagonal**, then $Q_1=Q_2$ and $R_1=R_2$. > [!recall]- Solution > From $Q_1R_1=Q_2R_2$, multiply left by $Q_2^\top$ and right by $R_1^{-1}$ (invertible since $r_{kk}>0$): > $$Q_2^\top Q_1=R_2R_1^{-1}.$$ > Call this matrix $M$. Two facts about $M$: > 1. **$M$ is upper-triangular.** $R_2$ is upper-triangular and the inverse of an upper-triangular matrix is upper-triangular, and a product of upper-triangular matrices is upper-triangular. So the right side $R_2R_1^{-1}=M$ is upper-triangular. > 2. **$M$ is orthogonal.** $M^\top M=(Q_2^\top Q_1)^\top(Q_2^\top Q_1)=Q_1^\top Q_2Q_2^\top Q_1$. Working in the thin setting where the column spaces coincide, $Q_2Q_2^\top$ acts as identity on that space, giving $M^\top M=Q_1^\top Q_1=I$. > An **upper-triangular orthogonal** matrix must be **diagonal with entries $\pm1$**: orthogonality forces columns to be unit and mutually perpendicular, and triangular structure forces all off-diagonal entries to vanish. So $M=\operatorname{diag}(\pm1)$. > Now use positivity: $M=R_2R_1^{-1}$ has diagonal entries $(r_2)_{kk}/(r_1)_{kk}>0$ (ratio of positive numbers). A diagonal $\pm1$ matrix with positive diagonal is $I$. Hence $M=I$, giving $R_2=R_1$ and then $Q_2^\top Q_1=I\Rightarrow Q_1=Q_2$. $\blacksquare$ ### Exercise 5.2 Let $A$ be $n\times n$ invertible. Show $A^\top A=R^\top R$ (this is the **Cholesky factorization** of $A^\top A$), and explain why this links QR to the normal equations. > [!recall]- Solution > Substitute $A=QR$: > $$A^\top A=(QR)^\top(QR)=R^\top Q^\top Q\,R=R^\top I\,R=R^\top R,$$ > using $Q^\top Q=I$. Here $R^\top$ is **lower**-triangular with positive diagonal and $R$ is upper-triangular with positive diagonal, so $R^\top R$ is precisely the Cholesky factorization of the symmetric positive-definite matrix $A^\top A$. > **Link to normal equations:** the normal equations $A^\top A\,x=A^\top b$ become $R^\top R\,x=R^\top Q^\top b$. Cancelling the invertible $R^\top$ gives $Rx=Q^\top b$ — the same stable triangular solve from the parent note. QR **is** the normal-equations solve with the dangerous $A^\top A$ squaring replaced by the already-computed $R$. > [!mistake] L5 trap: claiming "upper-triangular + orthogonal ⇒ identity" directly. > **Why it feels right:** It *nearly* is — but you skip a case. An upper-triangular orthogonal matrix is diagonal with $\pm1$ entries, and **without a sign convention it need not be $I$** (e.g. $\operatorname{diag}(1,-1)$ is orthogonal and triangular). **Fix:** the positive-diagonal requirement is exactly what kills the $-1$ possibility. Uniqueness of QR *depends* on that convention — drop it and $Q,R$ are only determined up to column sign flips. --- ## Connections - [[Gram-Schmidt process]] — every solution above ran this recipe. - [[Orthonormal bases and projections]] — the residual trick in 4.2 is orthogonal projection. - [[Least squares and normal equations]] — Exercises 4.1 and 5.2 are the payoff. - [[Householder reflections]] — the stable production route hinted at by the L2 trap. - [[Eigenvalues and the QR algorithm]] — where uniqueness (5.1) keeps iterations well-defined. - [[LU decomposition]] — compare 5.2's Cholesky link to that sibling factorization. --- ## Active Recall > [!recall]- Quick self-check > - How do you read $\det A$ off $R$ (square case)? ::: $|\det A|=\prod_k r_{kk}$. > - What is the residual squared in terms of $Q^\top b$? ::: $\|b\|^2-\sum_{i\le n}(\mathbf q_i^\top b)^2$. > - What identity makes QR = normal equations? ::: $A^\top A=R^\top R$. > - What convention makes QR unique? ::: $r_{kk}>0$.