The algorithm for modified Gram-Schmidt (it does the same thing, but is supposed to be better for computers due to rounding) is:
- For k=1,...,m
set $\tilde x_k=k_k$
Set $\tilde x_1=\tilde x_1/\|x_1\|$
For k=2,...,m
{
for j=k,...,m
{
set $\tilde x_j=\tilde x_j-\langle \tilde x_{k-1}, \tilde x_j\rangle\tilde x_{k-1}$
}
set $\tilde x_k=\tilde x_k/\|\tilde x_k\|$
}
I thought it'd be instructive to see what happens for m=3:
Set $$\tilde x_1=\frac{x_1} {\|x_1\|}$$
Set $$\tilde x_2=x_2-\langle \tilde x_1,x_2\rangle\tilde x_1$$
Set $$\tilde x_3=x_3-\langle \tilde x_1,x_3\rangle\tilde x_1$$
Set $$\tilde x_2=\frac{x_2-\langle \tilde x_1,x_2\rangle\tilde x_1}{\|x_2-\langle \tilde x_1,x_2\rangle\tilde x_1\|}$$
Set $$\begin{split}\tilde x_3 &= x_3-\langle \tilde x_1,x_3\rangle\tilde x_1 - \langle\frac{x_2-\langle \tilde x_1,x_2\rangle\tilde x_1}{\|x_2-\langle \tilde x_1,x_2\rangle\tilde x_1\|}, x_3-\langle \tilde x_1,x_3\rangle\tilde x_1\rangle \frac{x_2-\langle \tilde x_1,x_2\rangle\tilde x_1}{\|x_2-\langle \tilde x_1,x_2\rangle\tilde x_1\|}\\ &=x_3-\langle \tilde x_1,x_3\rangle\tilde x_1 - \langle \tilde x_2, x_3-\langle \tilde x_1,x_3\rangle\tilde x_1\rangle \tilde x_2\\ &=x_3-\langle \tilde x_1,x_3\rangle\tilde x_1 - \langle \tilde x_2, x_3\rangle\tilde x_2\end{split}$$
Set
$$\tilde x_3 = \frac{x_3-\langle \tilde x_1,x_3\rangle\tilde x_1 - \langle \tilde x_2, x_3\rangle\tilde x_2}{\|x_3-\langle \tilde x_1,x_3\rangle\tilde x_1 - \langle \tilde x_2, x_3\rangle\tilde x_2\|}$$
Show that if the initial set of vectors are linearly independent, all residuals in the algorithm are nonzero. For $k\ge 2$, all that is required is to show that $\tilde x_k-\langle \tilde x_{k-1},\tilde x_k\rangle \tilde x_{k-1}\ne 0$ if $\tilde x_k$ and $\tilde x_{k-1}$ are linearly independent. Why?
It sounds like it's saying to take the difference between $\tilde x_k$ and the projection of the previous vector $\tilde x_{k-1}$ onto $\tilde x_k$. Since they are orthogonal, the projection would be the 0 vector. So we would be left with $\tilde x_k$. I'm not sure how this would show that the residuals are nonzero if the initial set of vectors is linearly independent.