Orthonormal bases and Gram–Schmidt

Perpendicular axes are a luxury you can build

In Part 2 a basis was any independent set that reaches the whole space. Independence is enough to guarantee that every vector has exactly one recipe, but it says nothing about how hard the recipe is to read. Give me a skewed pair of axes and a point, and I have to solve a two-by-two system to learn the point's coordinates. That is fine for one vector and tiresome for a thousand.

The dot product changes the deal. If the basis vectors are perpendicular to each other and each has length one, then projecting a vector onto an axis is a dot product, and the projection is the coordinate. No system to solve, no inverse, no elimination. The catch is that a basis you are handed is rarely this nice. The question of this part is how to fix that: can you take any independent set and replace it with a perpendicular unit set that spans the same space?

The answer is yes, and the recipe is old and mechanical. Keep the first vector and normalise it. Take the second, subtract its shadow on the first, and what survives points in a genuinely new direction; normalise that. Take the third, subtract its shadows on both of the vectors you have fixed, normalise what is left, and continue. Each subtraction removes exactly the component that was already accounted for, so the leftover is perpendicular to everything before it. This is Gram–Schmidt, and it is the same operation whether you do it with arrows on a page or with columns of a matrix.

There is a second, quieter story in the same process. When you write the original vectors as columns of a matrix A, the orthonormal vectors you built are the columns of a matrix Q, and the coefficients you subtracted along the way fill an upper-triangular matrix R. The equation A = QR is then a complete record of Gram–Schmidt, and it is what numerical software actually computes — usually not by the hand method at all, but by reflections that are far more stable.

It is worth saying why the perpendicular version of a basis is the one worth wanting, beyond tidiness. A generic basis forces every question about a vector to be answered through the whole set at once: change one coordinate and the others shift, because the axes lean on each other. An orthonormal basis disentangles those questions. Each axis answers for its own direction and nothing else, so the coefficient along one axis is a measurement you can take in isolation, and measuring it does not disturb the others. That independence is what projection, least squares and change of basis all rely on, and it is why the first thing a careful computation does with a messy set of directions is make it perpendicular.

Remove what is already accounted for

Start with independent vectors v₁, v₂, v₃, …. The first one is already pointing somewhere new, so all it needs is a length of one: divide it by its own norm and call the result q₁. The second vector is the interesting case. Part of it lies along q₁ and part of it is perpendicular. The part along q₁ is the projection, and the projection coefficient is the dot product v₂ · q₁, because q₁ has length one. Subtract that projection and the remainder is perpendicular to q₁ by construction.

That remainder is the only genuinely new direction v₂ carries. Normalise it and you have q₂. The third vector repeats the operation twice: subtract its projection on q₁, subtract its projection on q₂, and normalise whatever is left. In general, the k-th vector loses its component along every vector already fixed, and the leftover becomes q_k:

Two things are worth noticing before you touch the demo. First, the subtraction is a projection in the sense of Part 8: each term is the shadow of the new vector on one of the fixed axes, and removing all the shadows leaves exactly the perpendicular component. Second, if the new vector lies entirely in the span of the ones already fixed, then every shadow accounts for all of it and the remainder has length zero. Gram–Schmidt does not fail when that happens; it reports that the vector carried no new direction. That is how the process detects dependence.

Picture the order the process works in. It finalises one axis before it looks at the next vector at all, so the perpendicular directions are built up one dimension at a time. That greediness is the point: after the k-th step, the first k unit vectors span exactly the same space as the first k original vectors, and every later vector is guaranteed to be orthogonal to all of them. The output is not unique — reverse the order of the inputs and you get a different orthonormal set, though one that spans the same subspaces step for step. What is forced by the construction is only that the lengths are one and the angles are right; which particular perpendicular directions appear depends on the order you feed the vectors in.

The demo makes the greediness visible. Before any subtraction, you see only the three inputs. Press the button once and the first axis appears, its length scaled to one. Press again and the second vector's shadow on that axis is drawn as a dashed arrow, the residual is drawn in pink, and the residual is then rescaled into the second unit axis. Each press commits one more direction and discards the parts of the input that were already represented.

The third input vector in the demo is built as a combination of the first two, so when its turn comes the two projections together cancel it and the residual collapses to zero. Nothing is added to the orthonormal set, and the readout says so. Feed the process a truly independent vector instead — drag v₁ or v₂ so that the fixed combination no longer matches — and a fresh unit axis appears.

Coordinates by dot product, not by elimination

A set of vectors is orthonormal when every pair of distinct vectors is perpendicular and every vector has length one. Written with dot products, the definition is a single line: the dot of a vector with itself is one, and the dot of two different vectors is zero. Stacked as the columns of a matrix Q, the same statement reads QᵀQ = I — the columns are as independent as it is possible to be.

Why care? Because in an orthonormal basis, finding coordinates is free. To write a vector p as a combination of the axes, dot it with each axis in turn; each dot product is the corresponding coordinate. Compare that with a skewed basis, where the coordinates are the solution of a linear system and every coordinate depends on all the others. The demo lets you rotate an orthonormal frame and drag a point, and it shows both readings side by side: the orthonormal coordinates are the two dot products, and the skewed coordinates are the output of a small solve.

