The Gram-Schmidt process

When you reach for it

Meseret, Biruk and Kidist run a robotics lab. Their camera rig reports a position as amounts along three sensor axes which, in the lab’s calibration frame (units of decimeters), are

The axes are skewed: \mathbf{x}_1 \cdot \mathbf{x}_2 = 9 \neq 0. A reading (c_1, c_2, c_3) means the point c_1\mathbf{x}_1 + c_2\mathbf{x}_2 + c_3\mathbf{x}_3, so turning a point into a reading means solving a system. Along perpendicular unit axes, each coordinate would be one dot product. The team wants perpendicular axes that keep the first new axis along \mathbf{x}_1 and the first two in the plane of \mathbf{x}_1 and \mathbf{x}_2.

Reach for the Gram-Schmidt process whenever a subspace W of \mathbb{R}^n is given by a basis, or any spanning list, and an orthogonal or orthonormal basis of W is needed: to project onto W (Orthogonal bases and projection onto a subspace), to read off coordinates by dot products, or to factor A = QR. That lesson’s last example repaired a basis of a plane with one subtraction; here the subtraction is repeated for any number of vectors, with a proof that it always works.

The procedure

Subtract the projections onto what is already built

Let \mathbf{x}_1, \dots, \mathbf{x}_p be a basis of a subspace W of \mathbb{R}^n. Keep the first vector, and from each later vector remove its projections onto the new vectors already built:

for k = 2, \dots, p.

Write X_k = \operatorname{span}\{\mathbf{x}_1, \dots, \mathbf{x}_k\}. Once \mathbf{v}_1, \dots, \mathbf{v}_{k-1} are known to be an orthogonal basis of X_{k-1}, the subtracted sum is exactly \operatorname{proj}_{X_{k-1}} \mathbf{x}_k, so

the residual of \mathbf{x}_k, which is orthogonal to X_{k-1} by the orthogonal decomposition theorem of Orthogonal bases and projection onto a subspace. Each step keeps the part of \mathbf{x}_k that is new. The figure shows one step in the plane.

For an orthonormal basis, divide each vector by its length: \mathbf{q}_k = \mathbf{v}_k / \lVert \mathbf{v}_k \rVert. Any \mathbf{v}_i may be replaced by a nonzero multiple partway through, to clear fractions, because a projection onto a line does not depend on which vector of the line is used (Exercise 8).

Why it works

Theorem 1 (Gram-Schmidt). If \mathbf{x}_1, \dots, \mathbf{x}_p is a basis of W, then \mathbf{v}_1, \dots, \mathbf{v}_p are nonzero and orthogonal, and for every k,

So \{\mathbf{v}_1, \dots, \mathbf{v}_p\} is an orthogonal basis of W, and \{\mathbf{q}_1, \dots, \mathbf{q}_p\} is an orthonormal basis of W.

Proof, by induction on k. For k = 1: \mathbf{v}_1 = \mathbf{x}_1 is nonzero because a vector of an independent set is never \mathbf{0}, and the two spans are the same line.

Now suppose \mathbf{v}_1, \dots, \mathbf{v}_{k-1} are nonzero, orthogonal, and span X_{k-1}. The denominators \mathbf{v}_i \cdot \mathbf{v}_i are positive, so \mathbf{v}_k is defined.

In X_k: each \mathbf{v}_i with i < k lies in X_{k-1} \subseteq X_k, and so does \mathbf{x}_k, so their combination \mathbf{v}_k does. Nonzero: if \mathbf{v}_k = \mathbf{0}, then \mathbf{x}_k equals the subtracted combination, so it lies in X_{k-1}, against the independence of the \mathbf{x}’s (Linear independence). Orthogonal: dot the definition with \mathbf{v}_j, j < k. Every \mathbf{v}_i \cdot \mathbf{v}_j with i \neq j is 0 by the hypothesis, which leaves

Same span: \mathbf{v}_1, \dots, \mathbf{v}_k are k nonzero orthogonal vectors, hence independent (Orthogonal bases and projection onto a subspace), inside the k-dimensional space X_k, so they span it (Basis and dimension).

That completes the induction. \square

Moving the subtracted terms to the other side gives

each old vector is its new vector plus earlier new vectors. That triangular pattern is the QR factorization below.

