Course contentsShow
← Mathematics
Lesson 2225 of 3,12146. Linear Algebra — Inner Products and OrthogonalityFree lesson

Why Gram-Schmidt Works: The Proof

Understand the mathematical justification showing that Gram-Schmidt produces orthogonal vectors at each step.

Why Gram-Schmidt Works: The Proof

You'll learn why the Gram-Schmidt algorithm is mathematically guaranteed to produce orthogonal vectors at every step.

The Core Idea

The Gram-Schmidt algorithm isn't just a recipe—it's built on a clever mathematical principle. At each step, when we create a new orthogonal vector, we're subtracting away all components that point in directions we've already handled. The proof shows that this subtraction process is exactly what's needed to ensure orthogonality.

The Proof Structure

Suppose we've already constructed orthogonal vectors v₁, v₂, ..., vₖ₋₁ from the first k-1 input vectors. Now we want to show that the next Gram-Schmidt vector is orthogonal to all previous ones.

What Gram-Schmidt does:

vₖ = uₖ − proj_{v₁}(uₖ) − proj_{v₂}(uₖ) − ... − proj_{vₖ₋₁}(uₖ)

Why it works: Take any previous vector vᵢ (where i < k) and compute the inner product:

⟨vₖ, vᵢ⟩ = ⟨uₖ, vᵢ⟩ − ⟨proj_{v₁}(uₖ), vᵢ⟩ − ... − ⟨proj_{vᵢ}(uₖ), vᵢ⟩ − ... − ⟨proj_{vₖ₋₁}(uₖ), vᵢ⟩

The magic: Since v₁, v₂, ..., vₖ₋₁ are already orthogonal, every projection term vanishes except the i-th one. That term equals ⟨uₖ, vᵢ⟩ exactly, but with opposite sign!

⟨vₖ, vᵢ⟩ = ⟨uₖ, vᵢ⟩ − ⟨uₖ, vᵢ⟩ = 0 ✓

The projections cancel precisely because they measure and remove the component in each direction.

Key Takeaway: Gram-Schmidt works because subtracting all projections onto previous orthogonal vectors removes exactly the components that would cause non-orthogonality, guaranteed by the linearity of inner products.