Gram-Schmidt method to identify linearly dependent vectors

Question

A method to orthogonalize a set of vectors (vectors of unit length that are mutually orthogonal) is the Gram-Schmidt process: http://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process

Note that the the nested for loops imply that the difference is between vector $v_i$ and vectors $\{v_1, \dots, v_{i-1}\}$.

However, I wonder about the behavior of the process in case the set of input vectors is linearly dependent. Namely, suppose the process is initialized on vectors $\{v_1, v_2, v_3, v_4, v_5\}$. In case $v_4$ can be expressed as a linear combination of $\{v_1, v_2, v_3\}$, the process will set $v_4=0_n$ (i.e, zero vector).

Now suppose that $v_2$ can be expressed as a linear combination of $\{v_3, v_4, v_5\}$. Would such ordering of vectors imply that the Gram-Schmidt process will fail to set $v_2=0_n$ (fail to report linear dependence)? If so, what is the common way to ensure that Gram-Schmidt would yield orthonormal vectors and report linearly dependent ones?

Answer 1

If $v_2$ can be expressed as a linear combination of $\{ v_3, v_4, v_5 \}$, but not of a subset of these vectors, then, e.g., $v_5$ is in the linear span of $\{ v_2, v_3, v_4 \}$. So your algorithm would likely map $v_5$ onto $0$.

Typically, if you apply the Gram-Schmidt proecess to the sequence of $v_i$, $1 \leq i \leq L$, a vector $v_k$ is mapped onto $0$ if it is in linear span of the $v_1, \dots, v_{k-1}$, in which case you probably drop it from further considerations. Eventually, your algorithm will produce an orthonormal basis $\{ w_1, \dots, w_l \}$ of the linear span of $\{ v_1, \dots, v_L \}$, $l \leq L$

Of course, this only holds up to rounding errors. Furthermore, you would probably use the stabilized Gram-Schmidt process. An interesting follow-up question is when a vector should be regarded as numerically $0$.

Answer 2

While it doesn't answer your explict question, I offer the following important remark that might answer the intentions behind the question.

The anomalies of the Gram-Scmidt process in case of dependence are avoided if one computes the orthogonalization instead by the standard Householder $QR$ factorization (or in the sparse case the Givens variant). The latter is also much more stable and hence usually the method of choice. Dependence is then simply reflected by one or more zero (or in finite precision arithmetic) tiny diagonal entry in $R$. Column pivoting helps by moving these tiny entries towards the bottom of $R$.