Math Core

Orthogonal bases make coordinates and projections easy, but the bases you meet in practice (columns of a matrix, solutions of a system) are rarely orthogonal. The Gram-Schmidt process fixes that: it turns any basis of a subspace into an orthogonal basis of the same subspace, one vector at a time, using nothing but projections.

The idea with two vectors

Suppose $W = \operatorname{Span}\{\mathbf{x}_1, \mathbf{x}_2\}$ with $\mathbf{x}_1, \mathbf{x}_2$ independent but not orthogonal. Keep the first vector: $\mathbf{v}_1 = \mathbf{x}_1$ . From $\mathbf{x}_2$ , subtract its projection onto $\mathbf{v}_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.

This is the component of $\mathbf{x}_2$ orthogonal to $\mathbf{v}_1$ , so $\mathbf{v}_1 \cdot \mathbf{v}_2 = 0$ . It is still in $W$ , being a combination of $\mathbf{x}_2$ and $\mathbf{x}_1$ . And it isn't $\mathbf{0}$ , because $\mathbf{x}_2$ is not a multiple of $\mathbf{x}_1$ . So $\{\mathbf{v}_1, \mathbf{v}_2\}$ is an orthogonal basis for $W$ .

Worked example: Two vectors in R³

Find an orthogonal basis for $W = \operatorname{Span}\{\mathbf{x}_1, \mathbf{x}_2\}$ , where $\mathbf{x}_1 = (1, 2, 2)$ and $\mathbf{x}_2 = (4, 5, 2)$ .

Let $\mathbf{v}_1 = \mathbf{x}_1$ . Then $\mathbf{x}_2 \cdot \mathbf{v}_1 = 4 + 10 + 4 = 18$ and $\mathbf{v}_1 \cdot \mathbf{v}_1 = 9$ , so

\mathbf{v}_2 = (4, 5, 2) - \frac{18}{9}(1, 2, 2) = (4, 5, 2) - (2, 4, 4) = (2, 1, -2).

Check: $\mathbf{v}_1 \cdot \mathbf{v}_2 = 2 + 2 - 4 = 0$ . So $\{(1, 2, 2), (2, 1, -2)\}$ is an orthogonal basis for $W$ .

The general process

For more vectors, keep going: each new $\mathbf{x}_k$ has its projection onto the span of all the earlier $\mathbf{v}$ 's removed. Because those earlier $\mathbf{v}$ 's are already orthogonal, that projection is just a sum of one-line projections.

The Gram-Schmidt process

Given a basis $\{\mathbf{x}_1, \ldots, \mathbf{x}_p\}$ of a subspace $W$ of $\mathbb{R}^n$ , define

\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 \\ &\ \ \vdots \\ \mathbf{v}_p &= \mathbf{x}_p - \frac{\mathbf{x}_p \cdot \mathbf{v}_1}{\mathbf{v}_1 \cdot \mathbf{v}_1}\mathbf{v}_1 - \cdots - \frac{\mathbf{x}_p \cdot \mathbf{v}_{p-1}}{\mathbf{v}_{p-1} \cdot \mathbf{v}_{p-1}}\mathbf{v}_{p-1}. \end{aligned}

Then $\{\mathbf{v}_1, \ldots, \mathbf{v}_p\}$ is an orthogonal basis for $W$ . Moreover, for each $k$ , $\operatorname{Span}\{\mathbf{v}_1, \ldots, \mathbf{v}_k\} = \operatorname{Span}\{\mathbf{x}_1, \ldots, \mathbf{x}_k\}$ .

In the language of the last lesson, $\mathbf{v}_k = \mathbf{x}_k - \operatorname{proj}_{W_{k-1}}\mathbf{x}_k$ , where $W_{k-1} = \operatorname{Span}\{\mathbf{x}_1, \ldots, \mathbf{x}_{k-1}\}$ . By the orthogonal decomposition theorem, $\mathbf{v}_k$ is orthogonal to $W_{k-1}$ , hence to all earlier $\mathbf{v}$ 's.

Tip

You may rescale any $\mathbf{v}_k$ before moving on, for example to clear fractions. Scaling doesn't change orthogonality or the span, and it keeps later arithmetic clean. Just be sure to use the rescaled vector consistently in every later step.

Worked example: Three vectors in R⁴

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

Step 1. $\mathbf{v}_1 = (1, 0, 1, 0)$ , with $\mathbf{v}_1 \cdot \mathbf{v}_1 = 2$ .

Step 2. $\mathbf{x}_2 \cdot \mathbf{v}_1 = 2$ , so

\mathbf{v}_2 = (1, 1, 1, 1) - \frac{2}{2}(1, 0, 1, 0) = (0, 1, 0, 1), \qquad \mathbf{v}_2 \cdot \mathbf{v}_2 = 2.

Step 3. $\mathbf{x}_3 \cdot \mathbf{v}_1 = 0 + 2 = 2$ and $\mathbf{x}_3 \cdot \mathbf{v}_2 = 1 + 1 = 2$ , so

\mathbf{v}_3 = (0, 1, 2, 1) - \frac{2}{2}(1, 0, 1, 0) - \frac{2}{2}(0, 1, 0, 1) = (-1, 0, 1, 0).

