Skip to content
VidiMaster it, module by module
Module 4/Gram-Schmidt & Orthogonal Maps

The Gram–Schmidt Process & QR Factorization

Orthonormal bases are wonderful to compute with — but where do they come from? The Gram–Schmidt process manufactures one from any basis, normalizing v1\mathbf{v}_1 and then, for each later vector, subtracting its projection onto the span of the vectors already processed before normalizing what remains (Theorem 8.15). The result depends on the order of the inputs (Remark 8.6), and when the vectors are the columns of a matrix the whole computation repackages into the QR factorization A=QRA=QR, with QQ orthonormal and RR upper triangular with positive diagonal (Theorem 8.16).

Before you start — give these a try

Attempting first primes your brain for the lesson — even if you miss. Nothing is graded or saved; it's just a warm-up.

In Example 8.7 the first unit vector is u1=12(1,1,1,1)T\mathbf{u}_1=\tfrac12(1,1,1,1)^{\mathsf{T}}. Compute the projection coefficient ⟨v2,u1⟩\langle\mathbf{v}_2,\mathbf{u}_1\rangle used to form v2⊥\mathbf{v}_2^{\perp}, where v2=(1,9,9,1)T\mathbf{v}_2=(1,9,9,1)^{\mathsf{T}}. (This equals the off-diagonal entry R12R_{12}.)

For v1=(1,1,1,1)T\mathbf{v}_1=(1,1,1,1)^{\mathsf{T}} and v2=(1,9,9,1)T\mathbf{v}_2=(1,9,9,1)^{\mathsf{T}}, compute the orthogonal projection proj⁡span⁡{v1}v2\operatorname{proj}_{\operatorname{span}\{\mathbf{v}_1\}}\mathbf{v}_2 — the part of v2\mathbf{v}_2 that Gram–Schmidt subtracts off. Enter it as a vector.

What you’ll be able to do

  • State and carry out Theorem 8.15: set u1=v1/∥v1∥\mathbf{u}_1=\mathbf{v}_1/\lVert\mathbf{v}_1\rVert, then for each later vector subtract its projection onto the span of the vectors already processed and normalize.
  • Compute the perpendicular component vk⊥=vk−∑j<k⟨vk,uj⟩uj\mathbf{v}_k^{\perp}=\mathbf{v}_k-\sum_{j<k}\langle\mathbf{v}_k,\mathbf{u}_j\rangle\mathbf{u}_j and the resulting unit vector uk=vk⊥/∥vk⊥∥\mathbf{u}_k=\mathbf{v}_k^{\perp}/\lVert\mathbf{v}_k^{\perp}\rVert.
  • Explain Remark 8.6: the orthonormal basis depends on the order of the input vectors, and each uk\mathbf{u}_k is determined only up to sign, so the basis is not unique.
  • State Theorem 8.16 and read the entries of RR off the Gram–Schmidt data: Rkk=∥vk⊥∥>0R_{kk}=\lVert\mathbf{v}_k^{\perp}\rVert>0 (with R11=∥v1∥R_{11}=\lVert\mathbf{v}_1\rVert) and Rjk=⟨vk,uj⟩R_{jk}=\langle\mathbf{v}_k,\mathbf{u}_j\rangle for j<kj<k.
  • Run a full Gram–Schmidt computation end to end (as in Example 8.7) and package the columns of AA as a QR factorization A=QRA=QR with positive diagonal.

In your course

