The Gram–Schmidt Process and QR Factorization

Quick answer

The Gram–Schmidt process converts a basis x₁, …, x_p of a subspace into an orthogonal basis of the same subspace. Keep the first vector; from each later vector subtract its projections onto the vectors already built, leaving only the part orthogonal to them. Dividing each result by its length gives an orthonormal basis. Recording the process in matrix form writes A = QR, with orthonormal columns in Q and an upper triangular R, a factorization that computers use to solve least-squares problems.

What you'll learn

Apply the Gram–Schmidt process to a basis
Normalize an orthogonal basis to an orthonormal one
Explain why each step keeps the same span
Form the QR factorization of a matrix with independent columns

Building an orthogonal basis

Orthogonal bases turn coordinates and projections into dot products, but the bases that come out of row reduction are rarely orthogonal. The Gram–Schmidt process fixes that. Given a basis $\mathbf{x}_1, \ldots, \mathbf{x}_p$ of a subspace $W$ :

\begin{aligned} \mathbf{v}_1 &= \mathbf{x}_1\\ \mathbf{v}_2 &= \mathbf{x}_2 - \frac{\mathbf{x}_2 \cdot \mathbf{v}_1}{\mathbf{v}_1 \cdot \mathbf{v}_1}\,\mathbf{v}_1\\ \mathbf{v}_3 &= \mathbf{x}_3 - \frac{\mathbf{x}_3 \cdot \mathbf{v}_1}{\mathbf{v}_1 \cdot \mathbf{v}_1}\,\mathbf{v}_1 - \frac{\mathbf{x}_3 \cdot \mathbf{v}_2}{\mathbf{v}_2 \cdot \mathbf{v}_2}\,\mathbf{v}_2 \end{aligned}

and so on: each new vector minus its projections onto every vector already built. The result $\mathbf{v}_1, \ldots, \mathbf{v}_p$ is an orthogonal basis of $W$ . Dividing each by its length gives an orthonormal basis.

One Gram–Schmidt step in the plane

Why each step keeps the span and adds orthogonality

At step $k$ , the vectors $\mathbf{v}_1, \ldots, \mathbf{v}_{k-1}$ are already orthogonal and span the same subspace as $\mathbf{x}_1, \ldots, \mathbf{x}_{k-1}$ . The subtracted terms are exactly the projection of $\mathbf{x}_k$ onto that subspace. So $\mathbf{v}_k$ is the error of that projection, and the error is orthogonal to the subspace. It is not zero, since $\mathbf{x}_k$ is not in the span of the earlier vectors. And $\mathbf{v}_k$ differs from $\mathbf{x}_k$ by a combination of earlier vectors, so the span is unchanged. Each step strips away the part of the new vector that the earlier ones already cover, and what remains is orthogonal to all of them.

Worked examples

Example 2 — Three vectors in ℝ³

Apply Gram–Schmidt to $\mathbf{x}_1 = (1, 1, 0)$ , $\mathbf{x}_2 = (1, 0, 1)$ , $\mathbf{x}_3 = (0, 1, 1)$ .

$\mathbf{v}_1 = (1, 1, 0)$ . Next,

\mathbf{v}_2 = (1, 0, 1) - \tfrac{1}{2}(1, 1, 0) = \left(\tfrac{1}{2}, -\tfrac{1}{2}, 1\right)

which rescales to $(1, -1, 2)$ . Using that rescaled vector,

\mathbf{v}_3 = (0, 1, 1) - \tfrac{1}{2}(1, 1, 0) - \tfrac{1}{6}(1, -1, 2) = \left(-\tfrac{2}{3}, \tfrac{2}{3}, \tfrac{2}{3}\right)

which rescales to $(-1, 1, 1)$ . All three pairs of $(1, 1, 0)$ , $(1, -1, 2)$ , $(-1, 1, 1)$ have dot product $0$ .

Example 4 — The QR factorization

Factor $A = \begin{bmatrix} 3 & 2\\ 1 & 2 \end{bmatrix}$ as $QR$ .

The columns are $\mathbf{x}_1$ and $\mathbf{x}_2$ from Example 1. Normalizing $(3, 1)$ and $(-1, 3)$ , both of length $\sqrt{10}$ , gives the columns of $Q$ . Since $Q^{\mathsf{T}}Q = I$ , the other factor is $R = Q^{\mathsf{T}}A$ , where $Q^{\mathsf{T}}$ , the transpose, has the columns of $Q$ as its rows:

Q = \frac{1}{\sqrt{10}}\begin{bmatrix} 3 & -1\\ 1 & 3 \end{bmatrix} \qquad R = \frac{1}{\sqrt{10}}\begin{bmatrix} 10 & 8\\ 0 & 4 \end{bmatrix}

$R$ is upper triangular because $\mathbf{q}_2$ is orthogonal to $\mathbf{x}_1$ , which makes the lower-left entry $\mathbf{q}_2 \cdot \mathbf{x}_1 = 0$ .

Common mistakes

Practice problems

