Proof That Gram-Schmidt Outputs Are Orthogonal

The Claim Behind the Recursion

Gram–Schmidt builds vectors one at a time. At each step, it subtracts from the new input its components in the directions of the normalized vectors already produced. The central claim of this tutorial is that this subtraction does what it is meant to do: the new residual is orthogonal to every earlier normalized output. The proof is an induction, because the cancellation at each step depends on the earlier outputs being orthonormal.

Let \(V\) be a finite-dimensional inner product space over \(\mathbb{F}\), where \(\mathbb{F}\) is \(\mathbb{R}\) or \(\mathbb{C}\). We use the convention that the inner product is linear in its first slot and conjugate-linear in its second slot. The norm is \(\|\mathbf{v}\|=\sqrt{\langle\mathbf{v},\mathbf{v}\rangle}\). Vectors \(\mathbf{x}\) and \(\mathbf{y}\) are orthogonal when \(\langle\mathbf{x},\mathbf{y}\rangle=0\). A list is orthonormal if every vector has norm \(1\) and every two distinct vectors in the list are orthogonal.

The coefficient in each subtraction is determined by our inner-product convention. If \(\mathbf{q}_j\) has norm \(1\), then subtracting \(c\mathbf{q}_j\) changes the inner product with \(\mathbf{q}_j\) to \(\langle\mathbf{v}_k-c\mathbf{q}_j,\mathbf{q}_j\rangle=\langle\mathbf{v}_k,\mathbf{q}_j\rangle-c\). Here we used linearity in the first slot and \(\langle\mathbf{q}_j,\mathbf{q}_j\rangle=1\). Choosing \(c=\langle\mathbf{v}_k,\mathbf{q}_j\rangle\) cancels that inner product. The induction proof shows that all the subtractions work together, not just one at a time.

The Induction Proof

Proof. We use induction on the number of outputs constructed. For the first output, \(\mathbf{q}_1=\mathbf{r}_1/\|\mathbf{r}_1\|\), so \(\|\mathbf{q}_1\|=1\). There are no earlier vectors to test against, so the orthogonality claim at this stage has no cases.

Now suppose \(2\le k\le p\), and assume that \(\mathbf{q}_1,\dots,\mathbf{q}_{k-1}\) are orthonormal. Fix any index \(i\) with \(1\le i<k\). Using the recursion and linearity in the first slot gives

By the induction hypothesis, \(\langle\mathbf{q}_j,\mathbf{q}_i\rangle=0\) when \(j\ne i\), and \(\langle\mathbf{q}_i,\mathbf{q}_i\rangle=1\). Therefore every term in the sum vanishes except the term with \(j=i\), which equals \(\langle\mathbf{v}_k,\mathbf{q}_i\rangle\). Hence \(\langle\mathbf{r}_k,\mathbf{q}_i\rangle=\langle\mathbf{v}_k,\mathbf{q}_i\rangle-\langle\mathbf{v}_k,\mathbf{q}_i\rangle=0\). Since \(i\) was any index less than \(k\), the residual is orthogonal to every earlier output.

Because \(\mathbf{r}_k\ne\mathbf{0}\), its norm is positive and \(\mathbf{q}_k=\mathbf{r}_k/\|\mathbf{r}_k\|\) is defined. Its norm is \(1\), since dividing a vector by its norm gives a unit vector. Also, for each \(i<k\), conjugate-linearity in the second slot gives \(\langle\mathbf{q}_k,\mathbf{q}_i\rangle=\langle\mathbf{r}_k,\mathbf{q}_i\rangle/\|\mathbf{r}_k\|=0\). Thus the list through \(\mathbf{q}_k\) is orthonormal, which supplies the induction hypothesis needed at the next step. Induction proves the claim for every \(k\). \(\square\)

The proof has two linked parts. First, orthonormality of the earlier outputs makes the sum in the inner product collapse to exactly one term. Second, normalizing a nonzero residual preserves its orthogonality to those earlier outputs and gives the new output norm \(1\). Both parts are needed for the induction to continue.

Worked Examples of the Cancellation

Why These Coefficients Are Forced

Proof. Put \(\mathbf{w}=\mathbf{v}-\sum_{j=1}^{m}c_j\mathbf{q}_j\). For each \(i\), linearity in the first slot and orthonormality give \(\langle\mathbf{w},\mathbf{q}_i\rangle=\langle\mathbf{v},\mathbf{q}_i\rangle-\sum_{j=1}^{m}c_j\langle\mathbf{q}_j,\mathbf{q}_i\rangle=\langle\mathbf{v},\mathbf{q}_i\rangle-c_i\). If \(\mathbf{w}\) is orthogonal to every \(\mathbf{q}_i\), this expression is zero for each \(i\), so \(c_i=\langle\mathbf{v},\mathbf{q}_i\rangle\). Conversely, if all these coefficient equalities hold, the displayed expression is zero for each \(i\), so \(\mathbf{w}\) is orthogonal to every vector in the list. This proves both directions. \(\square\)

This proposition explains the subtraction rule: among sums using the earlier orthonormal vectors, the coefficients that make the remainder orthogonal to each of them are exactly the inner products in the recursion. At stage \(k\), the induction hypothesis supplies the orthonormal list needed to apply this calculation.

Common Mistake: Reversing the Complex Inner Product

In \(\mathbb{C}^2\) with the convention used above, a tempting mistake is to use \(\langle\mathbf{q}_1,\mathbf{v}_2\rangle\) as the coefficient instead of \(\langle\mathbf{v}_2,\mathbf{q}_1\rangle\). For the complex example, these values are \((1+i)/\sqrt{2}\) and \((1-i)/\sqrt{2}\), respectively. They are conjugates, not equal. Using the reversed coefficient gives the incorrect proposed residual

It fails the required test:

The correction is to keep the vector being adjusted in the first slot: with the stated convention, the coefficient is \(\langle\mathbf{v}_2,\mathbf{q}_1\rangle\). In a real inner product, reversing the slots does not change the value, so this particular error can go unnoticed in real calculations. The complex check exposes it.

The orthogonality result has a precise scope. It guarantees that each defined residual is orthogonal to the earlier normalized outputs; it does not by itself guarantee that a residual is nonzero. If a residual is zero, the division needed to define its normalized output is unavailable, and the induction proceeds only through the outputs that are defined.