QR Decomposition and Gram-Schmidt
Turn any basis into an orthonormal one by subtracting the part that already points the wrong way. Watch the subtraction happen.
Overview
The procedure
Start with vectors that span what you want but are not perpendicular. Gram- Schmidt makes them perpendicular without changing what they span.
First vector: divide by its length. That is q1 — same direction, length 1.
Second vector: it points partly along q1 and partly perpendicular to it. [Project](projections.html) it onto q1, subtract that projection, and what is left is perpendicular by construction. Normalise it to get q2.
The visualisation draws each step. The dashed grey lines are the originals. The solid orange segment is the projection being removed, and the short dashed line is the remainder that becomes q2. The readout gives q1 . q2 — zero to six decimal places, because it cannot be anything else.
For more vectors the pattern repeats: subtract the components along everything already fixed, normalise what survives.
QR Decomposition and Gram-Schmidt
Worth knowing
A = QR: Q holds an orthonormal basis for the columns of A, R holds the coefficients that rebuild them.QR Decomposition and Gram-Schmidt
Manufacturing an orthonormal basis, and the factorisation that makes least squares numerically respectable.
Where R comes from
The projections you subtract are not discarded. Collect them and you have R, and together:
A = Q RQ has the orthonormal vectors as columns; R is upper triangular.
R is triangular for a structural reason worth seeing: the first original vector is built from q1 alone, the second from q1 and q2, the third from the first three. Nothing is ever built from a q that comes later, so everything below the diagonal is zero.
Drag until the two input vectors nearly align. The remainder shrinks toward zero and R becomes nearly singular — which is the same near-dependence [the basis module](basis_span_and_orthogonality.html) warns about, showing up as a small number on the diagonal.
Why least squares uses it
The textbook solution to least squares is the normal equations:
x = (A'A)^-1 A' bCorrect, and numerically poor. Forming A'A squares the condition number. A matrix with condition number 10⁶ — unremarkable for real data — becomes 10¹², and in double precision that has consumed most of the available accuracy before the solve begins.
QR avoids it. Substituting A = QR and using Q'Q = I:
R x = Q' bR is triangular, so this is solved by back-substitution in one pass, and the condition number is never squared. That is why numpy.linalg.lstsq, R's lm and essentially every serious least-squares routine uses QR or an [SVD](singular_value_decomposition.html) rather than the formula in the textbook.
Classical against modified Gram-Schmidt
The version described above is *classical* Gram-Schmidt, and it is unstable in floating point: rounding errors mean the later vectors drift away from orthogonality.
*Modified* Gram-Schmidt subtracts each projection immediately rather than all at once at the end. Algebraically identical, numerically much better behaved.
Serious implementations use neither, preferring Householder reflections, which build Q from a sequence of reflections and are stable regardless of the input. Gram-Schmidt survives because it is the version you can see, which is why it is the version on this page.
Where else it turns up
The QR algorithm for eigenvalues repeatedly factors and re-multiplies in the other order, and the result converges to a triangular matrix whose diagonal holds the eigenvalues. It is one of the most important numerical algorithms there is, and it is this decomposition in a loop.
Orthogonalising features before regression, to remove collinearity.
Kalman filters in square-root form, for the same conditioning reason as least squares.
Gram-Schmidt by hand, on two vectors
The editor below runs the full factorisation; the mechanism is clearest on two vectors small enough to finish on paper. Take a1 = (1, 1) and a2 = (2, 0), which span the plane but meet at 45°, not a right angle.
q1 is a1 normalised: its length is √2, so q1 = (1, 1)/√2.
q2 removes from a2 its component along q1. The projection length is a2 · q1 = 2/√2 = √2, so the projection is √2 · q1 = (1, 1). Subtract it: a2 − (1, 1) = (1, −1). That remainder is perpendicular to q1 by construction, and normalising it (length √2 again) gives q2 = (1, −1)/√2.
Check: q1 · q2 = (1−1)/2 = 0, exactly, as it must be. And the projections you subtracted are R:
| R | value |
|---|---|
| R₁₁ = |a1| | √2 |
| R₁₂ = a2 · q1 | √2 |
| R₂₂ = |remainder| | √2 |
R is upper triangular because a1 was built from q1 alone and only a2 ever used q2 — nothing is ever built from a later q, so everything below the diagonal is zero. That is the whole factorisation, and every larger case is this one repeated.
The reason least squares reaches for this rather than the textbook normal equations is visible in the same small picture. Solving Rx = Q'b uses the triangular R directly and never forms A'A, which would square the condition number — a matrix conditioned at 10⁶ becomes 10¹², and in double precision that discards most of the available digits before the solve even starts. The orthonormal columns are what make Q'Q disappear to the identity, so the substitution costs nothing and the conditioning is left untouched.
The version shown here, subtracting every projection at the end, is *classical* Gram-Schmidt and drifts out of orthogonality in floating point; the *modified* form subtracts each projection immediately and behaves far better, though serious libraries use Householder reflections instead. Gram-Schmidt survives as the version you can watch happen, which is why it is the one worth working by hand.
The same decomposition, run in a loop that factors and re-multiplies in the opposite order, is the QR algorithm for eigenvalues — one of the most important numerical methods there is, and at heart just this factorisation repeated until the matrix goes triangular.
Where it goes wrong
Classical Gram-Schmidt on ill-conditioned input. Use the modified version, or a library.
Forming A'A because the formula is shorter. It squares the conditioning.
Assuming Q is square. For a tall thin A, the economy QR gives a Q with the same shape as A, not a full orthogonal matrix.
Orthogonalise a basis, then solve with it
QR turns any set of columns into an orthonormal set plus the bookkeeping needed to get back. It is how least squares is solved in practice.
Check yourself
0 of …Answer without scrolling back up.
Why is R upper triangular?
Why do least-squares solvers avoid the normal equations?
What does modified Gram-Schmidt change?
QR Decomposition and Gram-Schmidt
Start with vectors that span what you want but are not perpendicular. Gram- Schmidt makes them perpendicular without changing what they span.