Gram-Schmidt Process

The Gram-Schmidt process turns any basis x₁, …, xₚ of a subspace into an orthogonal basis v₁, …, vₚ of the same subspace. Keep v₁ = x₁. From each next vector, subtract its projections onto the v’s you already have. Then divide each vᵢ by its length to get an orthonormal basis.

Before this lesson: Orthogonal Projections, Orthogonal Sets and Orthonormal Bases and Basis and Dimension

The idea behind Gram-Schmidt

Many formulas, like the orthogonal projection formula, only work with an orthogonal basis. Most bases you meet are not orthogonal. Gram-Schmidt fixes the basis one vector at a time without changing the subspace it spans.

Start with x₁ as it is. The second vector x₂ leans partly along x₁. Remove that part, which is the vector projection of x₂ onto x₁, and what is left points straight away from x₁. Each later vector gets the same treatment against every vector already built.

The Gram-Schmidt formulas

Let {x₁, …, xₚ} be a basis for a subspace W of ℝⁿ. Define

v_1 = x_1, \qquad v_2 = x_2 - \frac{x_2 \cdot v_1}{v_1 \cdot v_1}\,v_1, \qquad v_3 = x_3 - \frac{x_3 \cdot v_1}{v_1 \cdot v_1}\,v_1 - \frac{x_3 \cdot v_2}{v_2 \cdot v_2}\,v_2

and in general, subtract one projection for each vector already built:

v_k = x_k - \frac{x_k \cdot v_1}{v_1 \cdot v_1}\,v_1 - \frac{x_k \cdot v_2}{v_2 \cdot v_2}\,v_2 - \cdots - \frac{x_k \cdot v_{k-1}}{v_{k-1} \cdot v_{k-1}}\,v_{k-1}

• Then {v₁, …, vₚ} is an orthogonal basis for W, and span{v₁, …, vₖ} = span{x₁, …, xₖ} at every stage.
• Each vₖ is xₖ minus its projection onto span{v₁, …, vₖ₋₁}, so it is orthogonal to everything built before it.
• Orthonormal basis: divide each vector by its length, uᵢ = vᵢ/‖vᵢ‖.
• Scaling is allowed: multiplying a vᵢ by a nonzero number keeps it orthogonal to the others. Clear fractions before the next step to keep the arithmetic simple.
• If some vₖ comes out as the zero vector, then xₖ was a combination of the earlier vectors, so the set was not linearly independent. Drop xₖ and continue.

How to use the Gram-Schmidt process

1. Set v₁ = x₁.
2. For x₂, compute the weight (x₂ · v₁)/(v₁ · v₁) and subtract that many v₁’s from x₂ to get v₂.
3. For each later xₖ, compute one weight for every vector already built and subtract all of those pieces.
4. Check that every new vector has dot product 0 with each earlier one.
5. If you need an orthonormal basis, divide each vᵢ by ‖vᵢ‖.

Gram-Schmidt process examples

Example 1: Two vectors in ℝ²

Apply the Gram-Schmidt process to x_1 = \begin{bmatrix} 3 \\ 4 \end{bmatrix} and x_2 = \begin{bmatrix} 2 \\ 11 \end{bmatrix}. Then find an orthonormal basis.

v_1 = x_1 = \begin{bmatrix} 3 \\ 4 \end{bmatrix}

x_2 \cdot v_1 = 2(3) + 11(4) = 6 + 44 = 50

v_1 \cdot v_1 = 3^2 + 4^2 = 9 + 16 = 25

\frac{50}{25} = 2

v_2 = \begin{bmatrix} 2 \\ 11 \end{bmatrix} - 2\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 2 - 6 \\ 11 - 8 \end{bmatrix} = \begin{bmatrix} -4 \\ 3 \end{bmatrix}

v_1 \cdot v_2 = 3(-4) + 4(3) = -12 + 12 = 0

\|v_1\| = \sqrt{25} = 5,\quad \|v_2\| = \sqrt{16 + 9} = \sqrt{25} = 5

u_1 = \begin{bmatrix} 3/5 \\ 4/5 \end{bmatrix},\quad u_2 = \begin{bmatrix} -4/5 \\ 3/5 \end{bmatrix}

Answer: the orthogonal basis is {(3, 4), (−4, 3)}, and the orthonormal basis is {(3/5, 4/5), (−4/5, 3/5)}.

Example 2: Clearing fractions

Find an orthogonal basis for the plane W = span{x₁, x₂} in ℝ³, where x_1 = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} and x_2 = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}.

v_1 = x_1 = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}

\frac{x_2 \cdot v_1}{v_1 \cdot v_1} = \frac{1 + 0 + 0}{1 + 1 + 0} = \frac{1}{2}

