Gram-Schmidt Process — Gram–Schmidt Orthonormalization - Linear Algebra

SECTION 1

Historical Context & Motivation

Imagine you are building a coordinate system from scratch. You want your axes to be perfectly perpendicular — like the x-axis and y-axis on graph paper — so that measuring along one direction doesn't mix up information from another. The Gram–Schmidt process is a recipe that takes any collection of vectors (arrows with direction and length) and straightens them into a set that is both perpendicular and of unit length. This procedure is one of the most useful tools in all of linear algebra.

The idea grew over more than a century. Mathematicians in the 1800s realized that working with perpendicular directions makes calculations much simpler — projections become easy, distances stay clean, and errors in one direction don't leak into another. Two mathematicians in particular, Jørgen Pedersen Gram and Erhard Schmidt, formalized the method that now carries their names.

1836 • Early Orthogonalization Ideas

Pierre-Simon Laplace and others used orthogonal (perpendicular) functions in studying planetary motion. The core idea of removing overlap between directions appeared in applied mathematics long before it was given a formal name.

1883 • Gram's Contribution

Danish mathematician Jørgen Pedersen Gram published work on series expansions that contained the essential projection-and-subtraction idea. His paper focused on approximation problems in probability and statistics.

1907 • Schmidt Formalizes the Process

German mathematician Erhard Schmidt extended the procedure to infinite-dimensional spaces (function spaces). His rigorous treatment made the algorithm widely known and gave it its modern form.

1960s–today • Computers and Numerical Stability

With the rise of computers, researchers developed improved versions of the process (like the 'modified Gram–Schmidt') that handle rounding errors better. Today the algorithm powers everything from search engines to 3-D graphics.

The central question the Gram–Schmidt process answers is: Given a set of vectors that may point in messy, overlapping directions, how can we build a new set that spans the same space but uses perfectly perpendicular unit vectors? Answering that question opens the door to cleaner calculations in physics, data science, and engineering.

SECTION 2

Core Principles & Definitions

Before diving into the algorithm, you need a handful of key ideas. Think of these as the vocabulary words that make the recipe understandable.

Orthogonal Vectors

Two vectors are orthogonal (perpendicular) when their dot product equals zero. They share no component along each other's direction — like the x-axis and y-axis.

Dot Product (Inner Product)

The dot product of two vectors measures how much they point in the same direction. For vectors u = (u₁, u₂) and v = (v₁, v₂), it equals u₁v₁ + u₂v₂.

Projection

The projection of vector v onto vector u is the shadow that v casts along the direction of u. It tells you 'how much of v goes in the u direction.'

Unit Vector (Normalization)

A unit vector has length 1. You normalize a vector by dividing it by its own length (magnitude). This keeps its direction the same but scales it to size 1.

Orthonormal Set

An orthonormal set is a collection of vectors that are all mutually perpendicular AND each has length 1. This is the goal of the Gram–Schmidt process.

✦

KEY TAKEAWAY

Think of the Gram–Schmidt process like organizing a messy room. You start with several objects leaning against each other (your original vectors). Step by step, you stand each one straight up on its own, making sure no two lean on each other (orthogonal). Then you cut or stretch each one so they're all the same height (normalized). The result is a perfectly tidy set — an orthonormal basis.

SECTION 3

Visual Explanation

The diagram below shows the heart of the Gram–Schmidt idea in two dimensions. We start with two vectors, v₁ and v₂, that are not perpendicular. The process keeps v₁ as-is (calling it u₁), then removes the part of v₂ that points along u₁. What remains — shown in green — is perpendicular to u₁. Finally, both vectors are scaled to unit length.

The blue arrow is the first vector v₁, which we keep as u₁. The violet arrow is v₂. The dashed amber arrow shows the projection of v₂ onto u₁ — the part of v₂ that goes in the u₁ direction. Subtracting that projection from v₂ leaves the green arrow u₂, which is perpendicular to u₁. The small square at the base of u₂ confirms the right angle.

Notice the key move: we subtract the shadow (projection) from the original vector. What is left over has zero component in the direction of u₁, which is exactly the definition of perpendicular. If we had a third vector v₃, we would subtract its projections onto both u₁ and u₂ before moving on. The pattern continues for any number of vectors.

