QR decomposition

WHAT is QR decomposition?

WHY do we want this?

• Solving least squares $\min \|Ax-b\|$ becomes trivial: $Rx = Q^\top b$ (just back-substitution, no normal-equation squaring that wrecks numerical accuracy).
• Orthonormal columns mean lengths and angles are preserved — $Q$ is a rotation/reflection.
• It is the engine of the QR algorithm for eigenvalues.

HOW: derive QR from Gram–Schmidt (first principles)

Let $A=[\mathbf a_1 \mid \mathbf a_2 \mid \cdots \mid \mathbf a_n]$ (columns).

Step 1 — make the first axis. We need a unit vector pointing along $\mathbf a_1$: $\mathbf u_1=\mathbf a_1,\qquad \mathbf q_1=\frac{\mathbf u_1}{\|\mathbf u_1\|}.$ Why? $\mathbf q_1$ is our first orthonormal direction; everything else will be measured against it.

Step 2 — remove what's already explained. For $\mathbf a_2$, subtract its shadow (projection) onto $\mathbf q_1$: $\mathbf u_2=\mathbf a_2-(\mathbf q_1^\top\mathbf a_2)\,\mathbf q_1,\qquad \mathbf q_2=\frac{\mathbf u_2}{\|\mathbf u_2\|}.$ Why? The leftover $\mathbf u_2$ is the part of $\mathbf a_2$ perpendicular to $\mathbf q_1$, so $\mathbf q_2\perp\mathbf q_1$.

Step k — subtract all previous shadows. $\mathbf u_k=\mathbf a_k-\sum_{i<k}(\mathbf q_i^\top\mathbf a_k)\,\mathbf q_i,\qquad \mathbf q_k=\frac{\mathbf u_k}{\|\mathbf u_k\|}.$

Step — read off $R$. Invert each relation to express the original $\mathbf a_k$ in terms of the $\mathbf q_i$: $\mathbf a_k=\underbrace{\|\mathbf u_k\|}_{r_{kk}}\,\mathbf q_k+\sum_{i<k}\underbrace{(\mathbf q_i^\top\mathbf a_k)}_{r_{ik}}\,\mathbf q_i.$

So the coefficient of $\mathbf q_i$ in $\mathbf a_k$ is $\boxed{r_{ik}=\mathbf q_i^\top\mathbf a_k\ (i<k),\qquad r_{kk}=\|\mathbf u_k\|,\qquad r_{ik}=0\ (i>k).}$

Stacking $\mathbf a_k=\sum_i r_{ik}\mathbf q_i$ over all $k$ is exactly the matrix equation $A=QR$. ∎

Worked Example 1 — a clean $2\times 2$

$A=\begin{bmatrix}1 & 1\\ 0 & 1\\ 1 & 0\end{bmatrix}.$

Column 1. $\mathbf u_1=\mathbf a_1=(1,0,1)$, $\|\mathbf u_1\|=\sqrt2$. $\mathbf q_1=\tfrac1{\sqrt2}(1,0,1)$. Why this step? First axis = normalized first column.

Projection coefficient. $r_{12}=\mathbf q_1^\top\mathbf a_2=\tfrac1{\sqrt2}(1\cdot1+0\cdot1+1\cdot0)=\tfrac1{\sqrt2}$. Why? This measures how much of $\mathbf a_2$ already lies along $\mathbf q_1$.

Column 2. $\mathbf u_2=\mathbf a_2-r_{12}\mathbf q_1=(1,1,0)-\tfrac1{\sqrt2}\cdot\tfrac1{\sqrt2}(1,0,1)=(\tfrac12,1,-\tfrac12).$ $\|\mathbf u_2\|=\sqrt{\tfrac14+1+\tfrac14}=\sqrt{\tfrac32}$, so $r_{22}=\sqrt{3/2}$. $\mathbf q_2=\tfrac{1}{\sqrt{3/2}}(\tfrac12,1,-\tfrac12)$.

Result. $Q=\begin{bmatrix}\tfrac1{\sqrt2}&\tfrac{1/2}{\sqrt{3/2}}\\[2pt]0&\tfrac{1}{\sqrt{3/2}}\\[2pt]\tfrac1{\sqrt2}&\tfrac{-1/2}{\sqrt{3/2}}\end{bmatrix},\quad R=\begin{bmatrix}\sqrt2&\tfrac1{\sqrt2}\\0&\sqrt{3/2}\end{bmatrix}.$ Check: $Q^\top Q=I$ and $QR=A$.

Worked Example 2 — least squares via QR

Solve $\min\|Ax-b\|$ with the $A$ above and $b=(1,2,3)$.

Why QR helps. $\|Ax-b\|^2=\|QRx-b\|^2$. Since $Q$ preserves length, multiply inside by $Q^\top$ (extend to full $Q$): the minimizer satisfies $Rx=Q^\top b.$ Why? $A=QR\Rightarrow A^\top A x=A^\top b\Rightarrow R^\top Q^\top QR\,x=R^\top Q^\top b\Rightarrow R^\top R x=R^\top Q^\top b$. Cancel invertible $R^\top$: $Rx=Q^\top b$. No squaring of $A$ → numerically stable.

Compute $Q^\top b$:

• $(\mathbf q_1^\top b)=\tfrac1{\sqrt2}(1+0+3)=\tfrac4{\sqrt2}=2\sqrt2.$
• $(\mathbf q_2^\top b)=\tfrac1{\sqrt{3/2}}(\tfrac12\cdot1+1\cdot2-\tfrac12\cdot3)=\tfrac{1}{\sqrt{3/2}}\cdot 1=\sqrt{2/3}.$

Back-substitute $Rx=Q^\top b$: Row 2: $\sqrt{3/2}\,x_2=\sqrt{2/3}\Rightarrow x_2=\tfrac{\sqrt{2/3}}{\sqrt{3/2}}=\tfrac{2}{3}.$ Row 1: $\sqrt2\,x_1+\tfrac1{\sqrt2}x_2=2\sqrt2\Rightarrow x_1=2-\tfrac12 x_2=2-\tfrac13=\tfrac53.$

So $x=(\tfrac53,\tfrac23)$. Why trust it? Triangular solve is exact and avoids forming $A^\top A$.

Forecast-then-Verify

Common Mistakes

Active Recall

Connections

• Gram-Schmidt process — the algorithm QR packages.
• Orthonormal bases and projections — projections $=\mathbf q_i^\top\mathbf a_k$ are the entries of $R$.
• Least squares and normal equations — QR is the stable solver.
• Householder reflections — production-grade way to get QR.
• Eigenvalues and the QR algorithm — iterating $A_{k+1}=R_kQ_k$.
• LU decomposition — sibling factorization (triangular but not orthogonal).

Concept Map

Hinglish (regional understanding)