v_2 = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} - \frac{1}{2}\begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 - \tfrac{1}{2} \\ 0 - \tfrac{1}{2} \\ 1 - 0 \end{bmatrix} = \begin{bmatrix} \tfrac{1}{2} \\ -\tfrac{1}{2} \\ 1 \end{bmatrix}

v_2' = 2v_2 = \begin{bmatrix} 1 \\ -1 \\ 2 \end{bmatrix}

v_1 \cdot v_2' = 1 - 1 + 0 = 0

Answer: {(1, 1, 0), (1, −1, 2)} is an orthogonal basis for W.

Example 3: Three vectors in ℝ³

Apply the Gram-Schmidt process to x_1 = \begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}, x_2 = \begin{bmatrix} 3 \\ 3 \\ 0 \end{bmatrix} and x_3 = \begin{bmatrix} 1 \\ 0 \\ 5 \end{bmatrix}, and find an orthonormal basis for ℝ³.

v_1 = x_1 = \begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix},\quad v_1 \cdot v_1 = 1 + 4 + 4 = 9

\frac{x_2 \cdot v_1}{v_1 \cdot v_1} = \frac{3 + 6 + 0}{9} = \frac{9}{9} = 1

v_2 = \begin{bmatrix} 3 - 1 \\ 3 - 2 \\ 0 - 2 \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\ -2 \end{bmatrix}

v_2 \cdot v_2 = 4 + 1 + 4 = 9

\frac{x_3 \cdot v_1}{v_1 \cdot v_1} = \frac{1 + 0 + 10}{9} = \frac{11}{9}

\frac{x_3 \cdot v_2}{v_2 \cdot v_2} = \frac{2 + 0 - 10}{9} = -\frac{8}{9}

v_3 = \begin{bmatrix} 1 \\ 0 \\ 5 \end{bmatrix} - \frac{11}{9}\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix} + \frac{8}{9}\begin{bmatrix} 2 \\ 1 \\ -2 \end{bmatrix}

= \begin{bmatrix} \tfrac{9}{9} - \tfrac{11}{9} + \tfrac{16}{9} \\ 0 - \tfrac{22}{9} + \tfrac{8}{9} \\ \tfrac{45}{9} - \tfrac{22}{9} - \tfrac{16}{9} \end{bmatrix} = \begin{bmatrix} \tfrac{14}{9} \\ -\tfrac{14}{9} \\ \tfrac{7}{9} \end{bmatrix}

v_3' = \frac{9}{7}v_3 = \begin{bmatrix} 2 \\ -2 \\ 1 \end{bmatrix}

v_1 \cdot v_3' = 2 - 4 + 2 = 0,\quad v_2 \cdot v_3' = 4 - 2 - 2 = 0

\|v_1\| = \|v_2\| = \|v_3'\| = \sqrt{9} = 3

Answer: the orthogonal basis is {(1, 2, 2), (2, 1, −2), (2, −2, 1)}. Dividing by 3 gives the orthonormal basis {(1/3, 2/3, 2/3), (2/3, 1/3, −2/3), (2/3, −2/3, 1/3)}.

Example 4: An orthonormal basis for a plane

Find an orthonormal basis for the plane W given by x − 2y + 3z = 0 in ℝ³.

x = 2y - 3z

\begin{bmatrix} x \\ y \\ z \end{bmatrix} = y\begin{bmatrix} 2 \\ 1 \\ 0 \end{bmatrix} + z\begin{bmatrix} -3 \\ 0 \\ 1 \end{bmatrix}

\frac{x_2 \cdot v_1}{v_1 \cdot v_1} = \frac{-6 + 0 + 0}{4 + 1 + 0} = -\frac{6}{5}

v_2 = \begin{bmatrix} -3 \\ 0 \\ 1 \end{bmatrix} + \frac{6}{5}\begin{bmatrix} 2 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} -\tfrac{15}{5} + \tfrac{12}{5} \\ \tfrac{6}{5} \\ 1 \end{bmatrix} = \begin{bmatrix} -\tfrac{3}{5} \\ \tfrac{6}{5} \\ 1 \end{bmatrix}

v_2' = 5v_2 = \begin{bmatrix} -3 \\ 6 \\ 5 \end{bmatrix}

v_1 \cdot v_2' = -6 + 6 + 0 = 0

-3 - 2(6) + 3(5) = -3 - 12 + 15 = 0

\|v_1\| = \sqrt{5},\quad \|v_2'\| = \sqrt{9 + 36 + 25} = \sqrt{70}

Answer: an orthonormal basis for W is {(2, 1, 0)/√5, (−3, 6, 5)/√70}.

Example 5: Separating level, trend and curve in data

A coach records a runner’s weekly mileage for four weeks. To split any four-week pattern into a steady level, a straight-line trend and a curve, she wants orthogonal versions of the patterns x_1 = (1, 1, 1, 1), x_2 = (1, 2, 3, 4) and x_3 = (1, 4, 9, 16) (constant, linear and squared week numbers). Apply the Gram-Schmidt process.