· MATH2015 · Linear Algebra & Probability
§8.5 The Gram-Schmidt process
  • Theorem 8.15The Gram–Schmidt process
    Normalizing v1\mathbf{v}_1 and, for i≥2i\ge2, subtracting the projection of vi\mathbf{v}_i onto span⁡{v1,…,vi−1}\operatorname{span}\{\mathbf{v}_1,\dots,\mathbf{v}_{i-1}\} before normalizing, yields an orthonormal basis u1,…,un\mathbf{u}_1,\dots,\mathbf{u}_n of VV with span⁡{u1,…,uk}=span⁡{v1,…,vk}\operatorname{span}\{\mathbf{u}_1,\dots,\mathbf{u}_k\}=\operatorname{span}\{\mathbf{v}_1,\dots,\mathbf{v}_k\}.
  • Remark 8.6Order dependence of the process
    The orthonormal basis produced by Gram–Schmidt depends on the order of the original vectors; different orderings produce different orthonormal bases.
  • Theorem 8.16QR factorization
    A matrix AA with linearly independent columns factors as A=QRA=QR, where QQ has orthonormal columns (QTQ=IQ^{\mathsf{T}}Q=I) and RR is upper triangular with positive diagonal entries Rkk=∥vk⊥∥R_{kk}=\lVert\mathbf{v}_k^{\perp}\rVert; with this convention the factorization is unique.
  • Example 8.7Orthonormal basis of a subspace of R4\mathbb{R}^4
  • Example 8.8QR factorization of a matrix via Gram–Schmidt
OCR artefacts in the source were restored (e.g. ⊥\perp, ∥⋅∥\lVert\cdot\rVert, ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle) and every numerical value was recomputed. Because the Gram–Schmidt output basis is not unique (it is order- and sign-dependent), the auto-graded items target genuinely unique quantities: lengths ∥vk⊥∥\lVert\mathbf{v}_k^{\perp}\rVert, projections onto a fixed span, projection coefficients ⟨vk,uj⟩\langle\mathbf{v}_k,\mathbf{u}_j\rangle, and the positive diagonal of RR.
1

From a basis to an orthonormal basis

Having seen how convenient orthonormal bases are, a natural question is how to build one. Given a basis v1,…,vn\mathbf{v}_1,\dots,\mathbf{v}_n of a subspace V⊆RmV\subseteq\mathbb{R}^m (with the standard dot product), the Gram–Schmidt process produces an orthonormal basis u1,…,un\mathbf{u}_1,\dots,\mathbf{u}_n of the same space VV, one vector at a time. The first step is pure normalization: since v1≠0\mathbf{v}_1\neq\mathbf{0}, set u1=1∥v1∥ v1.\mathbf{u}_1=\frac{1}{\lVert\mathbf{v}_1\rVert}\,\mathbf{v}_1. Every later uk\mathbf{u}_k must be a unit vector orthogonal to all the ones before it, i.e. uk⊥span⁡{u1,…,uk−1}\mathbf{u}_k\perp\operatorname{span}\{\mathbf{u}_1,\dots,\mathbf{u}_{k-1}\}. The idea is to strip from vk\mathbf{v}_k the part that already lies in that span, leaving a genuinely new, perpendicular direction that we then scale to unit length.

2

The general step: subtract the projection

Suppose u1,…,uk−1\mathbf{u}_1,\dots,\mathbf{u}_{k-1} are already built. Resolve vk=vk∥+vk⊥\mathbf{v}_k=\mathbf{v}_k^{\parallel}+\mathbf{v}_k^{\perp} relative to the subspace span⁡{u1,…,uk−1}=span⁡{v1,…,vk−1}\operatorname{span}\{\mathbf{u}_1,\dots,\mathbf{u}_{k-1}\}=\operatorname{span}\{\mathbf{v}_1,\dots,\mathbf{v}_{k-1}\}. The parallel part vk∥\mathbf{v}_k^{\parallel} is the orthogonal projection, and subtracting it leaves the perpendicular part vk⊥=vk−proj⁡span⁡{u1,…,uk−1}vk=vk−⟨vk,u1⟩u1−⋯−⟨vk,uk−1⟩uk−1.\mathbf{v}_k^{\perp}=\mathbf{v}_k-\operatorname{proj}_{\operatorname{span}\{\mathbf{u}_1,\dots,\mathbf{u}_{k-1}\}}\mathbf{v}_k=\mathbf{v}_k-\langle\mathbf{v}_k,\mathbf{u}_1\rangle\mathbf{u}_1-\cdots-\langle\mathbf{v}_k,\mathbf{u}_{k-1}\rangle\mathbf{u}_{k-1}. Because the uj\mathbf{u}_j are orthonormal, each projection coefficient is simply the dot product ⟨vk,uj⟩\langle\mathbf{v}_k,\mathbf{u}_j\rangle, and the result vk⊥\mathbf{v}_k^{\perp} is orthogonal to every earlier uj\mathbf{u}_j. Normalizing gives the next basis vector uk=vk⊥/∥vk⊥∥\mathbf{u}_k=\mathbf{v}_k^{\perp}/\lVert\mathbf{v}_k^{\perp}\rVert (Theorem 8.15). The division is always legal: vk\mathbf{v}_k is linearly independent of v1,…,vk−1\mathbf{v}_1,\dots,\mathbf{v}_{k-1}, so vk⊥≠0\mathbf{v}_k^{\perp}\neq\mathbf{0}.