SECTION 4

Mathematical Framework

Let's write down the formulas that drive each step. Suppose we start with vectors v₁, v₂, …, vₙ and want to produce orthonormal vectors e₁, e₂, …, eₙ.

Step A — Build Orthogonal Vectors

FIRST ORTHOGONAL VECTOR

u₁ = v₁

The first vector is accepted without change. It becomes the reference direction.

PROJECTION FORMULA

proj_u(v) = ( (v · u) / (u · u) ) × u

v · u is the dot product of v and u. This formula finds the component of v in the direction of u. The fraction (v · u) / (u · u) is a single number (a scalar).

SECOND ORTHOGONAL VECTOR

u₂ = v₂ − proj_{u₁}(v₂)

Subtract from v₂ everything that points along u₁. The result u₂ is perpendicular to u₁.

k-TH ORTHOGONAL VECTOR

uₖ = vₖ − proj_{u₁}(vₖ) − proj_{u₂}(vₖ) − … − proj_{u_{k−1}}(vₖ)

For each new vector vₖ, subtract its projections onto every previously computed u. This guarantees uₖ is perpendicular to all earlier directions.

Step B — Normalize to Unit Length

NORMALIZATION

eₖ = uₖ / ‖uₖ‖

‖uₖ‖ is the magnitude (length) of uₖ, calculated as √(uₖ · uₖ). Dividing by this length scales the vector to length 1 without changing its direction.

💡

Why Two Steps?

You could normalize after every subtraction, but it is clearer to think of the process in two stages: first make everything perpendicular (orthogonal), then shrink or stretch each vector to length 1 (normalize). Many textbooks combine the two stages, but the logic is the same.

SECTION 5

Detailed Step-by-Step Flowchart

The flowchart below summarizes the entire Gram–Schmidt algorithm. Follow the arrows from top to bottom. At each stage a new vector joins the orthonormal set.

Follow the flowchart from top to bottom. The key decision diamond checks whether uₖ is the zero vector. If it is, the original vector vₖ was a linear combination of the others (linearly dependent) and is skipped. Otherwise the vector is normalized and added to the orthonormal set. The loop arrow on the right sends us back for each remaining vector.

The decision diamond in the middle is important. If after subtracting all projections the remaining vector is the zero vector (length 0), that means the original vector was already a combination of the ones before it. In that case, you simply skip it — you don't add a zero vector to your set. This situation arises when the original vectors are linearly dependent.

SECTION 6

Worked Example

Let's apply the Gram–Schmidt process to two vectors in ℝ² (two-dimensional space). We will find an orthonormal set that spans the same space.

ℹ

Given

v₁ = (3, 1) and v₂ = (2, 2). Find an orthonormal basis using the Gram–Schmidt process.

Gram–Schmidt on v₁ = (3, 1) and v₂ = (2, 2)

1
Step 1 — Set u₁ equal to v₁

We keep the first vector as is: u₁ = v₁ = (3, 1).

u₁ = (3, 1)
2
Step 2 — Compute the projection of v₂ onto u₁

First find the dot products. v₂ · u₁ = 2 × 3 + 2 × 1 = 6 + 2 = 8. Then u₁ · u₁ = 3 × 3 + 1 × 1 = 9 + 1 = 10. So the projection scalar is 8 / 10 = 4/5. Therefore proj_{u₁}(v₂) = (4/5) × (3, 1) = (12/5, 4/5).

proj = (12/5, 4/5) = (2.4, 0.8)
3
Step 3 — Subtract to get u₂

u₂ = v₂ − proj_{u₁}(v₂) = (2, 2) − (12/5, 4/5) = (2 − 2.4, 2 − 0.8) = (−0.4, 1.2). In fractions: (−2/5, 6/5).

u₂ = (−2/5, 6/5)
4
Step 4 — Verify orthogonality

Check: u₁ · u₂ = 3 × (−2/5) + 1 × (6/5) = −6/5 + 6/5 = 0. The dot product is zero, so they are perpendicular. ✓

u₁ · u₂ = 0 ✓
5
Step 5 — Normalize u₁

