Evanalysis
9.3Estimated reading time: 8 min

9.3 Gram-Schmidt orthogonalization

Apply Gram-Schmidt to turn a basis into an orthogonal or orthonormal basis while preserving the same span.

Course contents

MATH1030: Linear algebra I

Rigorous linear algebra notes on systems, matrices, structure, and proof, with interaction used only where it clarifies the mathematics.

Language

ENEnglish繁Traditional Chinese简Simplified Chinese
All note collectionsSeries overview
123456789
Chapter 1Systems of equations1 sections
1.11.1 Equations and solution sets
Chapter 2Matrices and elimination4 sections
2.12.1 Matrix basics2.22.2 Augmented matrices and row operations2.32.3 Gaussian elimination and RREF2.42.4 Solution-set types
Chapter 3Matrix algebra2 sections
3.13.1 Matrix multiplication and identity matrices3.23.2 Transpose and special matrices
Chapter 4Solution structure1 sections
4.14.1 Homogeneous systems and null space
Chapter 5Invertibility1 sections
5.15.1 Invertible matrices
Chapter 6Vector spaces6 sections
6.16.1 Vector spaces6.26.2 Subspaces6.36.3 Linear combinations and span6.46.4 Linear dependence and independence6.56.5 Basis and dimension6.66.6 Column space, row space, and rank
Chapter 7Determinants3 sections
7.17.1 Determinants and cofactor expansion7.27.2 Row operations, products, and invertibility7.37.3 Transpose, column operations, and Cramer's rule
Chapter 8Eigenvalues and diagonalization3 sections
8.18.1 Eigenvalues, eigenvectors, and eigenspaces8.28.2 Diagonalization and similarity8.38.3 Characteristic polynomials and diagonalization tests
Chapter 9Inner products and orthogonality4 sections
9.19.1 Inner products, norms, and angles9.29.2 Orthogonal sets and orthonormal bases9.39.3 Gram-Schmidt orthogonalizationCurrent section9.49.4 Cauchy-Schwarz and triangle inequalities

An orthogonal basis is valuable, but most bases are not orthogonal when they are first given to you. Gram-Schmidt is the standard procedure that repairs that problem.

It starts from any linearly independent list and systematically removes the components that point in already-used directions. What remains is orthogonal, and the span is preserved at every step.

The projection idea behind Gram-Schmidt

Suppose v1,…,vkv_1,\dots,v_k are already orthogonal and w is any vector. If you want the part of w that is perpendicular to every viv_i, you subtract the components of w along those vectors:

w−⟨w,v1⟩∥v1∥2v1−⋯−⟨w,vk⟩∥vk∥2vk.w- \frac{\langle w,v_1\rangle}{\|v_1\|^2}v_1 -\cdots- \frac{\langle w,v_k\rangle}{\|v_k\|^2}v_k.

Theorem

Orthogonal remainder theorem

Let S={v1,…,vk}S=\{v_1,\dots,v_k\} be an orthogonal subset of Rm\mathbb{R}^m, and let w∈Rmw\in\mathbb{R}^m. Define

v=w−⟨w,v1⟩∥v1∥2v1−⋯−⟨w,vk⟩∥vk∥2vk.v= w- \frac{\langle w,v_1\rangle}{\|v_1\|^2}v_1 -\cdots- \frac{\langle w,v_k\rangle}{\|v_k\|^2}v_k.

Then v is perpendicular to each viv_i.

This theorem is the engine of the algorithm. It tells you exactly how to build a new vector orthogonal to all the old ones.

Gram-Schmidt process

Theorem

Gram-Schmidt orthogonalization process

Let {w1,…,wk}\{w_1,\dots,w_k\} be a linearly independent subset of Rm\mathbb{R}^m. Define

v1=w1,v_1=w_1,

and for ℓ=2,…,k\ell=2,\dots,k,

vℓ=wℓ−⟨wℓ,v1⟩∥v1∥2v1−⋯−⟨wℓ,vℓ−1⟩∥vℓ−1∥2vℓ−1.v_\ell= w_\ell -\frac{\langle w_\ell,v_1\rangle}{\|v_1\|^2}v_1 -\cdots- \frac{\langle w_\ell,v_{\ell-1}\rangle}{\|v_{\ell-1}\|^2}v_{\ell-1}.

Then:

  1. {v1,…,vk}\{v_1,\dots,v_k\} is orthogonal;
  2. for each ℓ\ell,
span⁡{w1,…,wℓ}=span⁡{v1,…,vℓ}.\operatorname{span}\{w_1,\dots,w_\ell\} = \operatorname{span}\{v_1,\dots,v_\ell\}.

In particular, the final orthogonal set spans the same subspace as the original linearly independent set.

The second conclusion matters as much as the first. Gram-Schmidt does not merely produce some orthogonal vectors. It preserves the exact subspace you started with.

How to read the algorithm

The first vector is unchanged:

v1=w1.v_1=w_1.

The second vector is the part of w2w_2 orthogonal to v1v_1.

The third vector is the part of w3w_3 orthogonal to both v1v_1 and v2v_2.

And so on. Each step removes everything already accounted for by the earlier orthogonal directions.

Worked example

A short Gram-Schmidt computation in R^3

Start with the linearly independent vectors