3

Order dependence and non-uniqueness

Gram–Schmidt is deterministic once the order of the inputs is fixed — but that order is a real choice. Remark 8.6: different orderings of v1,…,vn\mathbf{v}_1,\dots,\mathbf{v}_n generally produce different orthonormal bases of the same subspace. The reason is structural: u1\mathbf{u}_1 is always a unit vector along the first input, so whichever vector is fed in first steers everything after it. There is a second, smaller ambiguity: replacing any uk\mathbf{u}_k by −uk-\mathbf{u}_k leaves the set orthonormal, so even for a fixed order each output vector is pinned down only up to sign. This is why, when we want an answer with a single correct value, we test invariant quantities — a projection onto a fixed span, a length ∥vk⊥∥\lVert\mathbf{v}_k^{\perp}\rVert, or a coefficient ⟨vk,uj⟩\langle\mathbf{v}_k,\mathbf{u}_j\rangle (with u1=v1/∥v1∥\mathbf{u}_1=\mathbf{v}_1/\lVert\mathbf{v}_1\rVert) — rather than asking for the orthonormal basis itself.

4

The QR factorization

Gram–Schmidt is really a change of basis from V=(v1,…,vn)V=(\mathbf{v}_1,\dots,\mathbf{v}_n) to the orthonormal U=(u1,…,un)U=(\mathbf{u}_1,\dots,\mathbf{u}_n). Rearranging the step formula, each original vector is a combination of the new ones, vk=⟨vk,u1⟩u1+⋯+⟨vk,uk−1⟩uk−1+∥vk⊥∥ uk\mathbf{v}_k=\langle\mathbf{v}_k,\mathbf{u}_1\rangle\mathbf{u}_1+\cdots+\langle\mathbf{v}_k,\mathbf{u}_{k-1}\rangle\mathbf{u}_{k-1}+\lVert\mathbf{v}_k^{\perp}\rVert\,\mathbf{u}_k, which collects columnwise into [ v1  ⋯  vn ]⏟A=[ u1  ⋯  un ]⏟Q R.\underbrace{[\,\mathbf{v}_1\;\cdots\;\mathbf{v}_n\,]}_{A}=\underbrace{[\,\mathbf{u}_1\;\cdots\;\mathbf{u}_n\,]}_{Q}\,R. This is the QR factorization (Theorem 8.16). Here QQ has orthonormal columns, so QTQ=IQ^{\mathsf{T}}Q=I, and RR is upper triangular because vk\mathbf{v}_k is built from u1,…,uk\mathbf{u}_1,\dots,\mathbf{u}_k only — never a later u\mathbf{u}. Its entries come straight from the process: Rjk=⟨vk,uj⟩R_{jk}=\langle\mathbf{v}_k,\mathbf{u}_j\rangle for j<kj<k, and the diagonal Rkk=∥vk⊥∥>0R_{kk}=\lVert\mathbf{v}_k^{\perp}\rVert>0 (with R11=∥v1∥R_{11}=\lVert\mathbf{v}_1\rVert). Insisting on this positive diagonal makes QQ and RR unique.

Theorem 8.15 — The Gram–Schmidt process

