What a Zero Residual Tells You
Gram–Schmidt does not require its input list to be linearly independent. When an input is already a combination of earlier inputs, removing its components along the directions already found leaves nothing: its residual is the zero vector. This is useful information, not a failure of the method. It tells us not to normalize that residual and not to add a new direction to the orthonormal list.
Let \(V\) be an inner product space over \(\mathbb{F}\), where \(\mathbb{F}=\mathbb{R}\) or \(\mathbb{C}\), and let \(\mathbf{x}_1,\dots,\mathbf{x}_m\) be a finite list in \(V\). The inner product convention is linear in its first slot. The norm is \(\|\mathbf{x}\|=\sqrt{\langle\mathbf{x},\mathbf{x}\rangle}\), and an orthonormal list has unit vectors that are pairwise orthogonal. The examples below use the usual dot product in \(\mathbb{R}^n\).
Because the inner product is linear in the first slot, the coefficient of a unit vector \(\mathbf{q}_j\) in this formula is \(\langle\mathbf{x}_k,\mathbf{q}_j\rangle\). In particular, the formula subtracts the components along the directions already produced; it does not require those directions to correspond one-for-one with the input indices. If an input is dependent, the list of \(\mathbf{q}\)'s simply grows by fewer than one vector at that step.
Why the Algorithm Detects Dependence
Proof. We use induction on the number of inputs processed. Before any input is processed, both lists are empty and both spans equal \(\{\mathbf{0}\}\); the empty list is orthonormal. Suppose the claim holds before processing \(\mathbf{x}_k\). By the induction hypothesis, the current \(\mathbf{q}_j\)'s are orthonormal. For each \(1\leq \ell\leq s\), the residual formula gives $$ \langle\mathbf{r}_k,\mathbf{q}_\ell\rangle = \langle\mathbf{x}_k,\mathbf{q}_\ell\rangle - \sum_{j=1}^{s}\langle\mathbf{x}_k,\mathbf{q}_j\rangle \langle\mathbf{q}_j,\mathbf{q}_\ell\rangle = \langle\mathbf{x}_k,\mathbf{q}_\ell\rangle- \langle\mathbf{x}_k,\mathbf{q}_\ell\rangle = 0, $$ since \(\langle\mathbf{q}_j,\mathbf{q}_\ell\rangle=1\) when \(j=\ell\) and \(0\) otherwise. Thus the residual is orthogonal to every existing \(\mathbf{q}_\ell\). Also, $$ \mathbf{x}_k=\sum_{j=1}^{s}\langle\mathbf{x}_k,\mathbf{q}_j\rangle\mathbf{q}_j+\mathbf{r}_k. $$ If \(\mathbf{r}_k=\mathbf{0}\), this equation places \(\mathbf{x}_k\) in the existing span, so adding it to the input list does not change that span; the orthonormal list also stays unchanged. If \(\mathbf{r}_k\ne\mathbf{0}\), then \(\mathbf{q}_{s+1}=\mathbf{r}_k/\|\mathbf{r}_k\|\) is a unit vector orthogonal to every existing \(\mathbf{q}_j\). It belongs to the span of the existing input vectors together with \(\mathbf{x}_k\), by the residual formula. Conversely, the displayed expression for \(\mathbf{x}_k\) shows that \(\mathbf{x}_k\) belongs to the span of the old \(\mathbf{q}_j\)'s and \(\mathbf{r}_k\), hence to the span after adjoining \(\mathbf{q}_{s+1}\). The spans therefore agree after this input as well. This completes the induction. \(\square\)
Proof. The theorem says that the earlier inputs and the existing orthonormal vectors span the same space. If \(\mathbf{r}_k=\mathbf{0}\), the residual formula expresses \(\mathbf{x}_k\) as a combination of the existing \(\mathbf{q}_j\)'s, so it belongs to the span of the earlier inputs. Conversely, suppose \(\mathbf{x}_k\) belongs to the span of the earlier inputs. It then belongs to the span of the orthonormal list, so write \(\mathbf{x}_k=\sum_{j=1}^{s}a_j\mathbf{q}_j\). Taking the inner product with \(\mathbf{q}_\ell\) gives \(\langle\mathbf{x}_k,\mathbf{q}_\ell\rangle=a_\ell\). Substitution in the residual formula gives \(\mathbf{r}_k=\mathbf{x}_k-\sum_{j=1}^{s}a_j\mathbf{q}_j=\mathbf{0}\). If the list is empty, its span is \(\{\mathbf{0}\}\), and the same conclusion follows directly. \(\square\)
Worked Examples: Zero and Nonzero Residuals
Worked Example: A Dependent Third Input
Apply Gram–Schmidt to \(\mathbf{x}_1=(1,0,1)\), \(\mathbf{x}_2=(0,1,1)\), and \(\mathbf{x}_3=(1,1,2)\) in \(\mathbb{R}^3\). Determine what the third residual says.
The first residual is \(\mathbf{r}_1=\mathbf{x}_1=(1,0,1)\), with \(\|\mathbf{r}_1\|=\sqrt{1^2+0^2+1^2}=\sqrt{2}\). Thus \(\mathbf{q}_1=(1,0,1)/\sqrt{2}\). For the second input, $$ \langle\mathbf{x}_2,\mathbf{q}_1\rangle=\frac{1}{\sqrt{2}}, \qquad \mathbf{r}_2=(0,1,1)-\frac{1}{\sqrt{2}}\frac{(1,0,1)}{\sqrt{2}} =\left(-\frac12,1,\frac12\right). $$ Its squared norm is \(\frac14+1+\frac14=\frac32\), so \(\|\mathbf{r}_2\|=\sqrt{6}/2\), and \(\mathbf{q}_2=(-1,2,1)/\sqrt{6}\). The two vectors are orthogonal because $$ \langle\mathbf{q}_1,\mathbf{q}_2\rangle =\frac{-1+0+1}{\sqrt{12}}=0. $$
For the third input, the projection coefficients are $$ \langle\mathbf{x}_3,\mathbf{q}_1\rangle=\frac{3}{\sqrt{2}}, \qquad \langle\mathbf{x}_3,\mathbf{q}_2\rangle=\frac{-1+2+2}{\sqrt{6}}=\frac{3}{\sqrt{6}}. $$ The corresponding projected vectors are $$ \frac{3}{\sqrt{2}}\mathbf{q}_1=\left(\frac32,0,\frac32\right), \qquad \frac{3}{\sqrt{6}}\mathbf{q}_2=\left(-\frac12,1,\frac12\right). $$ Their sum is \((1,1,2)\), so \(\mathbf{r}_3=(1,1,2)-(1,1,2)=\mathbf{0}\). The zero residual detects that the third input lies in the span of the first two.
Check: Directly, \(\mathbf{x}_3=\mathbf{x}_1+\mathbf{x}_2=(1,0,1)+(0,1,1)=(1,1,2)\). This confirms the dependence indicated by the residual.
Worked Example: Dependent Inputs Do Not Stop the Process
Process \(\mathbf{x}_1=(1,0,0)\), \(\mathbf{x}_2=(2,0,0)\), \(\mathbf{x}_3=(0,1,0)\), and \(\mathbf{x}_4=(3,1,0)\) in \(\mathbb{R}^3\). Keep only the nonzero normalized residuals.
First, \(\mathbf{r}_1=(1,0,0)\), so \(\|\mathbf{r}_1\|=1\) and \(\mathbf{q}_1=(1,0,0)\). At the second input, $$ \langle\mathbf{x}_2,\mathbf{q}_1\rangle=2, \qquad \mathbf{r}_2=(2,0,0)-2(1,0,0)=(0,0,0). $$ Do not divide by \(\|\mathbf{r}_2\|=0\). Keep the existing list \((\mathbf{q}_1)\) and continue. The third input has coefficient \(\langle\mathbf{x}_3,\mathbf{q}_1\rangle=0\), so \(\mathbf{r}_3=(0,1,0)\), with norm \(1\). Add \(\mathbf{q}_2=(0,1,0)\).
For the fourth input, the coefficients are \(\langle\mathbf{x}_4,\mathbf{q}_1\rangle=3\) and \(\langle\mathbf{x}_4,\mathbf{q}_2\rangle=1\). Hence $$ \mathbf{r}_4=(3,1,0)-3(1,0,0)-1(0,1,0)=(0,0,0). $$ Again, no new vector is added. The final orthonormal list is \(\mathbf{q}_1=(1,0,0)\), \(\mathbf{q}_2=(0,1,0)\).
Check: The second input is \(2\mathbf{x}_1\), and the fourth is \(3\mathbf{x}_1+\mathbf{x}_3\). Each zero residual therefore agrees with direct membership in the span of earlier inputs. The third input is not in the span of the first, which is why its residual is nonzero.
Worked Example: A Nonzero Residual Adds a Direction
Apply Gram–Schmidt to \(\mathbf{x}_1=(1,1,0)\), \(\mathbf{x}_2=(1,-1,0)\), and \(\mathbf{x}_3=(1,0,1)\) in \(\mathbb{R}^3\).
The first residual is \(\mathbf{r}_1=(1,1,0)\), with norm \(\sqrt{2}\), so \(\mathbf{q}_1=(1,1,0)/\sqrt{2}\). For the second input, \(\langle\mathbf{x}_2,\mathbf{q}_1\rangle=(1-1)/\sqrt{2}=0\). Thus \(\mathbf{r}_2=\mathbf{x}_2\), its norm is \(\sqrt{2}\), and \(\mathbf{q}_2=(1,-1,0)/\sqrt{2}\). These vectors are orthogonal because \((1-1)/2=0\).
For \(\mathbf{x}_3\), both projection coefficients equal \(1/\sqrt{2}\). Therefore $$ \begin{aligned} \mathbf{r}_3 &=(1,0,1)-\frac{1}{\sqrt{2}}\frac{(1,1,0)}{\sqrt{2}} -\frac{1}{\sqrt{2}}\frac{(1,-1,0)}{\sqrt{2}}\\ &=(1,0,1)-\left(\frac12,\frac12,0\right) -\left(\frac12,-\frac12,0\right)\\ &=(0,0,1). \end{aligned} $$ Its norm is \(1\), giving \(\mathbf{q}_3=(0,0,1)\). This is a genuine new direction, not a zero residual. As a check, \(\langle\mathbf{r}_3,\mathbf{q}_1\rangle=0\) and \(\langle\mathbf{r}_3,\mathbf{q}_2\rangle=0\), as required.
Checking a Suspicious Calculation
A residual is calculated by subtracting every projection onto the current orthonormal list. A nonzero answer does not by itself prove independence if the arithmetic may be wrong. Two checks are especially direct: verify that the residual is orthogonal to each existing \(\mathbf{q}_j\), and, if a dependence is suspected, verify the claimed linear combination in the original inputs.
Common mistake: an incorrect projection coefficient creates a false nonzero residual. In the first example, the correct coefficient of \(\mathbf{q}_2\) for \(\mathbf{x}_3=(1,1,2)\) is \(\langle\mathbf{x}_3,\mathbf{q}_2\rangle=3/\sqrt{6}\). If it is mistakenly calculated as \(2/\sqrt{6}\), the resulting subtraction gives $$ \left(1,1,2\right)-\left(\frac32,0,\frac32\right) -\frac{2}{\sqrt{6}}\mathbf{q}_2 = \left(-\frac16,\frac13,\frac16\right), $$ which is falsely nonzero. But this vector is not orthogonal to \(\mathbf{q}_2\): $$ \left\langle\left(-\frac16,\frac13,\frac16\right),\mathbf{q}_2\right\rangle =\frac{\frac16+\frac23+\frac16}{\sqrt{6}} =\frac{1}{\sqrt{6}}\ne0. $$ That failure exposes the arithmetic error. Recomputing the coefficient gives \(3/\sqrt{6}\), and the corrected residual is zero, as the direct relation \(\mathbf{x}_3=\mathbf{x}_1+\mathbf{x}_2\) also confirms.
There are two related cautions. First, a zero residual cannot be normalized: the expression \(\mathbf{r}_k/\|\mathbf{r}_k\|\) is undefined when \(\mathbf{r}_k=\mathbf{0}\). Second, a zero residual means the current input adds no new direction, not that the whole input list should be abandoned. Later inputs may still have nonzero residuals, as the second example demonstrates.
Check Your Understanding
For each question, use the residual formula and check any claimed dependence relation by substitution.
- If \(\mathbf{r}_k=\mathbf{0}\), what does this say about \(\mathbf{x}_k\) and the earlier inputs?
- For inputs \((1,0)\) and \((3,0)\) in \(\mathbb{R}^2\), compute the second residual after the first vector has been normalized. Should another orthonormal vector be added?
- Why is normalizing a zero residual invalid, and what should the algorithm do at that step?
- Suppose a computed residual is nonzero but has a nonzero inner product with an earlier \(\mathbf{q}_j\). What does this indicate you should check?
- Give a list of three vectors in \(\mathbb{R}^2\) for which the second residual is zero but the third is nonzero.
