Proof That Gram-Schmidt Preserves Spans

What Span Preservation Says

Gram–Schmidt changes the vectors in a list by subtracting components along earlier outputs. That subtraction alters the individual vectors, but it does not alter the set of vectors that all the list members can produce by linear combinations. More precisely, at every stage, the first \(k\) inputs and the first \(k\) outputs span the same subspace. The key is to use the recursion twice: once to express each output using inputs, and once to recover each input using outputs.

Let \(V\) be an inner product space over \(\mathbb{F}\), where \(\mathbb{F}\) is \(\mathbb{R}\) or \(\mathbb{C}\). For a list \(\mathbf{v}_1,\dots,\mathbf{v}_k\), its span, \(\operatorname{span}\{\mathbf{v}_1,\dots,\mathbf{v}_k\}\), is the set of all linear combinations \(c_1\mathbf{v}_1+\cdots+c_k\mathbf{v}_k\), with \(c_i\in\mathbb{F}\). A span is a set of vectors, while the input and output collections in Gram–Schmidt are ordered lists.

We use the inner product convention that the first slot is linear. Given inputs \(\mathbf{v}_1,\dots,\mathbf{v}_m\), the unnormalized Gram–Schmidt outputs are defined recursively by

Each denominator must be nonzero, so to carry out the recursion through stage \(m\), the outputs \(\mathbf{u}_1,\dots,\mathbf{u}_{m-1}\) must be nonzero. The last output \(\mathbf{u}_m\) may be zero: its formula only divides by earlier outputs. Normalizing outputs to have length one is a separate step and is not needed for the span argument.

Why the Recursion Gives Both Inclusions

Equality of spans means proving two containments. The recursion directly writes \(\mathbf{u}_k\) as \(\mathbf{v}_k\) minus a linear combination of earlier outputs. This places the new output in the span of the current input and earlier outputs. In the other direction, rearranging the same formula writes \(\mathbf{v}_k\) as the new output plus a linear combination of earlier outputs. Induction then makes each containment precise.

Proof. We prove the two containments for each initial segment by induction on \(k\). For \(k=1\), \(\mathbf{u}_1=\mathbf{v}_1\), so the spans are equal. Assume the spans agree at stage \(k-1\), where \(2\le k\le m\). The recursion gives \(\mathbf{u}_k=\mathbf{v}_k-\sum_{j=1}^{k-1}\frac{\langle\mathbf{v}_k,\mathbf{u}_j\rangle}{\langle\mathbf{u}_j,\mathbf{u}_j\rangle}\mathbf{u}_j\). Every \(\mathbf{u}_j\) in this sum belongs to \(\operatorname{span}\{\mathbf{u}_1,\dots,\mathbf{u}_{k-1}\}=\operatorname{span}\{\mathbf{v}_1,\dots,\mathbf{v}_{k-1}\}\). Therefore \(\mathbf{u}_k\in\operatorname{span}\{\mathbf{v}_1,\dots,\mathbf{v}_k\}\). The earlier outputs also belong to this span by the induction hypothesis. Thus \(\operatorname{span}\{\mathbf{u}_1,\dots,\mathbf{u}_k\}\subseteq\operatorname{span}\{\mathbf{v}_1,\dots,\mathbf{v}_k\}\). Rearranging the recursion gives \(\mathbf{v}_k=\mathbf{u}_k+\sum_{j=1}^{k-1}\frac{\langle\mathbf{v}_k,\mathbf{u}_j\rangle}{\langle\mathbf{u}_j,\mathbf{u}_j\rangle}\mathbf{u}_j\). This puts \(\mathbf{v}_k\) in \(\operatorname{span}\{\mathbf{u}_1,\dots,\mathbf{u}_k\}\), and the earlier inputs belong there by the induction hypothesis. Hence \(\operatorname{span}\{\mathbf{v}_1,\dots,\mathbf{v}_k\}\subseteq\operatorname{span}\{\mathbf{u}_1,\dots,\mathbf{u}_k\}\). The two containments prove equality at stage \(k\), completing the induction. \(\square\)

The proof does not require that the inputs be linearly independent. It requires only that the recursion be defined: each denominator used must come from a nonzero earlier output. If the final output is zero, the formula still proves the span equality at that final stage.

Reading the Two Directions in a Calculation

The containment argument depends on the structure of the formulas, not on the particular coordinates. At each stage, the new output is the current input plus a combination of earlier outputs. Conversely, the current input is the new output plus a combination of those same earlier outputs. The next examples show this structure in a three-vector calculation and in a space that is not \(\mathbb{R}^n\).

The Same Argument in a Polynomial Space

A Triangular View of the Formulas

Proof. The second statement is the recursion rearranged: \(\mathbf{v}_k=\mathbf{u}_k+\sum_{j=1}^{k-1}\frac{\langle\mathbf{v}_k,\mathbf{u}_j\rangle}{\langle\mathbf{u}_j,\mathbf{u}_j\rangle}\mathbf{u}_j\). For the first statement, use induction. At \(k=1\), \(\mathbf{u}_1=\mathbf{v}_1\), so the statement holds with an empty sum. Suppose each \(\mathbf{u}_j\), for \(j<k\), is \(\mathbf{v}_j\) plus a combination of earlier inputs. Substituting those expressions into \(\mathbf{u}_k=\mathbf{v}_k-\sum_{j=1}^{k-1}\frac{\langle\mathbf{v}_k,\mathbf{u}_j\rangle}{\langle\mathbf{u}_j,\mathbf{u}_j\rangle}\mathbf{u}_j\) expresses \(\mathbf{u}_k\) as \(\mathbf{v}_k\) plus a combination of \(\mathbf{v}_1,\dots,\mathbf{v}_{k-1}\). This proves the first statement at stage \(k\), and induction completes the proof. \(\square\)

The word “triangular” describes the restriction that stage \(k\) only involves vectors from stages \(1\) through \(k\); later vectors never enter its formula. It is another way to understand why each initial segment has the same span: each list can be built from the other without using any vector beyond the same stage.

Common Pitfall: Omitting the Denominator

A projection coefficient is not generally just \(\langle\mathbf{v}_k,\mathbf{u}_j\rangle\). It also divides by the squared norm of the vector being projected onto. In the first worked example, the incorrect calculation \(\mathbf{u}_2=(1,0)-1(1,1)=(0,-1)\) uses the inner product \(1\) as the coefficient and omits the denominator \(\langle\mathbf{u}_1,\mathbf{u}_1\rangle=2\). It fails the defining orthogonality check: \(\langle(0,-1),(1,1)\rangle=-1\ne0\). The correction is to use \(1/2\), yielding \(\mathbf{u}_2=(1/2,-1/2)\) and \(\langle\mathbf{u}_2,\mathbf{u}_1\rangle=1/2-1/2=0\).

Span preservation is a statement about the list at every stage, not just about the final output collection. It follows from two explicit identities: the recursion expresses an output through the current input and earlier outputs, and its rearrangement expresses the current input through the current output and earlier outputs. Keeping both directions visible prevents a one-sided containment from being mistaken for equality.