# Gram-Schmidt

A procedure that turns any linearly independent set into an orthonormal one by repeatedly subtracting off the components already accounted for.

**Rests on:** Linear Transformations, Orthogonality and Projections

*Mathematical Foundations · Linear Algebra*


## Why learn this

Gram–Schmidt is the procedure that takes a messy set of directions in space and straightens them out until they are perfectly at right angles to each other and all the same length. Imagine you have a pile of sticks that are tangled and pointing in overlapping ways. You want to rearrange them so they form a perfect corner, like the three edges of a box meeting at a point, but you are not allowed to throw any information away — the new sticks must still reach every corner the old ones did. This is useful because calculations become much simpler when your reference directions don't interfere with one another. For example, if you are trying to find the best fit for a line through a cloud of data points, or if you want to compress an image without losing important details, having these 'straightened out' directions makes the math stable and precise. Without this tool, many computer graphics and data analysis systems would produce noisy or incorrect results because they wouldn't know how to separate overlapping signals.


## The intuition

Let us walk through a concrete example in two dimensions. Imagine you have two sticks (vectors) starting from the origin.

Stick A points to the coordinate (3, 0). It lies flat on the horizontal axis.
Stick B points to the coordinate (1, 2). It goes right 1 unit and up 2 units.

These two sticks are independent — you cannot reach Stick B’s tip by just stretching Stick A. But they are not perpendicular; they overlap.

Step 1: Keep Stick A as it is. This becomes your first new stick, call it U1. So U1 = (3, 0).

Step 2: Now fix Stick B. We want to remove any part of B that points along U1. This removal process is called "projecting". Imagine shining a light from above; the shadow that Stick B casts onto Stick U1 is the overlap. 

To find this shadow (the projection), we use a simple formula: take the dot product of B and U1, divide by the length squared of U1, and multiply by U1.

The dot product of B(1, 2) and U1(3, 0) is (1*3) + (2*0) = 3.
The length squared of U1(3, 0) is 3^2 + 0^2 = 9.
So the scaling factor is 3 / 9 = 1/3.

The shadow vector is (1/3) * U1 = (1/3) * (3, 0) = (1, 0).
This means 1 unit of Stick B is "wasting" its effort pointing along the horizontal axis.

Step 3: Subtract this shadow from Stick B to get the part that is truly new and perpendicular to U1. This remainder is our second new stick, call it V2.

V2 = B - Shadow = (1, 2) - (1, 0) = (0, 2).

Check: Is V2 perpendicular to U1? U1 is (3, 0) and V2 is (0, 2). They form a right angle. One is horizontal, one is vertical. Perfect.

Step 4: Normalize. This means making the stick exactly length 1 without changing its direction.
The length of V2(0, 2) is 2.
Divide V2 by 2: U2 = (0, 1).

So, starting with messy sticks (3, 0) and (1, 2), Gram–Schmidt has produced two perfectly perpendicular, unit-length sticks: (3, 0) [which we keep as-is since it’s already on an axis] and (0, 1). Wait, actually, for U1, we usually also normalize it to be length 1. Let's do that.
Length of U1(3, 0) is 3. Normalized U1 becomes (1, 0).

Final result: The orthonormal basis is (1, 0) and (0, 1). These are the standard axes. We have straightened the messy input into the clean grid.

Why does this matter? In higher dimensions, like a machine learning model processing a word with 100 numbers, you don’t want one number to just be a scaled version of another (redundancy). Gram–Schmidt ensures each number carries unique information.


## An analogy

Imagine you are an architect trying to describe the orientation of a crooked picture frame hanging on a wall. The current frame is tilted, so its sides are not aligned with the vertical and horizontal edges of the room. You want to define a new set of axes that align perfectly with the room’s corners (vertical and horizontal) but still describe the exact same physical tilt.

You start with the first side of the frame, which points roughly up-right. You keep this direction as your baseline. Now, look at the second side of the frame, which should be perpendicular to the first. It isn’t quite; it leans a bit forward into the wall.

To fix this, you shine a light from the direction perpendicular to the room’s depth. The "shadow" the second side casts onto the first side represents the overlap or "leakage" between them. You subtract this shadow from the second side. What remains is the pure part of the second side that points in a truly new direction, completely at right angles to the first.

