MAT247H1/Unit 2
Unit 2 · Algebra II

Orthogonality & Gram–Schmidt

Bases in MAT240H1 were all equally good. With an inner product they stop being equal: orthonormal bases make every computation collapse to a dot product. Gram–Schmidt says you can always build one.

By the end you can
Why it matters & where it comes from
Why it exists

Finding coordinates in a general basis means solving a linear system. In an orthonormal basis the $i$-th coordinate is just $\langle v,e_i\rangle$ — no system, no inversion. That single simplification is why orthonormal bases are worth the effort of constructing.

In the real world

The QR factorization used by every least-squares solver is Gram–Schmidt in matrix form. Fourier series are coordinates in an orthonormal basis of a function space. JPEG compression is a change to an orthonormal cosine basis, keeping the large coordinates.

Story & open questions

Laplace used the procedure before either namesake; Gram published in 1883 and Schmidt in 1907. Naive Gram–Schmidt is numerically unstable — small rounding errors destroy orthogonality — so numerical linear algebra uses a modified version or Householder reflections instead.

Orthogonal and orthonormal sets

Definition

Vectors $u,v$ are orthogonal if $\langle u,v\rangle=0$, written $u\perp v$. A set is orthogonal if distinct members are pairwise orthogonal, and orthonormal if in addition every member has norm $1$. An orthonormal basis is a basis that is an orthonormal set.

Theorem Orthogonal implies independent

An orthogonal set of nonzero vectors is linearly independent.

Suppose $\sum_i c_iv_i=0$. Take the inner product with $v_j$: every term with $i\ne j$ dies by orthogonality, leaving $c_j\|v_j\|^2=0$. Since $v_j\ne0$, $c_j=0$. ∎

Theorem Coordinates are free

If $\{e_1,\dots,e_n\}$ is an orthonormal basis of $V$, then every $v\in V$ satisfies $v=\sum_{i=1}^n\langle v,e_i\rangle e_i$, and $\|v\|^2=\sum_i|\langle v,e_i\rangle|^2$ (Parseval).

Write $v=\sum c_ie_i$ and pair with $e_j$: orthonormality leaves $\langle v,e_j\rangle=c_j$. The norm identity follows by expanding $\langle v,v\rangle$.

Example The gain, concretely
In the basis $\{(1,1),(1,2)\}$ of $\mathbb{R}^2$, writing $(5,8)$ in coordinates means solving a $2\times2$ system.
In the orthonormal basis $e_1=\tfrac{1}{\sqrt2}(1,1)$, $e_2=\tfrac{1}{\sqrt2}(1,-1)$, the coordinates are $\langle(5,8),e_1\rangle=13/\sqrt2$ and $\langle(5,8),e_2\rangle=-3/\sqrt2$. Two dot products, no system.

Gram–Schmidt

Theorem Gram–Schmidt

Every finite-dimensional inner product space has an orthonormal basis. Given independent $v_1,\dots,v_n$, define

$w_1=v_1$, and for $k\ge2$, $w_k=v_k-\sum_{j=1}^{k-1}\dfrac{\langle v_k,w_j\rangle}{\|w_j\|^2}\,w_j$.
Then $\{w_1,\dots,w_n\}$ is orthogonal, each $w_k\ne0$, and $\operatorname{span}\{w_1,\dots,w_k\}=\operatorname{span}\{v_1,\dots,v_k\}$ for every $k$. Normalising, $e_k=w_k/\|w_k\|$, gives an orthonormal basis.
Proof Why $w_k\perp w_i$ for $i<k$
Induct on $k$. Assume $w_1,\dots,w_{k-1}$ are pairwise orthogonal. Pair $w_k$ with $w_i$ for some $i<k$:
$\langle w_k,w_i\rangle=\langle v_k,w_i\rangle -\sum_{j<k}\dfrac{\langle v_k,w_j\rangle}{\|w_j\|^2}\langle w_j,w_i\rangle$. By the inductive hypothesis only $j=i$ survives the sum, giving $\langle v_k,w_i\rangle-\langle v_k,w_i\rangle=0$.
And $w_k\ne0$: if it were $0$ then $v_k$ would lie in the span of $w_1,\dots,w_{k-1}$, which equals the span of $v_1,\dots,v_{k-1}$ — contradicting independence. ∎
Example Run it in $\mathbb{R}^3$

Take $v_1=(1,1,0)$, $v_2=(1,0,1)$.