v_1 = x_1 = (1, 1, 1, 1),\quad v_1 \cdot v_1 = 4

\frac{x_2 \cdot v_1}{v_1 \cdot v_1} = \frac{1 + 2 + 3 + 4}{4} = \frac{10}{4} = \frac{5}{2}

v_2 = \left(1 - \tfrac{5}{2},\ 2 - \tfrac{5}{2},\ 3 - \tfrac{5}{2},\ 4 - \tfrac{5}{2}\right) = \left(-\tfrac{3}{2}, -\tfrac{1}{2}, \tfrac{1}{2}, \tfrac{3}{2}\right)

v_2' = 2v_2 = (-3, -1, 1, 3),\quad v_2' \cdot v_2' = 9 + 1 + 1 + 9 = 20

\frac{x_3 \cdot v_1}{v_1 \cdot v_1} = \frac{1 + 4 + 9 + 16}{4} = \frac{30}{4} = \frac{15}{2}

\frac{x_3 \cdot v_2'}{v_2' \cdot v_2'} = \frac{-3 - 4 + 9 + 48}{20} = \frac{50}{20} = \frac{5}{2}

v_3 = x_3 - \tfrac{15}{2}v_1 - \tfrac{5}{2}v_2'

= \left(1 - \tfrac{15}{2} + \tfrac{15}{2},\ 4 - \tfrac{15}{2} + \tfrac{5}{2},\ 9 - \tfrac{15}{2} - \tfrac{5}{2},\ 16 - \tfrac{15}{2} - \tfrac{15}{2}\right)

= (1, -1, -1, 1)

v_1 \cdot v_3 = 0,\quad v_2' \cdot v_3 = -3 + 1 - 1 + 3 = 0

Answer: the orthogonal patterns are level (1, 1, 1, 1), trend (−3, −1, 1, 3) and curve (1, −1, −1, 1). Because they are orthogonal, the coach can find how much of each pattern is in her data with one dot product each. The level and trend pieces give the same line as the least-squares regression line.

Common mistakes

Related ideas

Projections. Each step computes vₖ = xₖ − proj xₖ, the projection onto span{v₁, …, vₖ₋₁}. That is the y − ŷ piece from Orthogonal Projections, so every vₖ is the part of xₖ that the earlier vectors cannot reach.

QR factorization. If the x’s are the columns of a matrix A, the orthonormal u’s form the columns of Q, and the weights from Gram-Schmidt fill an upper triangular matrix R with A = QR. The next lesson, QR Factorization, shows how.

Order matters. Running Gram-Schmidt on the same vectors in a different order gives a different orthogonal basis for the same subspace. Every order works.

On a computer. Rounding errors can slowly ruin orthogonality in long runs. Software uses a reordered version, modified Gram-Schmidt, or other methods that give the same answer in exact arithmetic.

Practice problems

1. Apply the Gram-Schmidt process to x₁ = (1, 2) and x₂ = (4, 3).
2. Turn your answer to Problem 1 into an orthonormal basis.
3. Find an orthogonal basis for span{(1, 0, 1), (3, 2, 1)}.
4. Find an orthogonal basis for span{(2, 1, 2), (1, 1, 0)} with integer entries.
5. Apply the Gram-Schmidt process to x₁ = (1, 1, 0), x₂ = (1, 0, 1) and x₃ = (0, 1, 1).
6. Apply the Gram-Schmidt process to x₁ = (1, 1, 1), x₂ = (1, 2, 3) and x₃ = (2, 3, 4). What happens, and why?
7. Find an orthonormal basis for the plane x + y − z = 0.
8. Repeat Problem 1 with the order switched: x₁ = (4, 3) and x₂ = (1, 2).
9. Find an orthogonal basis for span{(1, 1, 1, 1), (0, 2, 2, 4)} in ℝ⁴.
10. Show that v₂ = x₂ − ((x₂ · v₁)/(v₁ · v₁))v₁ is always orthogonal to v₁.

v_1 = (1, 2),\quad \frac{x_2 \cdot v_1}{v_1 \cdot v_1} = \frac{4 + 6}{1 + 4} = \frac{10}{5} = 2

v_2 = (4 - 2, 3 - 4) = (2, -1)

v_1 \cdot v_2 = 2 - 2 = 0

\|v_1\| = \sqrt{1 + 4} = \sqrt{5},\quad \|v_2\| = \sqrt{4 + 1} = \sqrt{5}

u_1 = \left(\tfrac{1}{\sqrt{5}}, \tfrac{2}{\sqrt{5}}\right),\quad u_2 = \left(\tfrac{2}{\sqrt{5}}, -\tfrac{1}{\sqrt{5}}\right)

\frac{3 + 0 + 1}{1 + 0 + 1} = \frac{4}{2} = 2

v_2 = (3 - 2, 2 - 0, 1 - 2) = (1, 2, -1)

v_1 \cdot v_2 = 1 + 0 - 1 = 0

\frac{2 + 1 + 0}{4 + 1 + 4} = \frac{3}{9} = \frac{1}{3}

v_2 = \left(1 - \tfrac{2}{3},\ 1 - \tfrac{1}{3},\ 0 - \tfrac{2}{3}\right) = \left(\tfrac{1}{3}, \tfrac{2}{3}, -\tfrac{2}{3}\right)

v_2' = 3v_2 = (1, 2, -2)

v_1 \cdot v_2' = 2 + 2 - 4 = 0

v_2 = (1, 0, 1) - \tfrac{1}{2}(1, 1, 0) = \left(\tfrac{1}{2}, -\tfrac{1}{2}, 1\right) \to (1, -1, 2)

\frac{x_3 \cdot v_1}{v_1 \cdot v_1} = \frac{0 + 1 + 0}{2} = \frac{1}{2},\quad \frac{x_3 \cdot v_2'}{v_2' \cdot v_2'} = \frac{0 - 1 + 2}{6} = \frac{1}{6}

v_3 = \left(0 - \tfrac{1}{2} - \tfrac{1}{6},\ 1 - \tfrac{1}{2} + \tfrac{1}{6},\ 1 - 0 - \tfrac{2}{6}\right) = \left(-\tfrac{2}{3}, \tfrac{2}{3}, \tfrac{2}{3}\right)

v_3' = \tfrac{3}{2}v_3 = (-1, 1, 1)

v_1 \cdot v_3' = -1 + 1 + 0 = 0,\quad v_2' \cdot v_3' = -1 - 1 + 2 = 0

\frac{1 + 2 + 3}{3} = 2,\quad v_2 = (1 - 2, 2 - 2, 3 - 2) = (-1, 0, 1)

\frac{2 + 3 + 4}{3} = 3,\quad \frac{-2 + 0 + 4}{2} = 1

v_3 = (2 - 3 + 1,\ 3 - 3 - 0,\ 4 - 3 - 1) = (0, 0, 0)

z = x + y,\quad x_1 = (1, 0, 1),\ x_2 = (0, 1, 1)

\frac{0 + 0 + 1}{2} = \frac{1}{2},\quad v_2 = \left(-\tfrac{1}{2}, 1, \tfrac{1}{2}\right) \to (-1, 2, 1)

\|v_1\| = \sqrt{2},\quad \|v_2'\| = \sqrt{1 + 4 + 1} = \sqrt{6}

\frac{4 + 6}{16 + 9} = \frac{10}{25} = \frac{2}{5}

v_2 = \left(1 - \tfrac{8}{5},\ 2 - \tfrac{6}{5}\right) = \left(-\tfrac{3}{5}, \tfrac{4}{5}\right) \to (-3, 4)

\frac{0 + 2 + 2 + 4}{4} = \frac{8}{4} = 2

v_2 = (0 - 2, 2 - 2, 2 - 2, 4 - 2) = (-2, 0, 0, 2) \to (-1, 0, 0, 1)

v_2 \cdot v_1 = x_2 \cdot v_1 - \frac{x_2 \cdot v_1}{v_1 \cdot v_1}(v_1 \cdot v_1)

= x_2 \cdot v_1 - x_2 \cdot v_1 = 0

Gram-Schmidt process FAQ

What is the Gram-Schmidt process used for?

It builds an orthogonal or orthonormal basis for a subspace. With that basis you can find projections, coordinates and least-squares answers with simple dot products, and it gives the QR factorization of a matrix.

Does the order of the vectors matter?

The span does not change, but the vectors you get do. Any order gives a valid orthogonal basis, as Practice Problems 1 and 8 show.

What happens if the vectors are linearly dependent?

At some step you get the zero vector. That vector was a combination of the earlier ones, so you drop it and keep going.

What is the difference between an orthogonal and an orthonormal basis?

In an orthogonal basis every pair of vectors has dot product 0. An orthonormal basis also has every vector of length 1, which you get by dividing each vector by its length.

Summary

• v₁ = x₁, and each vₖ is xₖ minus its projections onto v₁, …, vₖ₋₁.
• Every weight is (xₖ · vᵢ)/(vᵢ · vᵢ), using the new v’s, not the original x’s.
• You may scale any vᵢ to clear fractions. Divide by lengths at the end for an orthonormal basis.
• Check each new vector with dot products. They should all be 0.
• A zero vector means the original set was dependent. Drop that vector.

Previous lesson: Orthogonal Projections

Next lesson: QR Factorization

Back to the Linear Algebra Index