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 aren't at right angles. Gram- Schmidt makes them at right angles 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 it onto q1, subtract that map, and what is left is at right angles by build. Norm it to get q2.
The visualisation draws each step. The dashed grey lines are the originals. The solid orange segment is the map being removed, and the short dashed line is the remainder that turns q2. The readout gives q1 . q2 — zero to six decimal places, because it can't be any of it else.
For more vectors the pattern repeats: subtract the components along all already fixed, norm what lives.
QR Decomposition and Gram-Schmidt
This module needs JavaScript: the
numbers are computed in the page rather than recorded.
Worth knowing
A = QR: Q holds an orthonormal basis for the columns of A, R holds the coefficients that rebuild them.
Gram-Schmidt: normalise the first vector, then subtract from the second everything that points along the first.
The solid orange line is the projection being removed. What remains is perpendicular by construction.
R is upper triangular because the k-th original vector is built only from the first k orthonormal ones.
QR Decomposition and Gram-Schmidt
Making an unit-perp basis, and the factorisation that makes least squares by number fair.
Where R comes from
The maps you subtract aren't discarded. Collect them and you've R, and together:
A = Q R
Q has the unit-perp vectors as columns. R is upper tri.
R is tri for a structural reason worth seeing: the first first 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 all below the main-line is zero.
Drag until the two input vectors nearly align. The remainder shrinks toward zero and R turns nearly singular — which is the same near-dependence the basis module warns about, showing up as a small number on the main-line.
Why least squares uses it
The textbook answer to least squares is the normal equations:
x = (A'A)^-1 A' b
Correct, and by number poor. Forming A'Asquares the rule number. A mat with rule number 10⁶. — plain for real data — turns 10¹², and in double precision that has consumed most of the available fit before the solve begins.
QR avoids it. Substituting A = QR and using Q'Q = I:
R x = Q' b
R is tri, so this is solved by back-substitution in one pass, and the rule number is never squared. That is why numpy.linalg.lstsq, R's lm and each serious least-squares routine uses QR or an SVD rather than the formula in the textbook.
Classical against modified Gram-Schmidt
The version given above is *classical* Gram-Schmidt, and it's unstable in floating point: rounding errors mean the later vectors drift away from perpness.
*Modified* Gram-Schmidt subtracts each map right away rather than all at once at the end. Algebraically the same, by number much better behaved.
Serious setups use neither, preferring Householder reflections, which build Q from a sequence of reflections and are stable even so of the input. Gram-Schmidt lives because it's the version you can see, which is why it's the version on this page.
Where else it turns up
The QR method for eigenvals again and again factors and re-times in the other order, and the result settles to a tri mat whose main-line holds the eigenvals. It's one of the most key numeric methods there's, and it's this breakdown in a loop.
Orthogonalising features before regression, to drop 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 normed: its length is √2. So q1 = (1, 1)/√2.
q2 drops from a2 its component along q1. The map length is a2 · q1 = 2/√2 = √2. So The map is √2 · q1 = (1, 1). Subtract it: a2 − (1, 1) = (1, −1). That remainder is at right angles to q1 by build, and norming it (length √2 again) gives q2 = (1, −1)/√2.
Check: q1 · q2 = (1−1)/2 = 0, just, as it must be. And the maps you subtracted are R:
R
value
R₁₁ = |a1|
√2
R₁₂ = a2 · q1
√2
R₂₂ = |remainder|
√2
R is upper tri because a1 was built from q1 alone and only a2 ever used q2 — nothing is ever built from a later q, so all below the main-line is zero. That is the whole factorisation, and each 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 tri R right and never forms A'A. This Would square the rule number — a mat conditioned at 10⁶. Turns 10¹², and in double precision that discards most of the available digits before the solve even starts. The unit-perp 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 each map at the end, is *classical* Gram-Schmidt and drifts out of perpness in floating point. The *modified* form subtracts each map right away and behaves far better, though serious libraries use Householder reflections instead. Gram-Schmidt lives as the version you can watch happen. This Is why it's the one worth working by hand.
The same breakdown, run in a loop that factors and re-times in the opposite order, is the QR method for eigenvals. One of the most key numeric methods there's, and at heart just this factorisation repeated until the mat goes tri.
Where it goes wrong with QR Decomposition and Gram-Schmidt
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.
given Q is square. For a tall thin A, the economy QR gives a Q with the same shape as A, not a full perp mat.
Questions people ask about QR Decomposition and Gram-Schmidt
What does QR decomposition produce? It writes a matrix A as Q times R, where Q has orthonormal columns and R is upper triangular.
How is QR computed? Textbooks show Gram-Schmidt, but libraries use Householder reflections, which are more stable numerically.
Why use QR for least squares? Solving R x = Q transpose b avoids forming A transpose A, which squares the condition number. It gives more accurate answers.
What goes wrong with classical Gram-Schmidt? Rounding errors accumulate and the columns of Q lose orthogonality when the input columns are nearly dependent. Modified Gram-Schmidt or Householder fixes that.
What is the QR algorithm? An iterative method for eigenvalues that repeatedly factors and recombines as RQ. It is the basis of most eigenvalue solvers.
Does QR work for non-square matrices? Yes. For a tall matrix, the reduced form gives Q the same shape as A and a square R.
Orthogonalise a basis, then solve with it
QR turns any set of columns into an unit-perp set plus the bookkeeping needed to get back. It's how least squares is solved .
example_01.pyNumPy
import numpy as np
A = np.array([[1.0, 1.0, 1.0],
[1.0, 2.0, 4.0],
[1.0, 3.0, 9.0],
[1.0, 4.0, 16.0],
[1.0, 5.0, 25.0]])
Q, R = np.linalg.qr(A)
print("A is %d x %d, Q is %s, R is %s" % (A.shape + (Q.shape, R.shape)))
print()
print("Q has orthonormal columns -- Q.T @ Q is the identity:")
print(np.round(Q.T @ Q, 10) + 0.0)
print()
print("R is upper triangular (zeros below the diagonal):")
print(np.round(R, 4) + 0.0)
print()
print("and they multiply back to A:", np.allclose(Q @ R, A))
print()
b = np.array([2.1, 3.9, 8.2, 14.1, 22.0])
print("least squares fit of a quadratic to 5 points")
via_qr = np.linalg.solve(R, Q.T @ b)
via_normal = np.linalg.solve(A.T @ A, A.T @ b)
print(" via QR ", np.round(via_qr, 6))
print(" via normal eqns ", np.round(via_normal, 6))
print(" numpy's lstsq ", np.round(np.linalg.lstsq(A, b, rcond=None)[0], 6))
print()
print("all three agree here. QR is preferred because it never forms A.T @ A,")
print("which squares the condition number and throws away precision:")
print(" condition number of A %.3e" % np.linalg.cond(A))
print(" condition number of A.T@A %.3e" % np.linalg.cond(A.T @ A))
Output
Check yourself
0 of 3
Answer without scrolling back up.
Why is R upper triangular?
Nothing is ever built from a q that comes later, so everything below the diagonal is zero - which then makes back-substitution possible as a consequence.
Why do least-squares solvers avoid the normal equations?
A condition number of 10^6 becomes 10^12. QR gives Rx = Q'b, solved by back-substitution, with the conditioning never squared.
What does modified Gram-Schmidt change?
Algebraically identical, numerically much better. Serious implementations use Householder reflections instead, which are stable regardless of input.
Cheat sheet
QR Decomposition and Gram-Schmidt
Orthogonalise a set of vectors with Gram-Schmidt and factor the matrix into Q times R. See why this makes least squares numerically stable.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.