# Help to understand Gram-Schmidt Proof

This is from Axler's Linear Algebra Done Right 6.20 proof

I don't understand how does Axler get to equation 6.23. It seems to me that he simply add a vector $v_j$ such that $v_j$ is orthogonal to every vector in $\mathrm{span}(e_1,\:...\:e_{j-1})$ and becomes a new linearly independent spanning list ($e_1,\:...\:e_{j-1},v_j$)

therefore, $v_j=v_j-0*e_1 -.....-0*e_{j-1}$, because $v_{j}$ is orthogonal to $e_{i}$, then $\langle v_{j},e_{i} \rangle = 0$.

Thus, we have $v_{j}=v_{j-1} - \langle v_{j},e_{1} \rangle e_{1} -...- \langle v_{j},e_{j-1} \rangle e_{j-1}$

then normalize $v_{j}$ to $e_{j}$, so we get the equation 6.23

However, how do we know that we can always add an orthogonal vector to a spanning list? Axler doesn't prove that we can always add one more vector (linearly independent to the spanning list and orthogonal to every vector in that spanning list).

-
If you can, try to look this up in Hoffman's Linear Algebra. I think this proof is explained differently there. – Lessa121 Aug 4 '14 at 19:58
Hi @Hobbit6094! Here at StackExchange, we use MathJax, a subset of LaTeX, for mathematical notation. Please take your time to learn how to use it: this question, and many others, had to be edited to convert HTML formatting to MathJax. – Giulio Muscarello Aug 4 '14 at 22:27
To get started with MathJax, look up something like "latex mathematical formulas" on a search engine. To use MathJax on StackExchange sites, just type the LaTeX commands between dollar signs. – Giulio Muscarello Aug 4 '14 at 22:29

## 2 Answers

$v_j$ is the $j$th element of the original linearly independent set $\{v_1,\dots,v_m\}$. Also in regards to your comment, you don't know that $v_j$ is orthogonal to each $e_1,\dots,e_{j-1}$.

He is working inductively. He has assumed that for $j-1$ we can find $\{e_1,\dots,e_{j-1}\}$ such that span$\{e_1,\dots,e_{j-1}\}=$span$\{v_1,\dots,v_{j-1}\}$. Then he considers the set $\{v_1,\dots,v_j\}$. By induction we can find an orthonoromal set $\{e_1,\dots,e_{j-1}\}$ such that, as above, span$\{e_1,\dots,e_{j-1}\}=$span$\{v_1,\dots,v_{j-1}\}$. To complete the induction he throws in one more orthonormal vector into $\{e_1,\dots,e_{j-1}\}$ by taking the $j$th element of $\{v_1,\dots,v_m\}$ and forming $e_j$ as describe in your boxed 6.23.

The rest of the proof is showing why this vector is orthorgonal to each previous $e_i$ and that the set is linearly independent.

If you have an orthonormal linearly independent set $\{e_1,\dots,e_j\}$ with $j<\dim V$ then you can always throw in one more orthonormal vector. To see this, just extend $\{e_1,\dots,e_j\}$ to a basis for $V$ then preform Gram Scmidt on this set. Note that if $j=\dim V$, then you cannot throw in an orthonormal vector because then this new set would be linearly independent with size greater than $\dim V$.

-
he throws in one more orthonormal vector into $\{e_1,\dots,e_{j-1}\}$ by taking the $j$th element of $\{v_1,\dots,v_m\}$.----------can we always throw more orthogonal vector into a spanning list ? I mean there always exist an orthogonal vector like v<sub>j</sub> ? Is that possible for some spanning list that after we throw an extra vector in but this new vector can't be orthogonal to the other vectors in the list? – Hobbit6094 Aug 4 '14 at 20:25
I see what you are saying. The answer is yes, although only if the size of the orthogonal set is less than the dimension of the vector space! That is, if you have an orthogonal linearly independent set $\{e_1,\dots,e_j\}$ with $j<\dim V$, then you can always add another linearly independent orthonormal vector. If $j=\dim V$ then you cannot throw in an orthonormal vector as it cannot be linearly independent. – JonHerman Aug 4 '14 at 20:37
To see this, suppose that $\{e_1,\dots,e_j\}$ is an orthogonal set. Now add any linearly independent vector you want (which can always be done if $j<\dim V$). Call this added vector $w$. Now apply this Gram-Schmidt procedure to $\{e_1,\dots,e_j,w\}$. To turn this set into an orthogonal one. – JonHerman Aug 4 '14 at 20:38