‖u₁‖ = √(3² + 1²) = √(10). So e₁ = u₁ / √10 = (3/√10, 1/√10). In decimal form: approximately (0.949, 0.316).

e₁ = (3/√10, 1/√10)
6
Step 6 — Normalize u₂

‖u₂‖ = √((−2/5)² + (6/5)²) = √(4/25 + 36/25) = √(40/25) = √(40)/5 = 2√10/5. So e₂ = u₂ / (2√10/5) = (−2/5) / (2√10/5), (6/5) / (2√10/5)) = (−1/√10, 3/√10). In decimal form: approximately (−0.316, 0.949).

e₂ = (−1/√10, 3/√10)
7
Step 7 — Final check

Verify: e₁ · e₂ = (3/√10)(−1/√10) + (1/√10)(3/√10) = −3/10 + 3/10 = 0. And ‖e₁‖ = √(9/10 + 1/10) = 1. ‖e₂‖ = √(1/10 + 9/10) = 1. Both unit length, perpendicular — we have an orthonormal basis.

Orthonormal basis: { (3/√10, 1/√10), (−1/√10, 3/√10) }

SECTION 7

Strengths, Limitations & Comparisons

The Gram–Schmidt process is powerful, but like any tool it has both strengths and weaknesses. Understanding these helps you know when to use it and when to look for alternatives.

Feature	Strength	Limitation
Simplicity	Easy to understand and implement step by step. Great for learning.	For very large sets of vectors, the number of projections grows quickly.
Numerical Stability	The modified version improves accuracy on computers.	The 'classical' version can accumulate rounding errors, making results slightly non-orthogonal.
Generality	Works in any dimension and even in function spaces (infinite dimensions).	Input vectors must be linearly independent to produce a full set. Dependent vectors are discarded.
Output Quality	Produces exact orthonormal vectors in exact arithmetic.	Other methods (Householder reflections, Givens rotations) are preferred in high-performance software.

Comparing strengths and limitations of the Gram–Schmidt process

🔧

WHEN TO USE GRAM–SCHMIDT

Think of Gram–Schmidt as a reliable hand tool — perfect for building intuition and for small-to-medium jobs. For heavy-duty industrial work (huge matrices on a computer), engineers reach for power tools like Householder reflections or QR decomposition algorithms. But knowing the hand tool makes the power tools much easier to understand.

SECTION 8

Connection to Advanced Theory

The Gram–Schmidt process is the engine behind a much bigger idea in linear algebra called QR decomposition. In QR decomposition, any matrix A is written as the product of two matrices: Q (whose columns are the orthonormal vectors from Gram–Schmidt) and R (an upper triangular matrix of the projection coefficients). This decomposition is used to solve systems of equations, compute eigenvalues, and power search algorithms.

Concept	Gram–Schmidt (this lesson)	QR Decomposition (next steps)
Input	A set of vectors	A matrix A (whose columns are vectors)
Output	Orthonormal vectors e₁, e₂, …	Matrices Q and R such that A = QR
Core Operation	Project and subtract	Same — the projection coefficients fill R
Applications	Building orthonormal bases, simplifying calculations	Solving least-squares problems, eigenvalue computation, data compression

Gram–Schmidt vs. QR Decomposition

If you continue studying linear algebra, you will also encounter orthogonal projections in statistics (least-squares regression), signal processing (Fourier analysis), and quantum mechanics (state vectors). The Gram–Schmidt process is the first step on a path that leads to all of these fields.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

In your own words, explain why we subtract the projection of v₂ onto u₁ when building u₂. What would happen if we skipped this step?

Show answer

We subtract the projection because it is the part of v₂ that points in the same direction as u₁. By removing it, the remaining vector u₂ has zero component along u₁, making the two vectors perpendicular (their dot product is 0). If we skipped this step, u₂ would still have some component along u₁, so the two vectors would not be orthogonal. The whole point of the process is to eliminate these overlapping components one at a time.

Question 2: BASIC CALCULATION

Apply the Gram–Schmidt process to v₁ = (1, 0) and v₂ = (1, 1). Find the orthonormal vectors e₁ and e₂.

Show answer