Finally, you stretch or shrink both sides so they are exactly one meter long, making them unit vectors. Now you have a clean, orthogonal coordinate system that describes the frame’s tilt without any directional confusion. The caveat is that this analogy fails if the picture was actually lying flat against the wall with no thickness — in math terms, if your starting sticks were already dependent (one was just a copy of the other), the "remaining" part would vanish completely, resulting in a zero vector, which breaks the process.


## Definition

Gram–Schmidt is a method that takes any set of independent directions and transforms them into a new set where every direction is at a right angle to all others and has a length of one. It does this by taking each new direction, removing the parts of it that overlap with the directions already chosen, and then scaling the result to unit length.


## How it connects

This process sits directly beside "orthonormal bases" (sets of perpendicular vectors of length 1) because Gram–Schmidt is the primary way to create one from arbitrary inputs. It also connects to "linear regression" because finding the best-fit line in statistics relies on projecting data onto perpendicular axes, a step made computationally stable by the orthogonal vectors Gram–Schmidt produces.


## The mathematics

Gram–Schmidt is a method for turning a messy set of vectors into a clean, tidy set. The goal is to produce a new list of vectors that are all at right angles to each other (orthogonal) and all have the same length of 1 (normalized). We call this an orthonormal basis.

To do this, we need two tools from linear algebra: the dot product and vector length.

The dot product takes two vectors of the same size. It multiplies their first numbers together, their second numbers together, and so on, then adds all those products up. The result is a single number. If the dot product of two vectors is zero, it means they are at right angles. If it is not zero, it tells us how much one vector points in the direction of the other.

The length (or norm) of a vector is found by squaring each of its numbers, adding those squares together, and taking the square root of the sum.

Here is how Gram–Schmidt works step by step. Suppose you have a list of linearly independent vectors v1, v2, ..., vk. "Linearly independent" means no vector in the list can be built from the others; they all point in genuinely new directions. We will build our clean list e1, e2, ..., ek one by one.

Step 1: Take the first original vector, v1. It is not yet length 1. We calculate its length, let us call it L1. Then we divide every number in v1 by L1. The result is our first clean vector, e1. Now e1 points in the same direction as v1, but has length 1.

Step 2: Take the second original vector, v2. It likely points partly in the direction of e1 and partly in a new direction. We want to remove the part that points along e1. To find that part, we calculate the dot product of v2 and e1. Let us call this number P2. This number P2 tells us how much of v2 is "covered" by e1. We then multiply the vector e1 by this number P2. The result is a new vector, which we will call proj2. This vector proj2 lies exactly along e1 and represents the shadow of v2 on e1.

Now we subtract this shadow from the original vector v2. We do this by subtracting the first number of proj2 from the first number of v2, and the second number of proj2 from the second number of v2. The result is a new vector, which we will call w2. By construction, w2 is at right angles to e1.

Now we normalize w2. We calculate its length, L2. We divide every number in w2 by L2. The result is our second clean vector, e2. Now e2 is at right angles to e1 and has length 1.

Step 3: Take the third original vector, v3. It might point partly along e1 and partly along e2. We need to remove both shadows. First, we find the shadow on e1 by calculating the dot product of v3 and e1, then multiplying that number by the vector e1. Second, we find the shadow on e2 by calculating the dot product of v3 and e2, then multiplying that number by the vector e2.

We add these two shadow vectors together to get a total shadow vector. We subtract this total shadow from v3. The result is a new vector w3. This vector w3 is now at right angles to both e1 and e2.

Finally, we normalize w3 by dividing it by its length to get e3.

We repeat this process for every remaining vector in the original list. For each new vector vi, we calculate its dot product with every clean vector ej already built (where j is less than i). We multiply each of those dot products by the corresponding clean vector ej, add all those results together to get a total shadow vector, subtract that from vi to get wi, and then divide wi by its length to get ei.

If at any step the leftover vector wi has length zero, it means the original vector vi was completely covered by the previous vectors. This would mean the original set was not linearly independent. If the original set is truly independent, we will never get a zero-length vector, and we will successfully build a full orthonormal basis.


## A worked example

We have two vectors in 2D space: v1 = (3, 4) and v2 = (1, 2). We want to turn them into two clean, perpendicular unit vectors e1 and e2.

