# Gram-Schmidt method to identify linearly dependent vectors

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?

-

## 2 Answers

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$.

-

So, regardless of the ordering, the GS process will set one of the vectors to $0_n$?  What does it mean "if $v_2$ can be expressed as a linear combination of $\{2_3, v_4, v_5\}$", then "$v_5$ is in the linear span of $\{v_2, v_3, v_4\}$? This means that $v_5$ is a linear combination of $\{v_2, v_3, v_4\}$? Your second paragraph repeats the statement. What if, e.g., $v_2$ is in the linear span of $\{v_3, v_4, v_5\}$? – usero Sep 13 '12 at 14:50
Yes, the GS process will return a 0 0-vector, up to rounding errors of course. You should know that being a linear combination of a set of vectors is by definition the same as being in their span. As the second paragraph says, if v 2 ∈span{v 3 ,v 4 ,v 5 } v_2 \in \operatorname{span}\{v_3,v_4,v_5\}, then one of the vectors {v 3 ,v 4 ,v 5 } \{v_3,v_4,v_5\} will be processed as the 0 0-vector. – Martin Sep 13 '12 at 15:27
Thanks. The ambiguity was caused by yours "expressed as a linear combination" followed by "is in the linear span", both within the same sentence (and yet, they are the same). – usero Sep 13 '12 at 15:37

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$.

-

Gram-Schmidt is one algorithm for computing $QR$ factorizations. You seem to be referring specifically to Householder (preferred in practice because orthogonality is more stable), especially the "rank-revealing" versions. – Jed Brown Sep 14 '12 at 14:10
@JedBrown: Yes, Householder or Givens. I updated my answer accordingly. – Arnold Neumaier Sep 14 '12 at 15:18
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 37, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9275040626525879, "perplexity_flag": "head"}