Set u₁ = v₁ = (1, 0). Compute proj_{u₁}(v₂): (v₂ · u₁)/(u₁ · u₁) = (1×1 + 1×0)/(1×1 + 0×0) = 1/1 = 1, so proj = 1 × (1, 0) = (1, 0). Then u₂ = v₂ − proj = (1, 1) − (1, 0) = (0, 1). Now normalize: ‖u₁‖ = 1, so e₁ = (1, 0). ‖u₂‖ = 1, so e₂ = (0, 1). The orthonormal basis is {(1, 0), (0, 1)}, which is just the standard basis — a nice sanity check!

Question 3: INTERMEDIATE

Apply the Gram–Schmidt process to v₁ = (1, 1, 0) and v₂ = (1, 0, 1) in ℝ³. Find orthonormal vectors e₁ and e₂.

Show answer

Set u₁ = (1, 1, 0). Compute v₂ · u₁ = 1×1 + 0×1 + 1×0 = 1. Compute u₁ · u₁ = 1 + 1 + 0 = 2. So proj = (1/2)(1, 1, 0) = (1/2, 1/2, 0). Then u₂ = (1, 0, 1) − (1/2, 1/2, 0) = (1/2, −1/2, 1). Normalize: ‖u₁‖ = √2, so e₁ = (1/√2, 1/√2, 0). ‖u₂‖ = √(1/4 + 1/4 + 1) = √(3/2) = √6/2. So e₂ = (1/2, −1/2, 1) × (2/√6) = (1/√6, −1/√6, 2/√6). You can verify e₁ · e₂ = 0 and both have length 1.

Question 4: APPLIED

A 3-D graphics engine represents a camera's 'right' direction as r = (2, 1, 0) and 'up' direction as u = (−1, 2, 1). These are not perpendicular. Use the Gram–Schmidt process to produce two orthonormal direction vectors for the camera. Why is orthonormality important for a camera in 3-D graphics?

Show answer

Set u₁ = r = (2, 1, 0). Compute u · r = (−1)(2) + (2)(1) + (1)(0) = 0. Since the dot product is already 0, the projection is the zero vector and u₂ = u = (−1, 2, 1). Now normalize: ‖u₁‖ = √(4+1+0) = √5, so e₁ = (2/√5, 1/√5, 0). ‖u₂‖ = √(1+4+1) = √6, so e₂ = (−1/√6, 2/√6, 1/√6). Orthonormality matters because the graphics card uses these directions to transform every pixel on the screen. If they are not perpendicular, the image will appear sheared or stretched; if they are not unit length, objects will be the wrong size. Orthonormal axes keep the scene looking correct.

Question 5: CRITICAL THINKING

Suppose you try to apply the Gram–Schmidt process to v₁ = (1, 2) and v₂ = (2, 4). What happens at the projection step, and what does the result tell you about the original vectors? Can you explain why this makes sense geometrically?

Show answer

Compute proj_{u₁}(v₂): v₂ · u₁ = 2×1 + 4×2 = 10. u₁ · u₁ = 1 + 4 = 5. So proj = (10/5)(1, 2) = 2(1, 2) = (2, 4). Then u₂ = v₂ − proj = (2, 4) − (2, 4) = (0, 0). The result is the zero vector, which means v₂ is entirely in the direction of v₁ — it is just v₁ scaled by 2. Geometrically, both vectors lie on the same line through the origin, so there is no second independent direction to create. The vectors are linearly dependent, and we can only produce a one-vector orthonormal set: e₁ = (1/√5, 2/√5). This illustrates that the Gram–Schmidt process also serves as a test for linear independence.

SUMMARY

Lesson Summary

Summary

The Gram–Schmidt process transforms any set of linearly independent vectors into an orthonormal set — vectors that are mutually perpendicular and each of unit length. The algorithm works in two repeating steps: first, compute the projection of the new vector onto every previously computed direction and subtract those projections (making the new vector orthogonal). Second, normalize the result by dividing by its magnitude so it has length 1.

Named after Jørgen Gram and Erhard Schmidt, the process is the foundation of QR decomposition and appears throughout data science, physics, and engineering. Key formulas to remember: the projection formula proj_u(v) = ((v · u) / (u · u)) × u, and the normalization formula e = u / ‖u‖. If a vector reduces to zero during the process, the original vectors were linearly dependent.