Let v1,…,vn\mathbf{v}_1,\dots,\mathbf{v}_n be a basis of a subspace V⊆RmV\subseteq\mathbb{R}^m. For i=2,…,ni=2,\dots,n, resolve vi=vi∥+vi⊥\mathbf{v}_i=\mathbf{v}_i^{\parallel}+\mathbf{v}_i^{\perp} with respect to span⁡{v1,…,vi−1}\operatorname{span}\{\mathbf{v}_1,\dots,\mathbf{v}_{i-1}\}, where vi⊥=vi−⟨vi,u1⟩u1−⋯−⟨vi,ui−1⟩ui−1.\mathbf{v}_i^{\perp}=\mathbf{v}_i-\langle\mathbf{v}_i,\mathbf{u}_1\rangle\mathbf{u}_1-\cdots-\langle\mathbf{v}_i,\mathbf{u}_{i-1}\rangle\mathbf{u}_{i-1}. Then u1=1∥v1∥v1\mathbf{u}_1=\dfrac{1}{\lVert\mathbf{v}_1\rVert}\mathbf{v}_1 and ui=1∥vi⊥∥vi⊥\mathbf{u}_i=\dfrac{1}{\lVert\mathbf{v}_i^{\perp}\rVert}\mathbf{v}_i^{\perp} for i≥2i\ge2 form an orthonormal basis of VV, and span⁡{u1,…,uk}=span⁡{v1,…,vk}\operatorname{span}\{\mathbf{u}_1,\dots,\mathbf{u}_k\}=\operatorname{span}\{\mathbf{v}_1,\dots,\mathbf{v}_k\} for every kk.

Intuition. Build the basis greedily. The only way a fresh unit vector can be orthogonal to all the previous ones is to remove from vk\mathbf{v}_k everything living in their span — that removed piece is the projection vk∥\mathbf{v}_k^{\parallel}, and whatever remains is forced to be perpendicular. Normalizing turns it into a unit vector without changing its direction, so the running span is never disturbed.
Remark 8.6 — Order dependence

The orthonormal basis produced by the Gram–Schmidt process depends on the order of the vectors in the original basis: different orderings of v1,…,vn\mathbf{v}_1,\dots,\mathbf{v}_n generally produce different orthonormal bases of the same subspace VV.

Intuition. The process is front-loaded: u1\mathbf{u}_1 always points along the first input, and every later vector is constructed relative to the ones already chosen. Permute the inputs and u1\mathbf{u}_1 changes, which cascades through all the rest. On top of this, each uk\mathbf{u}_k could be replaced by −uk-\mathbf{u}_k, so an orthonormal basis is never unique — a reason to grade invariant quantities rather than the basis itself.
Theorem 8.16 — QR factorization

Let AA be an m×nm\times n matrix with linearly independent columns v1,…,vn\mathbf{v}_1,\dots,\mathbf{v}_n. Then A=QRA=QR, where QQ is the m×nm\times n matrix with orthonormal columns u1,…,un\mathbf{u}_1,\dots,\mathbf{u}_n produced by Gram–Schmidt (so QTQ=InQ^{\mathsf{T}}Q=I_n), and RR is the n×nn\times n upper-triangular matrix with Rkk=∥vk⊥∥>0R_{kk}=\lVert\mathbf{v}_k^{\perp}\rVert>0 (and R11=∥v1∥R_{11}=\lVert\mathbf{v}_1\rVert) on the diagonal and Rjk=⟨vk,uj⟩R_{jk}=\langle\mathbf{v}_k,\mathbf{u}_j\rangle above it. With this positive-diagonal convention the factorization is unique.

Intuition. Gram–Schmidt rewrites each vk\mathbf{v}_k using only u1,…,uk\mathbf{u}_1,\dots,\mathbf{u}_k, so the change-of-basis matrix RR from VV to UU is upper triangular. Its diagonal records how much genuinely new length each step contributes, ∥vk⊥∥\lVert\mathbf{v}_k^{\perp}\rVert, and this is positive exactly because the columns are independent (no vk\mathbf{v}_k collapses into the earlier span).

Worked examples

Example 1