w1=[101],w2=[111],w3=[012].w_1= \begin{bmatrix} 1\\0\\1 \end{bmatrix}, \qquad w_2= \begin{bmatrix} 1\\1\\1 \end{bmatrix}, \qquad w_3= \begin{bmatrix} 0\\1\\2 \end{bmatrix}.

Set

v1=w1=[101].v_1=w_1= \begin{bmatrix} 1\\0\\1 \end{bmatrix}.

Now compute

⟨w2,v1⟩∥v1∥2=22=1,\frac{\langle w_2,v_1\rangle}{\|v_1\|^2} =\frac{2}{2}=1,

so

v2=w2−v1=[010].v_2=w_2-v_1= \begin{bmatrix} 0\\1\\0 \end{bmatrix}.

Next,

⟨w3,v1⟩∥v1∥2=22=1,⟨w3,v2⟩∥v2∥2=11=1.\frac{\langle w_3,v_1\rangle}{\|v_1\|^2} =\frac{2}{2}=1, \qquad \frac{\langle w_3,v_2\rangle}{\|v_2\|^2} =\frac{1}{1}=1.

Therefore

v3=w3−v1−v2=[−101].v_3=w_3-v_1-v_2= \begin{bmatrix} -1\\0\\1 \end{bmatrix}.

The resulting set

{[101],[010],[−101]}\left\{ \begin{bmatrix} 1\\0\\1 \end{bmatrix}, \begin{bmatrix} 0\\1\\0 \end{bmatrix}, \begin{bmatrix} -1\\0\\1 \end{bmatrix} \right\}

is orthogonal and spans the same subspace as the original list.

From orthogonal to orthonormal

Gram-Schmidt gives an orthogonal basis. To get an orthonormal basis, normalize each nonzero vector:

ui=vi∥vi∥.u_i=\frac{v_i}{\|v_i\|}.

Theorem

Every subspace has an orthonormal basis

Let VV be a subspace of Rm\mathbb{R}^m. Then VV has an orthogonal basis, and after normalization it also has an orthonormal basis.

So orthonormal bases are not rare or special accidents. Every finite-dimensional subspace of Rm\mathbb{R}^m admits one.

Worked example

Normalize the Gram-Schmidt output

Using the vectors from the previous example:

∥v1∥=2,∥v2∥=1,∥v3∥=2.\|v_1\|=\sqrt2,\qquad \|v_2\|=1,\qquad \|v_3\|=\sqrt2.

So an orthonormal basis is

u1=12[101],u2=[010],u3=12[−101].u_1=\frac{1}{\sqrt2} \begin{bmatrix} 1\\0\\1 \end{bmatrix}, \qquad u_2= \begin{bmatrix} 0\\1\\0 \end{bmatrix}, \qquad u_3=\frac{1}{\sqrt2} \begin{bmatrix} -1\\0\\1 \end{bmatrix}.

Common mistake

Common mistake

Do not subtract projections onto the original w-vectors

In the recursive formula, each new vector must be built using the already constructed orthogonal vectors v1,…,vℓ−1v_1,\dots,v_{\ell-1}, not the original w1,…,wℓ−1w_1,\dots,w_{\ell-1}. If you subtract components along the original non-orthogonal vectors, the output need not become orthogonal.

Quick check

Quick check

What is the first Gram-Schmidt vector v_1?

Look at the definition.

Solution

Answer

Quick check

What property does Gram-Schmidt preserve besides orthogonality?

Think about the span conclusion in the theorem.

Solution

Answer

Quick check

How do you turn an orthogonal basis into an orthonormal basis?

Use normalization.

Solution

Answer

Exercises

Quick check

Apply the first two steps of Gram-Schmidt to w1=(1,1,0)w_1=(1,1,0) and w2=(1,0,1)w_2=(1,0,1).

Compute v1=w1v_1=w_1, then subtract the component of w2w_2 along v1v_1.

Solution

Guided solution

Quick check

Why does Gram-Schmidt require the original list w1,…,wkw_1,\dots,w_k to be linearly independent?

Think about what could happen to one of the new vectors.

Solution

Guided solution

Quick check

Suppose Gram-Schmidt gives orthogonal vectors v1,v2v_1,v_2 with norms 3 and 4. What are the corresponding orthonormal vectors?

Normalize each one separately.

Solution

Guided solution

Related notes

Read 9.2 Orthogonal sets and orthonormal bases first, because Gram-Schmidt is built from the orthogonal coefficient formula.

The existence theorem here is one of the main practical tools for working with subspaces introduced earlier in 6.2 Subspaces and 6.5 Basis and dimension.

The equality cases in the next note, 9.4 Cauchy-Schwarz and triangle inequalities, explain why the projection steps here behave geometrically.

Section mastery checkpoint

Answer each question correctly to complete this section checkpoint. Correct progress: 0%.

Skills: gram-schmidt, span, orthogonal-basis

Besides producing orthogonal vectors, what does Gram-Schmidt preserve at each step?

Attempts used: 0

Attempts remaining: Unlimited attempts

Preview does not consume an attempt.

Submit records a graded attempt.

Prerequisites

9.2

9.2 Orthogonal sets and orthonormal bases

6.5

6.5 Basis and dimension

Key terms in this unit

More notes in this series

Previous section

9.2 Orthogonal sets and orthonormal bases

Next section

9.4 Cauchy-Schwarz and triangle inequalities