Step 1: Start with v1 = (3, 4). We need its length. Square the first number: 3 * 3 = 9. Square the second number: 4 * 4 = 16. Add them: 9 + 16 = 25. Take the square root of 25. The length of v1 is 5.

Step 2: Normalize v1 to get e1. Divide each component by 5. First component: 3 / 5 = 0.6. Second component: 4 / 5 = 0.8. So, e1 = (0.6, 0.8). Check its length: 0.6 squared is 0.36, 0.8 squared is 0.64. 0.36 + 0.64 = 1. Square root of 1 is 1. Correct.

Step 3: Now handle v2 = (1, 2). We need to remove the part of v2 that points in the direction of e1. First, calculate the dot product of v2 and e1. Multiply matching components and add: (1 * 0.6) + (2 * 0.8) = 0.6 + 1.6 = 2.2. This number, 2.2, is how much v2 aligns with e1.

Step 4: Calculate the shadow vector on e1. Multiply the scalar 2.2 by the vector e1. First component: 2.2 * 0.6 = 1.32. Second component: 2.2 * 0.8 = 1.76. The shadow vector is (1.32, 1.76).

Step 5: Subtract the shadow from v2 to get the leftover vector w2. First component: 1 - 1.32 = -0.32. Second component: 2 - 1.76 = 0.24. So, w2 = (-0.32, 0.24). This vector is perpendicular to e1.

Step 6: Normalize w2 to get e2. First, find its length. Square the first component: (-0.32) * (-0.32) = 0.1024. Square the second component: 0.24 * 0.24 = 0.0576. Add them: 0.1024 + 0.0576 = 0.16. Take the square root of 0.16. The length is 0.4.

Step 7: Divide w2 by its length. First component: -0.32 / 0.4 = -0.8. Second component: 0.24 / 0.4 = 0.6. So, e2 = (-0.8, 0.6).

Result: The orthonormal basis is e1 = (0.6, 0.8) and e2 = (-0.8, 0.6). They are perpendicular because their dot product is (0.6 * -0.8) + (0.8 * 0.6) = -0.48 + 0.48 = 0. They both have length 1.


## From scratch, in Python

```python
# We'll need to compute dot products and lengths.
# A vector is just a list of numbers.

def dot(a, b):
    """Dot product of two vectors a and b."""
    total = 0
    for i in range(len(a)):
        total += a[i] * b[i]
    return total

def norm(a):
    """Length of vector a (square root of dot product with itself)."""
    return dot(a, a) ** 0.5

def gram_schmidt(vectors):
    """Turns a list of independent vectors into an orthonormal list."""
    orthonormal = []
    for v in vectors:
        # Start with the original vector
        w = v[:]
        # Subtract projections onto each already-constructed vector
        for e in orthonormal:
            proj = dot(v, e)
            # Subtract proj * e from w
            w = [w[i] - proj * e[i] for i in range(len(v))]
        # Normalize
        n = norm(w)
        if n < 1e-12:
            # This means the original set was not independent
            raise ValueError("Vectors are not linearly independent")
        e_new = [w[i] / n for i in range(len(v))]
        orthonormal.append(e_new)
    return orthonormal

# Test with our example
v1 = [3, 4]
v2 = [1, 2]
result = gram_schmidt([v1, v2])
print(result)  # prints [[0.6, 0.8], [-0.8, 0.6]]

# Verify they are orthonormal
print(dot(result[0], result[1]))  # 0.0 (approximately)
print(norm(result[0]))            # 1.0
print(norm(result[1]))            # 1.0
```


## The same thing, with a framework

```python
In NumPy, you can use `numpy.linalg.qr` which internally performs a modified Gram–Schmidt (or similar) to give the QR decomposition. The Q matrix is orthonormal. Alternatively, you can use `numpy.linalg.qr` directly:

    import numpy as np
    A = np.array([[3, 1], [4, 2]])  # columns are v1 and v2
    Q, R = np.linalg.qr(A)
    # Q's columns are orthonormal and span the same space as A's columns
    print(Q)  # columns are the orthonormal basis

Under the hood, `numpy.linalg.qr` does the same subtract-the-projections process but in a numerically more stable way, using Householder reflections or the modified Gram–Schmidt algorithm.
```


## What the code does