When the list is dependent

The same formulas can be run on a list that spans W but may not be independent. Suppose \mathbf{v}_1, \dots, \mathbf{v}_{k-1} have come out nonzero, so they are an orthogonal basis of X_{k-1}. Then \mathbf{v}_k = \mathbf{0} exactly when \mathbf{x}_k lies in X_{k-1}. If \mathbf{v}_k = \mathbf{0}, then \mathbf{x}_k equals its projection, which lies in X_{k-1}. If \mathbf{x}_k lies in X_{k-1}, its projection onto X_{k-1} is \mathbf{x}_k itself, by the weights formula for an orthogonal basis, so \mathbf{v}_k = \mathbf{0}.

So a zero vector says that \mathbf{x}_k adds nothing to the span so far. Drop it and continue with \mathbf{x}_{k+1}, which is the run on the shorter list. The nonzero \mathbf{v}’s form an orthogonal basis of the span of the whole list, and their number is its dimension.

The order matters, the spans do not

Since \mathbf{v}_1 = \mathbf{x}_1, listing the vectors in another order generally gives another orthogonal basis of W. What does not change: \mathbf{v}_k = \mathbf{x}_k - \operatorname{proj}_{X_{k-1}} \mathbf{x}_k depends only on \mathbf{x}_k and the subspace X_{k-1}, and a projection does not depend on which orthogonal basis of the subspace computes it. So reordering the first k - 1 vectors leaves \mathbf{v}_k, and every vector after it, unchanged (Exercise 20).

The QR factorization

Theorem 2 (QR factorization). Let A be an n \times p matrix with independent columns \mathbf{x}_1, \dots, \mathbf{x}_p, and let \mathbf{q}_1, \dots, \mathbf{q}_p be the orthonormal basis of its column space given by the Gram-Schmidt process. Let Q be the n \times p matrix with columns \mathbf{q}_1, \dots, \mathbf{q}_p, and R the p \times p matrix with entries r_{ij} = \mathbf{q}_i \cdot \mathbf{x}_j for i \leq j and 0 below the diagonal. Then

R is upper triangular with diagonal entries r_{kk} = \lVert \mathbf{v}_k \rVert > 0, and R is invertible.

Proof. By Theorem 1, \mathbf{x}_j lies in \operatorname{span}\{\mathbf{q}_1, \dots, \mathbf{q}_j\}, and the weights in an orthonormal basis are single dot products (Orthogonal bases and projection onto a subspace), so \mathbf{x}_j = r_{1j}\mathbf{q}_1 + \dots + r_{jj}\mathbf{q}_j. Column j of QR is Q times column j of R, the combination of the columns of Q with weights r_{1j}, \dots, r_{jj}, 0, \dots, 0 (Matrix multiplication), which is \mathbf{x}_j. So QR = A, and the zeros below the diagonal come from \mathbf{x}_j needing only \mathbf{q}_1, \dots, \mathbf{q}_j. For the diagonal, \mathbf{x}_k is \mathbf{v}_k plus a combination of \mathbf{v}_1, \dots, \mathbf{v}_{k-1}, each orthogonal to \mathbf{q}_k, so r_{kk} = \mathbf{q}_k \cdot \mathbf{v}_k = \lVert \mathbf{v}_k \rVert, positive since \mathbf{v}_k \neq \mathbf{0}. The determinant of a triangular matrix is the product of its diagonal entries (Properties of determinants: row operations, products, transposes), here nonzero, so R is invertible (The invertible matrix theorem). Finally Q^{T}Q = I_p because the columns are orthonormal, so Q^{T}A = Q^{T}QR = R. \square

When A is square, Q is square with Q^{T}Q = I, so Q^{-1} = Q^{T}, and

a triangular system solved from the bottom row up.

Worked examples

Boundaries

• Theorem 1 needs an independent list. On a dependent list a zero vector appears, and the next step would divide by 0 unless it is dropped (Example 6).
• The result depends on the order and on the starting basis; an orthogonal basis of a nonzero subspace is never unique. What the process fixes is \operatorname{span}\{\mathbf{v}_1, \dots, \mathbf{v}_k\} = X_k at every stage.
• Theorem 2 needs independent columns: that is what makes every r_{kk} positive and R invertible.
• With rounded computer arithmetic, the formulas as written can lose orthogonality on nearly dependent vectors; numerical software rearranges them.

