The Gram-Schmidt Process — Mathematics Knowledge System

Overview

The Gram-Schmidt process converts any linearly independent set of vectors into an orthogonal (or orthonormal) set that spans the same subspace. It works by processing vectors one at a time: each new vector has its projections onto all previously-built orthogonal vectors subtracted off, leaving only the part that is genuinely new and perpendicular to everything so far. This process is the constructive proof that every finite-dimensional inner product space has an orthonormal basis, and it underlies the QR decomposition of a matrix used throughout numerical linear algebra.

Intuition

Imagine building a set of mutually perpendicular directions one at a time out of a pile of skewed, non-perpendicular vectors. Keep the first vector as-is. For the second, strip away whatever part of it points along the first direction — what's left must be perpendicular to the first. For the third, strip away its shadow along both previous directions — what remains is perpendicular to both. Repeating this, each new vector contributes only the 'genuinely new, orthogonal' part of itself, like peeling off redundant overlap until only clean, independent perpendicular directions remain.

Formal Definition

Definition

Given linearly independent vectors v_1, \ldots, v_k, define orthogonal vectors u_1, \ldots, u_k recursively:

u_1 = v_1

First vector unchanged

u_j = v_j - \sum_{i=1}^{j-1} \frac{\langle v_j, u_i\rangle}{\langle u_i, u_i\rangle} u_i, \qquad j = 2,\ldots,k

Subtract projections onto all earlier u_i

e_j = \frac{u_j}{\|u_j\|}

Normalize to get an orthonormal basis

Worked Examples

Keep the first vector unchanged.
$u_1 = (1,1)$
Subtract the projection of v_2 onto u_1. Compute v_2·u_1 = 0(1)+1(1) = 1, and u_1·u_1 = 1+1 = 2.
$\text{proj}_{u_1}(v_2) = \frac{1}{2}(1,1) = (0.5, 0.5)$
u_2 is v_2 minus that projection.
$u_2 = (0,1) - (0.5,0.5) = (-0.5, 0.5)$

Answer: u_1 = (1,1), u_2 = (-0.5, 0.5). Check: u_1·u_2 = 1(-0.5)+1(0.5) = 0, confirming orthogonality.

Practice Problems

Difficulty 5/10

Apply Gram-Schmidt to v_1 = (1, 0), v_2 = (2, 3) in ℝ². Find u_1 and u_2.

Difficulty 6/10

Apply Gram-Schmidt to v_1 = (1, 1, 0), v_2 = (1, 0, 1) in ℝ³. Find u_1 and u_2.

Difficulty 6/10

Why does the numerical implementation of QR decomposition (used to solve least-squares regression problems) rely on a Gram-Schmidt-like process, and what advantage does an orthonormal basis give when solving Ax = b approximately?

Quiz

Summary

Gram-Schmidt converts independent vectors v_1,...,v_k into orthogonal vectors u_1,...,u_k spanning the same subspace.
Each u_j is v_j with its projections onto all earlier u_i subtracted off, leaving only the orthogonal remainder.
Normalizing the u_j gives an orthonormal basis, the constructive basis for QR decomposition and stable least-squares solving.

References

WebsiteWikipedia — Gram–Schmidt process