The function `dot` computes the dot product by looping over each index and adding the product of the corresponding entries. For example, `dot([1,2], [3,4])` gives 1*3 + 2*4 = 11.

The function `norm` uses the dot product with itself and takes the square root, giving the length.

In `gram_schmidt`, we keep a list `orthonormal` to hold the resulting vectors. For each input vector `v`, we copy it to `w`. Then for each already-found vector `e`, we compute the projection of `v` onto `e` (using the dot product) and subtract that multiple of `e` from `w`. This removes the component that points along `e`. After subtracting all projections, `w` is perpendicular to all existing `e`s. We then normalize `w` by dividing by its length. If the length is very small (nearly zero), it means the input vectors were not independent, and we raise an error. Otherwise, we add `e_new` to our result. Finally, we return the list of orthonormal vectors.

The code is plain Python and uses lists, loops, and a raise statement — nothing exotic. The framework version in NumPy does the same thing but is optimized and more numerically stable.


## Common misconceptions

**Gram–Schmidt changes the original vectors** — Gram–Schmidt replaces my vectors with completely different ones, so I lose information.

The new vectors are different, but they span the same space as the original set — every combination of the originals can be expressed as a combination of the new ones. The information is preserved; only the representation changes. In fact: Gram–Schmidt creates a new set of vectors that are orthonormal but span the same space as the original set. No information is lost; the new basis is just easier to work with.

**Gram–Schmidt only works in 2D or 3D** — I can only picture directions in two or three dimensions, so Gram–Schmidt must not work in higher dimensions.

The math works the same in any number of dimensions. The dot product and vector operations are defined for vectors of arbitrary length. Visual intuition fails, but the algebra is identical. In fact: Gram–Schmidt works in any dimension — 2D, 3D, or 1000-dimensional space. The same formulas and procedures apply.

**The classical Gram–Schmidt I learned is fine for real code** — I coded the simple Gram–Schmidt loop, and it works, so I'll use it in production.

In floating-point arithmetic, the simple version loses orthogonality because rounding errors accumulate. The modified version (re-projecting each time) is far more stable. In fact: The classical Gram–Schmidt is numerically unstable; real implementations use the modified Gram–Schmidt or QR decomposition, which re-orthogonalize to prevent error buildup.

**Gram–Schmidt can orthogonalize any set of vectors** — I can apply Gram–Schmidt to any list of vectors and get an orthonormal basis.

If the vectors are not linearly independent (some is a combination of others), you'll get a zero vector, and the process fails — you cannot build more than the dimension allows. In fact: Gram–Schmidt requires the original set to be linearly independent. If not, you'll get a zero vector, indicating that the set was redundant.

**Orthogonal and orthonormal are the same** — Orthogonal and orthonormal mean the same thing: perpendicular.

Orthogonal means perpendicular (dot product zero). Orthonormal means the vectors are orthogonal AND each has length 1. You can have an orthogonal set without normalizing. In fact: Orthogonal: all pairs are at right angles. Orthonormal: they are orthogonal and each has unit length. Normalization is a separate step.


## In short

Gram–Schmidt is a procedure that takes any linearly independent set of vectors and produces an orthonormal set (all perpendicular, all length 1) that spans the same space. The core idea: for each new vector, subtract off its projection onto each already-handled direction, leaving only the truly new part, then normalize. This is the constructive foundation of orthonormal bases, which are crucial in least-squares regression (via QR), PCA, and many numerical algorithms. Remember: use the modified version for stability, and never forget to check linear independence.


## Where this is used

Gram–Schmidt appears in several places in modern AI, sometimes explicitly and sometimes under the hood.

1. **Least-squares regression:** In everyday applied machine learning, fitting a linear model often comes down to solving the normal equations, which involve inverting a matrix — but that is numerically unstable. The QR decomposition, which is a direct product of Gram–Schmidt, is the preferred method. It avoids squaring the condition number, making the solution more accurate. A developer writes `numpy.linalg.lstsq` which internally uses QR, rather than explicitly computing the inverse. If they did it by hand, they would follow the Gram–Schmidt approach to create an orthogonal basis for the design matrix.

