# Why does the Gram-Schmidt procedure divide by 0 on a linearly dependent lists of vectors?

Let $v_1, \dots, v_m$ be a linearly dependent list of vectors.
If $v_1 \ne 0$, then there is some $v_j$ in the span of $v_1, \dots, v_{j-1}$
If we let j be the smallest integer with this property, and apply the gram-schmidt procedure to produce an orthonormal list $(e_1, \dots, e_{j-1})$ then $v_j$ is in the span of $(e_1, \dots, e_{j-1})$ and
$$v_j = \langle v_j, e_1\rangle e_1+ \dots + \langle v_j, e_{j-1}\rangle e_{j-1}$$
Why does this guarantee that length of $v_j$=0? I'm missing something about linear dependence that should probably be obvious sorry :\

-

The Gram-Schmidt process goes as follows: given $v_1,\ldots,v_n$, you define \begin{align*} u_1 &= v_1\\ e_1 &= \frac{1}{||u_1||}u_1;\\ u_2 &= v_2 - \langle v_2,e_1\rangle e_1;\\ e_2 &= \frac{1}{||u_2||}u_2;\\ &\vdots\\ u_{k+1} &= v_{k+1} - \left(\langle v_{k+1},e_1\rangle e_1 + \langle v_{k+1},e_2\rangle e_2 + \cdots + \langle v_{k+1},e_k\rangle e_k\right)\\ e_{k+1}&= \frac{1}{||u_{k+1}||}u_{k+1}\\ &\vdots \end{align*}

So when you construct $u_{j}$, you get $\mathbf{0}$, and when you try to construct $e_{j}$ you attempt to divide by $0$. It's not $v_j$ which has length $0$, it's $u_j$.

-
I see, thank you. – fdart17 Mar 29 '11 at 5:04
@Arturo - can you explain why does it follow that $u_j$ is 0? I understand that $v_j$ is in the span of its previous vectors, which means there is a linear combination of them which equals to $v_j$, but why is it a must that its this particular combination? – ihadanny Jan 22 at 14:29

It does not guarantee that. What it guarantees is that $v_j - \langle v_j, e_1\rangle e_1- \dots - \langle v_j, e_{j-1}\rangle e_{j-1} = 0$, which means that you cannot define $e_j$ by dividing this vector by its norm. Instead, you throw it away and move on to $v_{j+1}$.

E.g., consider the case $v_1\neq 0$ and $v_2=v_1$.

-
Thank you, this also helped with the simple example. – fdart17 Mar 29 '11 at 5:06
@Jonas - can you explain why does it follow that $v_j$ minus the projections of the others is 0? linear dependence means that there is a linear combination of the previous vectors which equals to $v_j$, but why is it a must that its this particular combination? – ihadanny Jan 22 at 14:33
@ihadanny: It is 0 because it is a vector in the span of the $e_i$s whose inner product with each $e_i$ is 0. – Jonas Meyer Jan 23 at 2:16
@Jonas - let me rephrase that to see if I understood correctly. $u_j$ is in the span of the $e_i$s. This means that we can write $u_j$ as a linear combination of those $e_i$s. A linear combination of *orthogonal vectors* is a sum of the inner product with each of them. But since we made sure that the inner product of $u_j$ with each of the $e_i$ would be 0, the entire sum would be 0. – ihadanny Jan 23 at 9:02