The Gram–Schmidt Process

The Gram–Schmidt process is simply a recipe for straightening out a basis: you start with vectors that point in slanted directions and replace them, one at a time, with perpendicular vectors that span the same space. The name isn't descriptive; it's just the two mathematicians it's named after, Jørgen Gram and Erhard Schmidt. What it's good for: the last two lessons kept saying "with an orthogonal basis," and this is how you get one. All we're really saying here is that $\vec v_1$ is just $\vec x_1$, $\vec v_2$ is $\vec x_2$ minus its shadow on $\vec v_1$, and $\vec v_3$ is $\vec x_3$ minus its shadows on $\vec v_1$ and $\vec v_2$. Each fraction in the formula is the same projection weight you've been using since the orthogonal sets lesson. The formula looks long, but it's one move (subtract a shadow) repeated; bear with it.

Think about why it works. Back in the orthogonal sets lesson, you saw that $\vec y$ minus its projection onto $\vec u$ is perpendicular to $\vec u$. Gram–Schmidt just uses that over and over. Subtracting from $\vec x_2$ its shadow on $\vec v_1$ leaves something perpendicular to $\vec v_1$. Subtracting from $\vec x_3$ its shadows on $\vec v_1$ and $\vec v_2$ leaves something perpendicular to both. In other words, $\vec v_3$ is $\vec x_3$ minus its projection onto the plane of $\vec v_1$ and $\vec v_2$, from the last lesson.

So each step keeps only the new direction a vector adds. Nothing is lost along the way: the $\vec v$'s span the same subspaces as the $\vec x$'s at every stage, since each $\vec v_k$ is $\vec x_k$ plus a combination of earlier vectors.

A common mistake. When you compute $\vec v_3$, it's tempting to subtract its projections onto the original $\vec x_1$ and $\vec x_2$, because those are the vectors you were given. That doesn't work: you project onto the new $\vec v_1$ and $\vec v_2$. Adding up shadows only gives the right answer when the vectors you project onto are orthogonal, and the $\vec x$'s usually aren't.

Normalize at the end (divide each $\vec v_i$ by its length) to get an orthonormal basis.

QR factorization packages the process: $Q$ holds the orthonormal vectors and $R = Q^TA$. That formula for $R$ comes from $Q^TQ = I$: multiply $A = QR$ on the left by $Q^T$. $R$ is upper triangular because each column $\vec x_k$ of $A$ only needs $\vec v_1, \dots, \vec v_k$ to rebuild it. It's the numerically stable way to solve least squares and the core of eigenvalue algorithms.

There's an animation further down that shows one Gram–Schmidt step as $\vec x_2$ swings around.

Numerical libraries use QR factorization (Gram–Schmidt's stable cousins) for least squares, and quantum chemistry orthogonalizes orbitals with the same process.