$\newcommand{\norm}[1]{\|{#1}\|}\newcommand{\ip}[1]{\langle{#1}\rangle}$The key is to understanding Equation 6.23 is the following observation:

Let $S$ be a subspace of a finite-dimensional vector space $V$, and let $\{\xi_1,\dotsc,\xi_k\}$ be an orthonormal basis for $S$. Then for any $v \in V$, $$P_S v = \ip{v,\xi_1}\xi_1 + \cdots + \ip{v,\xi_k}\xi_k$$ is the orthogonal projection of $v$ onto $S$, whilst $$P_{S^\perp} v = v - P_S v = v - \ip{v,\xi_1}\xi_1 - \cdots - \ip{v,\xi_k}\xi_k$$ is the orthogonal projection of $v$ onto $S^\perp$.

Now, suppose, by induction, that you've constructed an orthonormal basis $\{e_1,\dotsc,e_{j-1}\}$ for $S_{j-1} := \operatorname{Span}\{v_1,\dotsc,v_{j-1}\}$. Then, in particular, $$v_j = P_{S_{j-1}} v + P_{S_{j-1}^\perp}$$ for $$P_{S_{j-1}} v_j = \ip{v_j,e_1}e_1 + \cdots + \ip{v_j,e_{j-1}}e_{j-1} \in S_{j-1} = \operatorname{Span}\{v_1,\dotsc,v_{j-1}\}\\ P_{S_{j-1}^\perp} v_j = v_j - \ip{v_j,e_1}e_1 - \cdots - \ip{v_j,e_{j-1}}e_{j-1} \in S_{j-1}^\perp = \operatorname{Span}\{v_1,\dotsc,v_{j-1}\}^\perp,$$ so that $\{e_1,\dotsc,e_{j-1},P_{S_{j-1}^\perp} v_j\}$ defines an orthogonal basis for $$S_j := \operatorname{Span}\{v_1,\dotsc,v_j\} = \operatorname{Span}\{e_1,\dotsc,e_{j-1},v_j\} = \operatorname{Span}\{e_1,\dotsc,e_{j-1},P_{S_{j-1}^\perp} v_j\};$$ to get an orthonormal basis for $S_j$, you simply normalise $P_{S_{j-1}^\perp} v_j$ to get $$e_j := \frac{1}{\norm{P_{S_{j-1}^\perp} v_j}} P_{S_{j-1}^\perp} v_j = \frac{v_j - \ip{v_j,e_1}e_1 - \cdots - \ip{v_j,e_{j-1}}e_{j-1}}{\norm{v_j - \ip{v_j,e_1}e_1 - \cdots - \ip{v_j,e_{j-1}}e_{j-1}}},$$ which is precisely Equation 6.23. If you're worried about linear independence of $\{e_1,\dotsc,e_j\}$, the point is that it is, by construction, a spanning set with $j$ elements for the $j$-dimensional subspace $S_j$, which is guaranteed to be $j$-dimensional precisely because $\{v_1,\dotsc,v_m\}$ was assumed to be linearly independent.

-
Oh, sorry about that, I'm just used to the convention where inner products are conjugate linear in the first variable instead of the second. I can fix that for you. – Branimir Ćaćić Aug 4 '14 at 20:43
thanks so much, – Hobbit6094 Aug 4 '14 at 20:44