The General Gram-Schmidt Recursion

The Recursion Uses What Has Already Been Built

Gram-Schmidt is a step-by-step procedure: at each stage, remove from the next input vector its components along the normalized vectors already constructed, then normalize what remains. The general recursion packages the two-vector and three-vector calculations into one rule that works for any finite independent ordered list. Its order matters: the residual for the \(k\)th input is formed using the first \(k-1\) normalized outputs, not the later inputs.

Let \(V\) be a finite-dimensional inner product space over \(\mathbb{F}\), where \(\mathbb{F}\) is \(\mathbb{R}\) or \(\mathbb{C}\). The inner product is taken to be linear in its first slot and conjugate-linear in its second slot. The norm is \(\|\mathbf{v}\|=\sqrt{\langle\mathbf{v},\mathbf{v}\rangle}\). An ordered list is linearly independent if the only linear combination of its vectors equal to \(\mathbf{0}\) has all coefficients zero. A list is orthonormal if each vector has norm \(1\) and distinct vectors in the list have inner product \(0\).

For a unit vector \(\mathbf{q}\), the component of \(\mathbf{x}\) along \(\mathbf{q}\) is \(\langle\mathbf{x},\mathbf{q}\rangle\mathbf{q}\). The order of the inner product slots matters over \(\mathbb{C}\): with the convention above, this coefficient is \(\langle\mathbf{x},\mathbf{q}\rangle\), not \(\langle\mathbf{q},\mathbf{x}\rangle\). Removing this component leaves a residual with no component along \(\mathbf{q}\).

Proof. Write \(\mathbf{r}=\mathbf{x}-\dfrac{\langle\mathbf{x},\mathbf{q}\rangle}{\langle\mathbf{q},\mathbf{q}\rangle}\mathbf{q}\). Since the inner product is linear in the first slot,

The denominator is nonzero because \(\mathbf{q}\ne\mathbf{0}\) and the inner product is positive definite. If \(\|\mathbf{q}\|=1\), then \(\langle\mathbf{q},\mathbf{q}\rangle=1\), giving the stated special case. \(\square\)

The General Gram-Schmidt Formulas

Start with an ordered independent list \((\mathbf{v}_1,\dots,\mathbf{v}_p)\). Use \(\mathbf{u}_k\) for the residual at stage \(k\), before normalization, and \(\mathbf{q}_k\) for the normalized output. The first stage has no earlier directions to remove. Every later stage subtracts one component for each earlier normalized vector.

Each coefficient \(\langle\mathbf{v}_k,\mathbf{q}_j\rangle\) measures the component of the current input along one of the unit vectors already constructed. The recursion uses the original input \(\mathbf{v}_k\) in these coefficients. It does not use \(\mathbf{u}_k\) in place of \(\mathbf{v}_k\), nor does it subtract components along the unnormalized residuals from earlier stages.

The procedure assumes each residual is nonzero before it is normalized. For an independent input list in a finite-dimensional inner product space, the standard Gram-Schmidt result is that these residuals are nonzero. The proof of that implication is a separate result; here the recursion is stated with its necessary condition so that it also makes sense for lists that may be dependent.

For \(k=1\), the sum of earlier components is empty, so the first residual is just the first input. For \(k=2\), there is one term to subtract. For \(k=4\), there are three terms. The growing number of terms is the main bookkeeping feature: at stage \(k\), use every \(\mathbf{q}_j\) with \(j<k\), exactly once.

Worked Calculations Before the Four-Vector Trace

Tracing a Symbolic Four-Vector Input

Now let \((\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4)\) be an independent ordered list in \(V\). The calculation can be traced without specifying coordinates: each coefficient is an inner product with an output already constructed. This symbolic form is useful when the vectors belong to a function space, a matrix space, or an abstract inner product space rather than \(\mathbb{R}^n\).

The standard Gram-Schmidt conclusions include that the normalized outputs are orthonormal and that each initial segment of the outputs spans the same space as the corresponding initial segment of inputs. These conclusions explain why the procedure is useful, but their proofs are separate: the orthogonality proof, the span-preservation proof, and the proof that independence ensures nonzero residuals are treated as distinct results.

Common Mistake: Using an Unnormalized Vector as if It Were Unit

A projection coefficient of the form \(\langle\mathbf{x},\mathbf{q}\rangle\) applies when \(\mathbf{q}\) has norm \(1\). If the direction vector is not normalized, its squared norm must also be accounted for. For example, with \(\mathbf{v}_1=(1,1,0)^\top\) and \(\mathbf{v}_2=(1,0,1)^\top\), a mistaken calculation subtracts \(\langle\mathbf{v}_2,\mathbf{v}_1\rangle\mathbf{v}_1\). Since \(\langle\mathbf{v}_2,\mathbf{v}_1\rangle=1\), this gives the incorrect residual

It is not orthogonal to \(\mathbf{v}_1\), because \((0,-1,1)\cdot(1,1,0)=-1\ne0\). The corrected coefficient for a non-unit vector is \(\langle\mathbf{v}_2,\mathbf{v}_1\rangle/\langle\mathbf{v}_1,\mathbf{v}_1\rangle=1/2\). Subtracting \(\frac12\mathbf{v}_1\) gives \((1/2,-1/2,1)^\top\), whose dot product with \(\mathbf{v}_1\) is \(1/2-1/2=0\). Gram-Schmidt avoids this denominator at each stage by normalizing first, then using unit vectors for all subsequent projections.

For a practical check at any stage, count the earlier outputs: stage \(k\) has \(k-1\) coefficients and \(k-1\) subtracted terms. Then check that the residual equation rearranges to the original input, and calculate its norm before dividing. In exact computations, keep radicals and fractions exact until the final normalized vector is written.