Apply Gram–Schmidt to $(1, 0)$ and $(1, 2)$ .

Answer

$(1, 0)$ and $(0, 2)$

Full solution

$\mathbf{v}_2 = (1, 2) - \tfrac{1}{1}(1, 0) = (0, 2)$ .
Apply Gram–Schmidt to $(1, 1)$ and $(1, 3)$ .

Answer

$(1, 1)$ and $(-1, 1)$

Full solution

The coefficient is $\tfrac{1 + 3}{2} = 2$ , so $\mathbf{v}_2 = (1, 3) - (2, 2) = (-1, 1)$ .
Normalize the answer to exercise 2.

Answer

$\tfrac{1}{\sqrt{2}}(1, 1)$ and $\tfrac{1}{\sqrt{2}}(-1, 1)$

Full solution

Both vectors have length $\sqrt{2}$ .
Apply Gram–Schmidt to $(1, 0, 1)$ and $(2, 1, 0)$ .

Answer

$(1, 0, 1)$ and $(1, 1, -1)$

Full solution

The coefficient is $\tfrac{2 + 0 + 0}{2} = 1$ , so $\mathbf{v}_2 = (2, 1, 0) - (1, 0, 1) = (1, 1, -1)$ . Check: $1 + 0 - 1 = 0$ .
What does Gram–Schmidt produce from $(1, 2)$ and $(2, 4)$ ?

Answer

$(1, 2)$ and the zero vector

Full solution

The second vector is twice the first, so its projection is itself and nothing is left. The span is only a line.
Why may $\left(\tfrac{1}{2}, -\tfrac{1}{2}, 1\right)$ be replaced by $(1, -1, 2)$ in the middle of the process?

Answer

Scaling keeps orthogonality and keeps the span.

Full solution

If $\mathbf{u} \cdot \mathbf{v} = 0$ then $\mathbf{u} \cdot (c\mathbf{v}) = 0$ , and $c\mathbf{v}$ spans the same line as $\mathbf{v}$ for $c \ne 0$ . Later projections onto that line come out the same.
Is $\left\{\tfrac{1}{\sqrt{2}}(1, 1, 0),\ \tfrac{1}{\sqrt{6}}(1, -1, 2),\ \tfrac{1}{\sqrt{3}}(-1, 1, 1)\right\}$ a basis of ℝ³?

Answer

Yes, an orthonormal one

Full solution

Three orthogonal nonzero vectors are independent, and three independent vectors in ℝ³ form a basis.
In Example 4, what is $Q^{\mathsf{T}}Q$ ?

Answer

The identity matrix

Full solution

Its entries are the dot products of the columns of $Q$ : $1$ on the diagonal because they are unit vectors, and $0$ off it because they are orthogonal.
Why is the factor $R$ in $A = QR$ upper triangular?

Answer

Each column of $Q$ is orthogonal to every earlier column of $A$ .

Full solution

Entry $(i, j)$ of $R = Q^{\mathsf{T}}A$ is $\mathbf{q}_i \cdot \mathbf{x}_j$ . Gram–Schmidt makes $\mathbf{q}_i$ orthogonal to $\mathbf{x}_1, \ldots, \mathbf{x}_{i-1}$ , so every entry below the diagonal is $0$ .
A student computes $\mathbf{v}_3$ by subtracting from $\mathbf{x}_3$ its projections onto $\mathbf{x}_1$ and $\mathbf{x}_2$ . What went wrong?

Hint

Is $\{\mathbf{x}_1, \mathbf{x}_2\}$ orthogonal?

Answer

The projections must be onto the orthogonal vectors $\mathbf{v}_1$ and $\mathbf{v}_2$ .

Full solution

The sum of projections onto separate vectors equals the projection onto their span only when those vectors are orthogonal. With $\mathbf{x}_1$ and $\mathbf{x}_2$ the pieces overlap, and the result is not orthogonal to the span.

Frequently asked questions

What does the Gram–Schmidt process do?

It takes any basis of a subspace and produces an orthogonal basis of the same subspace, one vector at a time.

What is the formula for each step?

v_k = x_k minus the projections of x_k onto v₁, …, v_(k−1). Each projection is (x_k · v_j)/(v_j · v_j) v_j.

Can I rescale the vectors along the way?

Yes. Multiplying a vector by a nonzero number keeps it orthogonal to the others and keeps the span, so clearing fractions is safe.

What happens if the starting vectors are dependent?

At the step where a vector lies in the span of the earlier ones, subtracting its projections leaves the zero vector. That vector adds nothing and is dropped.

What is the QR factorization?

A = QR, where Q has orthonormal columns from Gram–Schmidt and R = QᵀA is upper triangular. It exists whenever A has independent columns.

What to learn next

Least Squares and the Line of Best FitWhen Ax = b has no solution, find the x that comes closest: solve the normal equations AᵀAx = Aᵀb, and use them to fit a line to data.

For teachersPrint problems onlyTick to print a blank worksheet; leave it clear to print the lesson with the full answer key.