Help to understand Gram-Schmidt Proof

Question

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

Answer 1

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

Answer 2

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