Gram-Schmidt orthogonalization — algorithm: Visual walkthrough

Step 0 — What is a vector, and what is "leaning along"?

WHAT. A vector is an arrow with a length and a direction. In the plane we write it as a pair of numbers $v = (v_{x}, v_{y})$ : go $v_{x}$ steps right, then $v_{y}$ steps up, and the tip of your pencil is where the arrow points.

WHY start here. Everything that follows is about how much one arrow leans along another. Before we can measure "lean" we need one number that captures it. That number is the inner product (also called dot product).

PICTURE. Two arrows share a tail. The angle between them is what $⟨ a, b ⟩$ secretly measures — and it hits exactly $0$ when that angle is $9 0^{\circ}$ .

Figure — Gram-Schmidt orthogonalization — algorithm

Recall Why is "

$⟨ a, b ⟩ = 0$ means perpendicular" believable? $⟨ a, b ⟩ = ∥ a ∥ ∥ b ∥ cos θ$ , where $θ$ is the angle between them. Perpendicular means $θ = 9 0^{\circ}$ , and $cos 9 0^{\circ} = 0$ , so the whole thing is $0$ . ::: The cosine is the bridge between arithmetic and geometry.

Step 1 — The shadow: projecting one arrow onto another

WHAT. Shine a light straight down onto a clean reference direction $u$ . The messy arrow $v$ casts a shadow on the line through $u$ . That shadow is a scaled copy $c u$ of the reference. We must find the one number $c$ .

WHY this tool and not another. We could try to "eyeball" how far along $u$ the vector $v$ reaches — but Gram–Schmidt needs the exact amount so that whatever is left over is perfectly perpendicular. There is only one $c$ that does this, and the inner product hands it to us. This single operation is Orthogonal projection, the beating heart of the whole algorithm.

PICTURE. The shadow $c u$ lands on the line; the dashed drop from the tip of $v$ meets $u$ at a right angle. The leftover arrow $r = v - c u$ is that dashed drop — and it is perpendicular to $u$ .

Now let's force the right angle and solve for $c$ .

Step 2 — Keep the leftover, and it is guaranteed perpendicular

WHAT. Subtract the shadow from $v$ . What remains, $r = v - proj_{u} (v),$ is the part of $v$ that had nothing to do with $u$ .

WHY. We chose $c$ precisely so $⟨ r, u ⟩ = 0$ . This is not luck — it was the equation we solved. So $r$ points in a brand-new, independent direction, at a clean right angle to $u$ .

PICTURE. Watch $v$ split into two arrows placed head-to-tail: the horizontal shadow along $u$ , and the vertical leftover $r$ climbing off at exactly $9 0^{\circ}$ . The two shadows add back up to $v$ .

Step 3 — First worked pair: $v_{1} = (3, 1), v_{2} = (2, 2)$

WHAT. Take the very first vector as-is — it needs no cleaning because there is nothing yet to be perpendicular to: $u_{1} = v_{1} = (3, 1) .$ Then clean $v_{2}$ against $u_{1}$ .

WHY. With only one settled direction, the recursion has a single term. We compute the shadow of $v_{2}$ on $u_{1}$ and subtract it.

$2 \cdot 3 + 2 \cdot 1 = 8 ⟨ v_{2}, u_{1} ⟩, 9 + 1 = 10 ⟨ u_{1}, u_{1} ⟩, c = \frac{8}{10} .$

$u_{2} = (2, 2) - \frac{8}{10} (3, 1) = (2, 2) - (2.4, 0.8) = (- 0.4, 1.2) .$

$(2, 2)$ — the messy input $v_{2}$ .
$(2.4, 0.8)$ — its shadow on $u_{1}$ .
$(- 0.4, 1.2)$ — the pure leftover, and $⟨ u_{1}, u_{2} ⟩ = 3 (- 0.4) + 1 (1.2) = 0$ . ✅

PICTURE. $u_{1}$ sits at a shallow slope; $v_{2}$ points up-right; the amber shadow lands on $u_{1}$ ; the cyan leftover $u_{2}$ shoots off perpendicular.

Step 4 — Why we subtract from $u_{j}$ , never from $v_{j}$

WHAT. In the recursion the shadows are cast onto the already-orthogonalized $u_{j}$ , not the original messy $v_{j}$ .

WHY. Take the general recursion and dot it with an earlier $u_{i}$ (with $i < k$ ):