Where this goes next

Every subspace of \mathbb{R}^n now has an orthogonal basis, so the projection formula of Orthogonal bases and projection onto a subspace always applies, and QQ^{T} is the projection matrix onto the column space of A. Running the process on a basis of W extended to \mathbb{R}^n also gives an orthogonal basis of W^{\perp} (Exercise 19). When A\mathbf{x} = \mathbf{b} has no exact solution, the factorization A = QR is one route to the best approximate one, taken up in Least squares: the best approximate solution of Ax = b.

Exercises

Day 1: running the process

1. Apply the process to \mathbf{x}_1 = (1, 2), \mathbf{x}_2 = (4, 3), and give an orthonormal basis of \mathbb{R}^2.
2. Apply the process to (1, 1, 1), (2, 1, 3), (4, 0, 2) to get an orthogonal basis of \mathbb{R}^3.
3. Turn the basis of Exercise 2 into an orthonormal basis.
4. Find an orthogonal basis of W = \operatorname{span}\{(2, 0, 1, 2), (3, 1, 1, 1)\} in \mathbb{R}^4, then the projection of \mathbf{y} = (1, 3, 2, 1) onto W.
5. The vectors (a, b, c) with a + b + c = 0 form a plane in \mathbb{R}^3 with basis (1, -1, 0), (1, 0, -1). Starting from that basis, find an orthonormal basis of the plane.
6. Apply the process to (0, 3, 4), (5, 0, 0), (5, 7, 1), and give the orthonormal basis.

Day 1: reasoning

7. Show that the process returns an orthogonal list of nonzero vectors unchanged.
8. Show that replacing \mathbf{v}_k by c\mathbf{v}_k, c \neq 0, before computing the later vectors changes none of them. Conclude that normalizing as you go gives the same \mathbf{q}’s as normalizing at the end.
9. Show that \lVert \mathbf{v}_k \rVert \leq \lVert \mathbf{x}_k \rVert, with equality exactly when \mathbf{x}_k is orthogonal to each of \mathbf{x}_1, \dots, \mathbf{x}_{k-1}.
10. For independent \mathbf{x}_1, \mathbf{x}_2 in \mathbb{R}^2, explain why the parallelogram with sides \mathbf{x}_1 and \mathbf{x}_2 has area \lVert \mathbf{x}_1 \rVert \lVert \mathbf{v}_2 \rVert, and check it against the determinant for the vectors of Exercise 1.

Day 2: QR, dependence and order

11. Find the QR factorization of \begin{bmatrix} 1 & 4 \\ 2 & 3 \end{bmatrix}.
12. Find the QR factorization of the matrix whose columns are (1, 1, 1), (2, 1, 3), (4, 0, 2).
13. With the factorization of Exercise 12, solve A\mathbf{x} = (4, 1, 1) by solving R\mathbf{x} = Q^{T}\mathbf{b}.
14. Apply the process to (1, 0, 1), (0, 1, 1), (1, 1, 2). What does the result say about the third vector, and what is the dimension of the span?
15. Apply the process to (4, 3), (1, 2), the vectors of Exercise 1 in the other order, and compare the two orthogonal bases.
16. Find the QR factorization of the 4 \times 2 matrix with columns (1, 1, 1, 1) and (1, 2, 3, 6).

Day 2: reasoning

17. For A = QR as in Theorem 2, show that R = Q^{T}A and A^{T}A = R^{T}R.
18. For a square A with independent columns, show that \lvert \det A \rvert = r_{11}r_{22}\cdots r_{nn}, and check it on the sensor matrix of Example 5.
19. Let \mathbf{x}_1, \dots, \mathbf{x}_p be a basis of W, extended to a basis \mathbf{x}_1, \dots, \mathbf{x}_n of \mathbb{R}^n. Show that the process gives \mathbf{v}_{p+1}, \dots, \mathbf{v}_n forming an orthogonal basis of W^{\perp}.
20. Show that if \mathbf{x}_1, \dots, \mathbf{x}_{k-1} are reordered among themselves, then \mathbf{v}_k, \dots, \mathbf{v}_p do not change.