Gram-Schmidt orthogonalization — algorithm

What it does

Deriving the algorithm from scratch (HOW + WHY)

The whole machine rests on ONE tool: projection of a vector onto another vector.

Step 1 — Project $v$ onto $u$ . We want a scalar $c$ such that $cu$ is the shadow of $v$ along $u$ , and the leftover $r = v - cu$ is orthogonal to $u$ . Impose orthogonality: $\langle v - cu,\; u\rangle = 0 \implies \langle v,u\rangle - c\langle u,u\rangle = 0 \implies c = \frac{\langle v,u\rangle}{\langle u,u\rangle}.$

Step 2 — Build the orthogonal set one vector at a time.

$u_1 = v_1$ (first vector is already "clean"; nothing to remove yet).
For each new $v_k$ , subtract its overlap with every already-built $u_1,\dots,u_{k-1}$ :

Why subtract from all previous $u_j$ ? Each $u_j$ is already mutually orthogonal, so removing the overlap with each one independently leaves $u_k$ perpendicular to all of them simultaneously. Let's prove the key claim.

Worked example Proof that

$u_k \perp u_i$ for $i<k$ Take the inner product of the recursion with $u_i$ : $\langle u_k,u_i\rangle = \langle v_k,u_i\rangle - \sum_{j<k}\frac{\langle v_k,u_j\rangle}{\langle u_j,u_j\rangle}\langle u_j,u_i\rangle.$ Why this step? Inductively, $\langle u_j,u_i\rangle = 0$ for $j\ne i$ , so the whole sum collapses to the single $j=i$ term: $= \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 = \langle v_k,u_i\rangle - \langle v_k,u_i\rangle = 0. \;\checkmark$

Figure — Gram-Schmidt orthogonalization — algorithm

Worked Example 1 (in $\mathbb{R}^2$ )

Orthonormalize $v_1=(3,1),\; v_2=(2,2)$ .

Step A: $u_1 = v_1 = (3,1)$ . Why? First vector is taken as-is.

Step B: $\langle v_2,u_1\rangle = 2\cdot3 + 2\cdot1 = 8$ , and $\langle u_1,u_1\rangle = 9+1 = 10$ . $u_2 = (2,2) - \frac{8}{10}(3,1) = (2,2) - (2.4,\,0.8) = (-0.4,\,1.2).$ Why? We removed the part of $v_2$ leaning along $u_1$ .

Check: $\langle u_1,u_2\rangle = 3(-0.4)+1(1.2) = -1.2+1.2 = 0.$ ✅

Step C — normalize: $\lVert u_1\rVert=\sqrt{10}$ , $\lVert u_2\rVert=\sqrt{0.16+1.44}=\sqrt{1.6}$ . $e_1 = \tfrac{1}{\sqrt{10}}(3,1),\qquad e_2 = \tfrac{1}{\sqrt{1.6}}(-0.4,1.2).$

Worked Example 2 (in $\mathbb{R}^3$ )

Orthogonalize $v_1=(1,1,0),\; v_2=(1,0,1),\; v_3=(0,1,1)$ .

$u_1=(1,1,0)$ .
$\langle v_2,u_1\rangle = 1$ , $\langle u_1,u_1\rangle=2$ : $u_2=(1,0,1)-\tfrac12(1,1,0)=(\tfrac12,-\tfrac12,1).$
For $u_3$ subtract overlaps with both $u_1$ and $u_2$ . $\langle v_3,u_1\rangle = 1,\ \langle u_1,u_1\rangle=2$ . $\langle v_3,u_2\rangle = 0-\tfrac12+1=\tfrac12,\ \langle u_2,u_2\rangle=\tfrac14+\tfrac14+1=\tfrac32$ . $u_3=(0,1,1)-\tfrac12(1,1,0)-\tfrac{1/2}{3/2}(\tfrac12,-\tfrac12,1)=(0,1,1)-(\tfrac12,\tfrac12,0)-(\tfrac16,-\tfrac16,\tfrac13).$ $u_3=(-\tfrac23,\tfrac23,\tfrac23).$ Why this step? Two subtractions because there are two earlier orthogonal vectors to clear. Check: $\langle u_3,u_1\rangle = -\tfrac23+\tfrac23+0=0$ , $\langle u_3,u_2\rangle=-\tfrac13-\tfrac13+\tfrac23=0$ . ✅