When the orthonormal vectors are square — as many axes as the space has dimensions — the matrix they form is called an orthogonal matrix, and QᵀQ = I says something stronger than it first appears. Since the columns are independent, Q is invertible, and the equation forces its inverse to be its own transpose: Q⁻¹ = Qᵀ. Finding coordinates is then literally multiplying by the transpose, which is exactly the collection of dot products you would compute by hand. An orthogonal matrix also preserves the dot product of any two vectors it multiplies, because (Qx) · (Qy) = xᵀ Qᵀ Q y = xᵀ y. That is a compact way to say it preserves lengths and angles, and it is why these matrices are the vocabulary of rotation.

In two dimensions an orthonormal basis is nothing more exotic than the standard axes after a rotation, which is why dragging one handle rotates the other to stay perpendicular. In higher dimensions the same idea holds and the picture is just harder to draw: a rotation matrix has orthonormal columns, and that single fact is the reason rotations preserve lengths and angles. The determinant of such a matrix is +1 for a pure rotation and −1 when a reflection is included, so the sign of the determinant from Part 5 tells you which kind of frame you are looking at. Part 20 takes up that thread directly.

Writing the whole process as a product

Put the original vectors into the columns of a matrix A, in the order Gram–Schmidt processed them. Put the orthonormal vectors you built into the columns of Q. Every original column is a combination of the orthonormal columns, and the coefficients are exactly the projections you subtracted. Collect those coefficients and you get a matrix R that is upper triangular: column j uses only q₁, …, q_j, so nothing below the diagonal is needed. The identity A = QR is therefore a one-line summary of the entire construction.

Read R carefully and the hand method reappears. Its diagonal entries are the lengths of the residuals — the norms that had to be nonzero for the process to continue — and its off-diagonal entries are the projection coefficients. A zero on the diagonal is a vector that carried no new direction, which is the same as saying the columns of A were dependent and Q did not grow.

The reason to package the process this way is that the factors are useful long after Gram–Schmidt is finished. Q is a set of perpendicular unit directions that span the column space, and R records how the originals were assembled from them. If you later need to solve a least-squares problem with columns A, you do not touch A again: you replace it by QR, and because Q has orthonormal columns it leaves lengths unchanged, so the problem collapses to a triangular solve with R. That triangular system is trivial to work through from the bottom up, and it never needs the product AᵀA that would otherwise square the conditioning. This is the bridge to Part 10, where projection onto a column space is the whole subject.

Nothing in the construction cares that the matrix is square. Feed Gram–Schmidt a tall matrix — more rows than columns — and it produces a Q with the same number of columns as A, each one a unit vector in the larger output space, and a small square R. Feed it a wide matrix and it produces a Q with as many columns as the rank allows and an R that is trapezoidal, with the same zero pattern below the diagonal. The relationship A = QR holds in every case, and the number of genuinely nonzero diagonal entries of R is the rank. That is the same rank from Part 7, now read off a triangular matrix instead of a row reduction.

There is a numerical reason the decomposition is usually computed by something other than the hand recipe. Classical Gram–Schmidt subtracts all the projections at once, and when the vectors are nearly parallel those subtractions can lose orthogonality badly through cancellation. Modified Gram–Schmidt recomputes each projection against the updated remainder, which is what the toolkit's gramSchmidt(vs, { modified: true }) does, and it is markedly better. Householder reflections are better still: each one flips a vector across a carefully chosen plane, and the accumulated reflections build Q while leaving a triangular R. That is the default in LinAlg.mat.qr(A), and it is why a library routine can orthonormalise a nearly dependent set that would wreck the version you do on paper.

The product QR reproduces A to the last displayed digit, QᵀQ comes out as the identity, and R stays upper triangular no matter how you edit the columns. Push the second column toward the first and the picture shows the warning sign: q₂ swings around as the two original columns become nearly parallel, and the entries of R grow. That sensitivity is exactly the conditioning story of Part 19, and it is the practical reason the reflection-based route is preferred.

The process in five lines

A zero residual is information, not an error: it means the current vector was already in the span of the ones before it, so the columns are dependent and the orthonormal set does not grow.

The table is one idea seen from four angles, and it is worth holding them together. Geometrically, Gram–Schmidt is a way of straightening a set of directions until they meet at right angles, one at a time, by shaving off the parts that lean on the directions already fixed. Algebraically, that shaving is a sum of projections, and the projections are dot products because the fixed directions have been rescaled to length one. In the language of coordinates, the outcome is a basis in which reading a coordinate is a single dot product rather than the solution of a system. And in the language of matrices, the whole thing is the factorisation A = QR, with the orthonormal axes in Q and the record of every subtraction in R. When a later part says "project onto the column space" or "solve the least-squares problem with QR", it is using the same four descriptions you have just built.

One idea, two worlds

• Grant Sanderson, "Dot products and duality", Essence of Linear Algebra, 3Blue1Brown — why projection onto a unit direction is a dot product.
• Grant Sanderson, "Change of basis", Essence of Linear Algebra, 3Blue1Brown — the same map described in a different frame, which is what choosing an orthonormal basis does.
• Gilbert Strang, 18.06 Linear Algebra, MIT OpenCourseWare — Lectures 14–16 on orthogonal vectors and projections, and Lecture 17 on Gram–Schmidt and A = QR.
• Immersive Math, Chapter 4 — the coordinate picture that makes an orthonormal basis feel like a rotated set of axes.