2. **Principal Component Analysis (PCA):** PCA finds the directions of greatest variance in data. The eigenvectors of the covariance matrix are those directions, and they are naturally orthogonal. In practice, algorithms like SVD (which is related to eigen-decomposition) compute these orthogonal directions. Gram–Schmidt is the conceptual basis for constructing an orthonormal basis, and it appears in algorithms that iteratively find eigenvectors. For example, the power iteration method, which repeatedly multiplies by the covariance matrix, can be combined with Gram–Schmidt (in a process called orthogonal iteration) to find several eigenvectors at once. Language models use PCA-like techniques for embedding dimensionality reduction (e.g., in visualization or in some compression methods).

3. **Large language models (LLMs):** Embeddings — the numerical representations of words or tokens — are vectors. Sometimes these embeddings are post-processed to be more orthogonal (e.g., using the Gram–Schmidt process on a subset of embeddings) to reduce redundancy in the representation space. In some transformer architectures, attention heads are regularized to be orthogonal, which improves diversity in what each head attends to. The theoretical analysis of these models often assumes orthonormal initialization or uses Gram–Schmidt to orthogonalize weight matrices — for example, in some weight initialization schemes, orthogonal initialization uses the QR decomposition to generate a random orthogonal matrix. A developer using PyTorch might write `torch.nn.init.orthogonal_` which uses QR on a random matrix to produce orthogonal weights.

4. **Small models on devices (TinyML):** On-device models must be compact and numerically stable, using low-precision numbers. Orthonormal bases are numerically stable because you avoid ill-conditioned matrices. In model compression, techniques like quantization sometimes involve orthogonalizing the weight matrices to reduce error. Gram–Schmidt is also used in the modified version (MGS) in numerical linear algebra libraries that run on embedded devices.

5. **Retrieval-Augmented Generation (RAG):** In RAG, documents are embedded into vectors, and retrieval is done by finding the nearest neighbors using cosine similarity. If the embeddings are not well-distributed, some directions dominate. Applying Gram–Schmidt to the set of all document embeddings (or a sample) can decorrelate them, making retrieval more discriminative. In practice, you might use SVD to decorrelate embeddings, which is a related concept. The Gram–Schmidt process is the conceptual foundation for understanding why decorrelation works.

6. **Agentic systems:** Agents that plan and call tools often use embeddings to represent state and actions. If these representations are redundant, the agent may make poor decisions. Orthogonalization can help by ensuring each dimension carries independent information. In some reinforcement learning algorithms, feature bases are explicitly orthogonalized using Gram–Schmidt to improve value function approximation.

7. **Forecasting and signal processing:** In time-series forecasting, feature engineering often involves constructing orthogonal basis functions (like polynomial or Fourier bases). Gram–Schmidt can be used to create orthogonal polynomials from raw features, improving the conditioning of the regression problem.

8. **Speech and audio:** In audio processing, independent component analysis (ICA) and beamforming use orthogonalization steps that are essentially Gram–Schmidt on the signal vectors. Libraries like `scipy.linalg.orth` use SVD, but the concept is the same.

**What a developer actually writes:** In Python, a developer might use `numpy.linalg.qr` to orthonormalize a set of vectors, or `torch.linalg.qr` in PyTorch. The key is that they rely on the QR decomposition to do Gram–Schmidt in a stable way. When they need orthogonal initialization for a neural network, they write `torch.nn.init.orthogonal_`. When they analyze embeddings, they might compute the SVD and take the top components, which is the same spirit.

**What breaks when done badly:** If you use the classical Gram–Schmidt naively (as in our from-scratch code) on a large set of vectors, the loss of orthogonality due to floating-point rounding can be severe — the resulting vectors may drift from being perpendicular. That's why modified Gram–Schmidt is used in practice. If you forget to normalize, you get an orthogonal but not orthonormal basis, which is usually fine but complicates calculations. More importantly, if you apply Gram–Schmidt to a set that is not linearly independent, you get a zero vector and an error — but if you ignore that and continue, you'll publish nonsense.

In practice, in machine learning, the concept appears more in the theoretical foundations than in day-to-day code. But understanding it lets you appreciate why `numpy.linalg.lstsq` is stable, why PCA works, and why orthogonal initialization helps training. The next time you see a QR decomposition in a solution to a least-squares problem or a paper on orthogonalization, you'll know exactly what it does.


---

Read this on the web: https://basavapurushottam.com/learn-ai/gram-schmidt