Common mistakes

Recall Feynman: explain to a 12-year-old

Imagine your friends each cast a shadow on a wall. You want everyone to stand in directions where their shadows don't overlap at all. Take the first friend as the reference. For the next friend, look at how much they overlap the first one's direction, and slide them sideways until that overlap is zero. For each new friend, remove the overlap with everyone already placed. After that, all friends point in totally separate (right-angle) directions, and you can shrink each to the same height (unit length). That's Gram–Schmidt: remove the overlap, keep the leftover.

Flashcards

What single operation is the building block of Gram–Schmidt?

Projection of a vector onto another:

\operatorname{proj}_u(v)=\frac{\langle v,u\rangle}{\langle u,u\rangle}u

Why does subtracting the projection make the residual orthogonal?

We choose the scalar

c=\frac{\langle v,u\rangle}{\langle u,u\rangle}

exactly so

\langle v-cu,u\rangle=0

State the Gram–Schmidt recursion.

u_k=v_k-\sum_{j<k}\frac{\langle v_k,u_j\rangle}{\langle u_j,u_j\rangle}u_j

Why subtract from the

u_j

and not the

v_j

Only the

u_j

are already mutually orthogonal, so cross terms vanish; using

v_j

leaves nonzero overlaps.

What does it mean if some

u_k=0

during the process?

v_k

was linearly dependent on earlier vectors; the input set was not independent.

How do you get an orthonormal set from the orthogonal one?

Divide each

u_k

by its norm:

e_k=u_k/\lVert u_k\rVert

If you use already-normalized

e_j

, how does the recursion simplify?

u_k=v_k-\sum_{j<k}\langle v_k,e_j\rangle e_j

(denominators become 1).

What matrix factorization is Gram–Schmidt equivalent to?

A=QR

, with

Q

's columns the orthonormal

e_k

and

R

upper-triangular holding the projection coefficients.

Connections

Inner product spaces — the $\langle\cdot,\cdot\rangle$ Gram–Schmidt relies on
Orthogonal projection — the single primitive operation reused
QR decomposition — Gram–Schmidt is one way to compute $Q$ and $R$
Linear independence — required for the input set
Orthonormal basis — the output object
Least squares — uses orthogonal bases to decouple the normal equations

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, Gram–Schmidt ka core idea bilkul simple hai: tumhare paas kuch independent vectors hain jo tedhe-medhe directions mein point kar rahe hain, aur tum chahte ho ki unko aise vectors mein convert kar do jo aapas mein perpendicular (90 degree) ho, lekin same space ko span karein. Iska fayda yeh hai ki perpendicular directions mein coordinates independent ho jaate hain, projections aasan ho jaate hain, aur QR decomposition jaisa kaam clean nikalta hai.

Pura algorithm ek hi tool pe khada hai — projection. Agar tumhare paas ek saaf direction $u$ hai aur ek messy vector $v$ hai, to $v$ ka jo hissa $u$ ke along jhukta hai woh hai $\operatorname{proj}_u(v)=\frac{\langle v,u\rangle}{\langle u,u\rangle}u$ . Ab agar tum yeh shadow subtract kar do, jo bachta hai woh automatically $u$ ke perpendicular hota hai. Yeh scalar $c$ koi guess nahi hai — humne use force kiya $\langle v-cu,u\rangle=0$ se, isliye answer guaranteed perpendicular aata hai.

Ab algorithm: pehla vector $u_1=v_1$ as-it-is. Har naye $v_k$ se uske saare pehle ban chuke clean vectors $u_1,\dots,u_{k-1}$ ke shadows subtract kar do. Ek bahut common galti — students $v_j$ pe project karte hain, but karna $u_j$ pe hai, kyunki sirf $u_j$ aapas mein orthogonal hain, isliye cross terms zero ho jaate hain aur proof chalta hai. End mein har vector ko uski length se divide karke unit (orthonormal) bana lo. Agar koi $u_k$ zero aa jaye, matlab tumhare input vectors independent the hi nahi.

Gram-Schmidt orthogonalization — algorithm

What it does

Deriving the algorithm from scratch (HOW + WHY)

Worked Example 1 (in $\mathbb{R}^2$ )

Worked Example 2 (in $\mathbb{R}^3$ )

Common mistakes

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Linear Algebra (Full)

Connections