Find an orthonormal basis u1,u2\mathbf{u}_1,\mathbf{u}_2 of the subspace V⊆R4V\subseteq\mathbb{R}^4 spanned by v1=(1,1,1,1)T\mathbf{v}_1=(1,1,1,1)^{\mathsf{T}} and v2=(1,9,9,1)T\mathbf{v}_2=(1,9,9,1)^{\mathsf{T}} (Example 8.7).

  1. 1

    Normalize v1\mathbf{v}_1. Its length is ∥v1∥=12+12+12+12=4=2\lVert\mathbf{v}_1\rVert=\sqrt{1^2+1^2+1^2+1^2}=\sqrt{4}=2, so u1=12(1,1,1,1)T=(12,12,12,12)T.\mathbf{u}_1=\frac{1}{2}(1,1,1,1)^{\mathsf{T}}=\left(\tfrac12,\tfrac12,\tfrac12,\tfrac12\right)^{\mathsf{T}}.

  2. 2

    Projection coefficient. Compute ⟨v2,u1⟩=12(1+9+9+1)=202=10.\langle\mathbf{v}_2,\mathbf{u}_1\rangle=\tfrac12(1+9+9+1)=\tfrac{20}{2}=10.

  3. 3

    Subtract the projection. The perpendicular component is v2⊥=v2−⟨v2,u1⟩u1=(1,9,9,1)T−10(12,12,12,12)T=(1,9,9,1)T−(5,5,5,5)T=(−4,4,4,−4)T.\mathbf{v}_2^{\perp}=\mathbf{v}_2-\langle\mathbf{v}_2,\mathbf{u}_1\rangle\mathbf{u}_1=(1,9,9,1)^{\mathsf{T}}-10\left(\tfrac12,\tfrac12,\tfrac12,\tfrac12\right)^{\mathsf{T}}=(1,9,9,1)^{\mathsf{T}}-(5,5,5,5)^{\mathsf{T}}=(-4,4,4,-4)^{\mathsf{T}}.

  4. 4

    Orthogonality check. ⟨v2⊥,u1⟩=12(−4+4+4−4)=0\langle\mathbf{v}_2^{\perp},\mathbf{u}_1\rangle=\tfrac12(-4+4+4-4)=0, as required.

  5. 5

    Normalize v2⊥\mathbf{v}_2^{\perp}. Its length is ∥v2⊥∥=(−4)2+42+42+(−4)2=64=8\lVert\mathbf{v}_2^{\perp}\rVert=\sqrt{(-4)^2+4^2+4^2+(-4)^2}=\sqrt{64}=8, so u2=18(−4,4,4,−4)T=(−12,12,12,−12)T.\mathbf{u}_2=\frac{1}{8}(-4,4,4,-4)^{\mathsf{T}}=\left(-\tfrac12,\tfrac12,\tfrac12,-\tfrac12\right)^{\mathsf{T}}.

Answer. U=(u1,u2)U=(\mathbf{u}_1,\mathbf{u}_2) with u1=(12,12,12,12)T\mathbf{u}_1=\left(\tfrac12,\tfrac12,\tfrac12,\tfrac12\right)^{\mathsf{T}} and u2=(−12,12,12,−12)T\mathbf{u}_2=\left(-\tfrac12,\tfrac12,\tfrac12,-\tfrac12\right)^{\mathsf{T}} is an orthonormal basis of VV. Choosing the opposite sign when normalizing v2⊥\mathbf{v}_2^{\perp}, or feeding the two vectors in the other order, gives an equally valid but different orthonormal basis (Remark 8.6).
Example 2

Apply the full Gram–Schmidt process to v1=(1,2,2)T\mathbf{v}_1=(1,2,2)^{\mathsf{T}}, v2=(3,3,0)T\mathbf{v}_2=(3,3,0)^{\mathsf{T}}, v3=(−1,4,1)T\mathbf{v}_3=(-1,4,1)^{\mathsf{T}} to obtain an orthonormal basis u1,u2,u3\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3 of R3\mathbb{R}^3.

Example 3

Using the Gram–Schmidt computation from Example 8.7, write the QR factorization of A=[11191911]A=\begin{bmatrix}1&1\\1&9\\1&9\\1&1\end{bmatrix} (whose columns are v1,v2\mathbf{v}_1,\mathbf{v}_2), with RR having a positive diagonal.