Check all pairs: $\mathbf{v}_1 \cdot \mathbf{v}_2 = 0$ , $\mathbf{v}_1 \cdot \mathbf{v}_3 = -1 + 1 = 0$ , $\mathbf{v}_2 \cdot \mathbf{v}_3 = 0$ . The orthogonal basis is $\{(1, 0, 1, 0), (0, 1, 0, 1), (-1, 0, 1, 0)\}$ .

Common mistake

In step $k$ , project $\mathbf{x}_k$ onto the new vectors $\mathbf{v}_1, \ldots, \mathbf{v}_{k-1}$ , not onto the original $\mathbf{x}_1, \ldots, \mathbf{x}_{k-1}$ . The one-line projections only add up correctly because the $\mathbf{v}$ 's are orthogonal; the $\mathbf{x}$ 's are not.

Orthonormal bases

To get an orthonormal basis, run Gram-Schmidt and then normalize each $\mathbf{v}_k$ . Normalize at the end, not along the way: dividing by square roots mid-process fills every later step with radicals.

For the first example, $\|\mathbf{v}_1\| = \|\mathbf{v}_2\| = 3$ , so an orthonormal basis for $W$ is

\mathbf{q}_1 = \tfrac{1}{3}(1, 2, 2), \qquad \mathbf{q}_2 = \tfrac{1}{3}(2, 1, -2).

If the input vectors are dependent, Gram-Schmidt reveals it: some $\mathbf{v}_k$ comes out as $\mathbf{0}$ , meaning $\mathbf{x}_k$ was already in the span of the earlier vectors. Drop it and continue.

QR factorization

Gram-Schmidt, written in matrix form, is a factorization.

QR factorization

If $A$ is an $m \times n$ matrix with linearly independent columns, then $A = QR$ , where $Q$ is $m \times n$ with orthonormal columns forming a basis of $\operatorname{Col} A$ , and $R$ is an $n \times n$ upper triangular invertible matrix with positive diagonal entries.

To build it, apply Gram-Schmidt to the columns of $A$ and normalize to get the columns of $Q$ . Then, since $Q^TQ = I$ , multiplying $A = QR$ on the left by $Q^T$ gives

R = Q^TA.

$R$ is upper triangular because, by the span property, column $k$ of $A$ is a combination of $\mathbf{q}_1, \ldots, \mathbf{q}_k$ only, so its inner products with $\mathbf{q}_{k+1}, \mathbf{q}_{k+2}, \ldots$ are all $0$ .

Worked example: A QR factorization

Find a QR factorization of $A = \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 2 & 2 \end{bmatrix}$ .

The columns are $\mathbf{x}_1$ and $\mathbf{x}_2$ from the first example, so

Q = \frac{1}{3}\begin{bmatrix} 1 & 2 \\ 2 & 1 \\ 2 & -2 \end{bmatrix}.

Then

R = Q^TA = \frac{1}{3}\begin{bmatrix} 1 & 2 & 2 \\ 2 & 1 & -2 \end{bmatrix}\begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 2 & 2 \end{bmatrix} = \frac{1}{3}\begin{bmatrix} 9 & 18 \\ 0 & 9 \end{bmatrix} = \begin{bmatrix} 3 & 6 \\ 0 & 3 \end{bmatrix}.

Check: column 2 of $QR$ is $6\mathbf{q}_1 + 3\mathbf{q}_2 = (2, 4, 4) + (2, 1, -2) = (4, 5, 2)$ , which is column 2 of $A$ .

The diagonal entries of $R$ have a meaning: $r_{kk} = \|\mathbf{v}_k\|$ , the length of the new direction found at step $k$ . Computers use QR factorizations to solve least-squares problems stably, as you'll see in the next lesson.

Practice

Practice 1

Apply Gram-Schmidt to $\mathbf{x}_1 = (2, 1, 2)$ and $\mathbf{x}_2 = (4, -1, 1)$ . Find $\mathbf{v}_2$ .

Enter a point like (2, -3)

Practice 2

Apply Gram-Schmidt to $\mathbf{x}_1 = (1, -1, 1)$ and $\mathbf{x}_2 = (4, 0, 2)$ , then normalize. Find the second orthonormal vector $\mathbf{q}_2$ . Give exact values (you may type sqrt).

Enter a point like (2, -3)

Practice 3

Apply Gram-Schmidt to $\mathbf{x}_1 = (3, 4, 0)$ and $\mathbf{x}_2 = (1, 1, 1)$ . Rescale $\mathbf{v}_2$ to clear fractions: enter the multiple of $\mathbf{v}_2$ whose third entry is $25$ .

Enter a point like (2, -3)

Practice 4

Apply Gram-Schmidt to $\mathbf{x}_1 = (1, 1, 1, 1)$ , $\mathbf{x}_2 = (2, 0, 2, 0)$ , $\mathbf{x}_3 = (4, 2, 2, 0)$ . Find $\mathbf{v}_3$ .

Enter a point like (2, -3)

Practice 5

Let $A = \begin{bmatrix} 1 & 1 \\ 2 & 5 \\ 2 & -1 \end{bmatrix}$ and $A = QR$ be its QR factorization. Find the entry $r_{22}$ of $R$ as an exact value.

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 6

You apply Gram-Schmidt to $\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3$ and find $\mathbf{v}_3 = \mathbf{0}$ . What does that tell you?

Practice 7

$A$ is a $5 \times 3$ matrix with linearly independent columns and $A = QR$ . Which statement is true?