$w_1=(1,1,0)$, $\|w_1\|^2=2$.
$\langle v_2,w_1\rangle=1$, so $w_2=(1,0,1)-\tfrac12(1,1,0)=(\tfrac12,-\tfrac12,1)$. Check: $\langle w_2,w_1\rangle=\tfrac12-\tfrac12+0=0$. ✓
Normalise: $e_1=\tfrac{1}{\sqrt2}(1,1,0)$ and $e_2=\sqrt{\tfrac23}(\tfrac12,-\tfrac12,1)$.
Read the formula as a subtraction. Each step takes $v_k$ and removes its shadow on everything built so far. The sum being subtracted is exactly the orthogonal projection of $v_k$ onto $\operatorname{span}\{w_1,\dots,w_{k-1}\}$ — which is the next section.

Orthogonal complements and projections

Definition

For a subset $S\subseteq V$, the orthogonal complement is $S^\perp=\{v\in V:\langle v,s\rangle=0\text{ for all }s\in S\}$. It is always a subspace, even when $S$ is not.

Theorem Orthogonal decomposition

If $W$ is a finite-dimensional subspace of $V$, then $V=W\oplus W^\perp$: every $v$ splits uniquely as $v=w+w'$ with $w\in W$ and $w'\in W^\perp$. The map $P_W(v)=w$ is the orthogonal projection onto $W$, and in an orthonormal basis $\{e_1,\dots,e_k\}$ of $W$,

$P_W(v)=\sum_{i=1}^k\langle v,e_i\rangle e_i$.

For existence, define $w$ by that formula and set $w'=v-w$; a direct check gives $\langle w',e_j\rangle=\langle v,e_j\rangle-\langle v,e_j\rangle=0$ for each $j$, so $w'\in W^\perp$. For uniqueness, a vector in $W\cap W^\perp$ is orthogonal to itself, hence $0$.

Theorem Best approximation

$P_W(v)$ is the unique closest point of $W$ to $v$: for every $w\in W$ with $w\ne P_W(v)$, $\|v-P_W(v)\|<\|v-w\|$.

Write $v-w=(v-P_W v)+(P_W v-w)$. The first term is in $W^\perp$ and the second in $W$, so they are orthogonal and Pythagoras gives $\|v-w\|^2=\|v-P_Wv\|^2+\|P_Wv-w\|^2$. The second term is positive unless $w=P_Wv$.

Example Dimensions add

In $\mathbb{R}^3$, let $W=\operatorname{span}\{(1,1,0)\}$. Then $W^\perp$ is the plane $x+y=0$, spanned by $(1,-1,0)$ and $(0,0,1)$. Indeed $\dim W+\dim W^\perp=1+2=3$, and $(W^\perp)^\perp=W$.

Common pitfalls

• Forgetting to normalise. The projection formula $\sum\langle v,e_i\rangle e_i$ needs an orthonormal basis; with merely orthogonal vectors divide by $\|w_i\|^2$.
• Applying Gram–Schmidt to a dependent list. Some $w_k$ becomes $0$ and the division blows up — the process assumes independence.
• Writing $W^\perp$ without saying which inner product. Change the inner product and the complement changes.
• Assuming $(W^\perp)^\perp=W$ in infinite dimensions. It needs $W$ closed; in finite dimensions it is automatic.

Practice

Original problems written for this guide in the style of Friedberg, Insel & Spence exercises. Write a full solution before opening the answer.

Practice 1 · Basic run

Apply Gram–Schmidt to $(1,1)$, $(2,0)$ in $\mathbb{R}^2$.

Answer
$w_1=(1,1)$; $\langle(2,0),w_1\rangle=2$ and $\|w_1\|^2=2$, so $w_2=(2,0)-(1,1)=(1,-1)$. Normalised: $\tfrac{1}{\sqrt2}(1,1)$ and $\tfrac{1}{\sqrt2}(1,-1)$.
Practice 2 · Coordinates

Using that orthonormal basis, write $(3,5)$ in coordinates.

Answer
$\langle(3,5),e_1\rangle =8/\sqrt2$ and $\langle(3,5),e_2\rangle=-2/\sqrt2$. Check: $\tfrac{8}{\sqrt2}\cdot\tfrac{1}{\sqrt2}(1,1) -\tfrac{2}{\sqrt2}\cdot\tfrac{1}{\sqrt2}(1,-1)=(4,4)-(1,-1)=(3,5)$. ✓
Practice 3 · Legendre

In $P_2(\mathbb{R})$ with $\langle f,g\rangle=\int_{-1}^1 fg$, apply Gram–Schmidt to $1,t,t^2$.