= \langle v_k,u_i\rangle - \sum_{j<k}\frac{\langle v_k,u_j\rangle}{\langle u_j,u_j\rangle}\underbrace{\langle u_j,u_i\rangle}_{\text{= }0\text{ unless }j=i}.$$ Because the $u$'s are *mutually perpendicular*, every cross term $\langle u_j,u_i\rangle$ dies except the one where $j=i$. That surviving term cancels the first piece exactly: $$= \langle v_k,u_i\rangle - \frac{\langle v_k,u_i\rangle}{\langle u_i,u_i\rangle}\langle u_i,u_i\rangle = 0.$$ If instead we used the raw $v_j$, the cross terms $\langle v_j,v_i\rangle$ would **not** vanish — the cancellation collapses and $u_k$ is left tilted, not perpendicular. **PICTURE.** Left panel: subtracting shadows onto clean orthogonal $u_1,u_2$ leaves a leftover standing straight up. Right panel: subtracting onto the tangled $v_1,v_2$ leaves a leftover that still leans — the method fails. ![[deepdives/dd-maths-4.5.35-d2-s05.png]] --- ## Step 5 — Two subtractions at once in $\mathbb{R}^3$ **WHAT.** With $v_1=(1,1,0),\ v_2=(1,0,1),\ v_3=(0,1,1)$, the third vector must lose its shadow on **both** settled directions $u_1$ and $u_2$. - $u_1=(1,1,0)$. - $u_2 = v_2-\frac{\langle v_2,u_1\rangle}{\langle u_1,u_1\rangle}u_1=(1,0,1)-\frac12(1,1,0)=\left(\tfrac12,-\tfrac12,1\right).$ - For $u_3$, two overlaps: $$\frac{\langle v_3,u_1\rangle}{\langle u_1,u_1\rangle}=\frac12,\qquad \frac{\langle v_3,u_2\rangle}{\langle u_2,u_2\rangle}=\frac{1/2}{3/2}=\frac13.$$ $$u_3=(0,1,1)-\tfrac12(1,1,0)-\tfrac13\left(\tfrac12,-\tfrac12,1\right)=\left(-\tfrac23,\tfrac23,\tfrac23\right).$$ **WHY two terms.** There are two already-clean directions to be perpendicular to, so we erase two shadows. Each subtraction is Step 2, done independently — and *because* $u_1\perp u_2$, removing one shadow never re-introduces the other. **Check:** $\langle u_3,u_1\rangle=-\tfrac23+\tfrac23+0=0$ and $\langle u_3,u_2\rangle=-\tfrac13-\tfrac13+\tfrac23=0$. ✅ **PICTURE.** In 3D, $v_3$ drops two shadows onto the plane spanned by $u_1$ and $u_2$; removing both leaves $u_3$ pointing straight out of that plane. ![[deepdives/dd-maths-4.5.35-d2-s06.png]] --- ## Step 6 — Normalize: shrink each to unit length **WHAT.** We now have perpendicular arrows of assorted lengths. To make an [[Orthonormal basis]], divide each by its own length: $$e_k=\frac{u_k}{\lVert u_k\rVert},\qquad \lVert u_k\rVert=\sqrt{\langle u_k,u_k\rangle}.$$ For Step 3: $\lVert u_1\rVert=\sqrt{10}$, $\lVert u_2\rVert=\sqrt{1.6}$, giving $$e_1=\tfrac{1}{\sqrt{10}}(3,1),\qquad e_2=\tfrac{1}{\sqrt{1.6}}(-0.4,1.2).$$ **WHY.** Direction is untouched by scaling, so perpendicularity survives. Unit length is what makes projections lose their denominators and what turns the columns into the $Q$ of a [[QR decomposition]]. **PICTURE.** Same right angle as before, but both arrows now reach exactly to the unit circle. ![[deepdives/dd-maths-4.5.35-d2-s07.png]] --- ## Step 7 — The degenerate case: a dependent input collapses to zero **WHAT.** Suppose $v_2$ is just a stretched copy of $v_1$, say $v_2=2v_1$. Then $v_2$ is entirely shadow — its whole self leans along $u_1$. **WHY.** The shadow equals $v_2$, so $$u_2 = v_2-\operatorname{proj}_{u_1}(v_2)=v_2-v_2=\mathbf{0}.$$ A **zero vector** has no direction and length $0$, so you cannot normalize (division by zero). Gram–Schmidt is *telling you* the input was not independent — see [[Linear independence]]. This is not a bug; it's a built-in detector. **PICTURE.** $v_2$ lies flat on top of $u_1$; its shadow covers it completely; the leftover shrinks to a single point at the origin. ![[deepdives/dd-maths-4.5.35-d2-s08.png]] > [!mistake] Expecting a nonzero $u_k$ from dependent vectors > **Why it feels right:** the formula still "runs" and returns *something*. **Fix:** that something is $\mathbf 0$. Whenever $u_k=\mathbf 0$, drop $v_k$ — it added no new direction. This is exactly how the algorithm reports linear dependence. --- ## The one-picture summary Below, the entire derivation on a single diagram: messy inputs enter on the left, each new vector sheds its shadows on every settled direction, the leftovers stack up at right angles, and normalization tucks them onto the unit circle. ![[deepdives/dd-maths-4.5.35-d2-s09.png]] > [!formula] Everything on one line > $$u_1=v_1,\qquad u_k=v_k-\sum_{j<k}\frac{\langle v_k,u_j\rangle}{\langle u_j,u_j\rangle}u_j,\qquad e_k=\frac{u_k}{\lVert u_k\rVert}.$$ > [!recall]- Feynman: retell the whole walkthrough > Imagine flashlights and a wall. First, I keep my very first arrow exactly as it is — call it the reference, nothing to fix yet. For the next arrow, I shine a light down onto the reference and see the shadow it casts; that shadow is the part they share. I slide the arrow back by exactly that shadow, and the piece left over now stands at a perfect right angle to the reference — that's guaranteed, because I picked the shadow size to make the leftover perpendicular. For the third arrow I do the same trick twice: remove its shadow on the first clean direction and its shadow on the second, and the leftover pops straight out, perpendicular to both. Because I always subtract shadows onto the *already-cleaned* arrows (not the raw ones), the shadows never interfere and every cross-overlap cancels cleanly. If an arrow was secretly a stretched copy of one I already have, its whole self is shadow and the leftover shrinks to nothing — the algorithm just told me the arrows weren't independent. Finally I shrink each surviving arrow to length one. Done: same space, all right angles, all unit length. Remove the overlap, keep the leftover. ::: That single mantra *is* Gram–Schmidt. --- ## Connections - [[Inner product spaces]] — supplies the $\langle\cdot,\cdot\rangle$ that detects right angles - [[Orthogonal projection]] — the shadow operation of Steps 1–2 - [[Orthonormal basis]] — the unit-length output of Step 6 - [[QR decomposition]] — the columns $e_k$ become $Q$ - [[Linear independence]] — the collapse in Step 7 detects its failure - [[Least squares]] — orthogonal directions decouple the equations - [[Gram-Schmidt orthogonalization — algorithm]] — the parent formula this page draws