Solution
$w_1=1$ with $\|w_1\|^2=2$. Since $\int_{-1}^1 t\,dt=0$, $w_2=t$ already. For $t^2$: $\int_{-1}^1t^2\,dt=\tfrac23$ and $\int_{-1}^1t^3\,dt=0$, so $w_3=t^2-\tfrac{2/3}{2}\cdot1=t^2-\tfrac13$. These are the Legendre polynomials up to scaling.
Practice 4 · Projection

Find the orthogonal projection of $(1,2,3)$ onto $W=\operatorname{span}\{(1,0,0),(0,1,0)\}$.

Answer
The spanning set is already orthonormal, so $P_W(v)=1\cdot(1,0,0)+2\cdot(0,1,0)=(1,2,0)$. The residual $(0,0,3)$ is in $W^\perp$. ✓
Practice 5 · Complement

Find $W^\perp$ for $W=\operatorname{span}\{(1,2,1)\}$ in $\mathbb{R}^3$.

Solution
$W^\perp$ is the plane $x+2y+z=0$, a $2$-dimensional subspace with basis $\{(2,-1,0),(1,0,-1)\}$.
Practice 6 · Dimension count

Prove $\dim W+\dim W^\perp=\dim V$ for finite-dimensional $V$.

Solution
By the decomposition theorem $V=W\oplus W^\perp$, and dimensions add over a direct sum. Or: pick an orthonormal basis of $W$, extend to one of $V$, and the added vectors form a basis of $W^\perp$.
Practice 7 · Best approximation

Find the polynomial of degree $\le1$ closest to $t^2$ on $[-1,1]$ in the integral inner product.

Solution
Project $t^2$ onto $\operatorname{span}\{1,t\}$. From Practice 3, $\langle t^2,1\rangle=\tfrac23$ with $\|1\|^2=2$, and $\langle t^2,t\rangle=0$. So the projection is $\tfrac13$ — the constant $1/3$, and the error $t^2-\tfrac13$ is orthogonal to every linear polynomial.
Practice 8 · Pythagoras

Prove that if $u\perp v$ then $\|u+v\|^2=\|u\|^2+\|v\|^2$, and show the converse can fail over $\mathbb{C}$.

Solution
Expanding, $\|u+v\|^2=\|u\|^2+2\operatorname{Re}\langle u,v\rangle+\|v\|^2$, so the identity holds iff $\operatorname{Re}\langle u,v\rangle=0$. Over $\mathbb{R}$ that is orthogonality; over $\mathbb{C}$ take $u=(1,0)$, $v=(i,0)$, where $\langle u,v\rangle=-i$ is purely imaginary — Pythagoras holds but the vectors are not orthogonal.

Expanded topic checklist

Course coverage. This unit is part of the complete MAT247H1 topic map. It should cover the following items before you move on:

Textbook/source alignment

Use the current UofT MAT247H1 calendar topics as the coverage spine, and pair lecture notes with a Friedberg-Insel-Spence-style linear algebra text for extra reading. The exact assigned textbook should still be checked against the instructor syllabus.

Core theorem map

Orthogonal sets are independent; Gram–Schmidt manufactures them; an orthonormal basis of $W$ builds $P_W$; and $P_W$ solves the best approximation problem. Every later projection argument in the course reuses this chain.

Study routine. After every Gram–Schmidt run, verify orthogonality by computing the inner products. The arithmetic is error-prone and the check is two lines.

Deep practice extensions

Use these after the main practice set. They are designed to force definition-level reasoning, theorem selection, and mixed application rather than routine calculation only.

Extension 1 · Why normalise

What changes in the projection formula if the basis is orthogonal but not orthonormal?

Guide
Each term picks up a denominator: $P_W(v)=\sum_i\frac{\langle v,w_i\rangle}{\|w_i\|^2}w_i$. Normalising makes the denominators $1$.
Extension 2 · Failure mode

What happens if Gram–Schmidt is run on a dependent list?

Guide
The first $v_k$ lying in the span of its predecessors produces $w_k=0$, and normalising divides by zero. Discarding those zero vectors turns the process into a way of extracting a basis from a spanning set.
Extension 3 · Complement of a complement

Is $(W^\perp)^\perp=W$ always?

Guide
In finite dimensions, yes — both have the same dimension and $W\subseteq(W^\perp)^\perp$ is immediate. In infinite dimensions it needs $W$ to be closed.
Extension 4 · Least squares preview

Why does the best approximation theorem matter for fitting data?

Guide
Fitting is choosing the point of a subspace (the column space of the design matrix) closest to the data vector. The theorem says that point is the orthogonal projection, and the residual is orthogonal to every column — the normal equations.
← Unit 01Inner product spaces Unit 03 →The adjoint