# A Proof for Gram-Schmidt Procedure in Linear Algebra Done Right

I am reading the following proof in the book Linear Algebra Done Right. But I don't understand what induction on $j$ means here! I suppose the author means induction on $m$. However, all the proof is talking about $j$ and I don't think this is a typo!

Does induction on $j$ makes sense, here? I mean what is the variable of induction? I am confused!

My Thought

What is the index $j$ that the author is talking about in the proof? Is it the same as mentioned in the theorem? If the author is assuming that the theorem is true for $v_1,...,v_k, 1 \le k \le j$ and then wants to prove it for $v_1,...,v_j,v_{j+1}$ while $j$ remain in $1 \le j \le m-1$, then the proof suffers from abuse of notation so badly.

Induction on $j$ seems meaningless to me! Because theorem is an expression which depends on $m$ (the length of the list of linearly independent vectors) not $j$! In other words, we want to see that Theorem is true for all $m \ge 2$ or not!

$1$- If I was going to prove the theorem by myself then I would change the last line of theorem by

$$\text{span}(v_1,...,v_m)=\text{span}(e_1,...,e_m)$$

and then do an induction on $m$.

$2$- I also think that we can prove the theorem by induction on $m$ in the original form. It is stronger than the case $1$ above?

• There's no typo. In this context, $m$ is a parameter, and the construction of an orthonormal basis from s system of linearly independent vectors is a (finite) recursive procedure. – Bernard Aug 16 '16 at 13:26
• The induction is on $j$ where $1\le j\le m$. As you rightly observe though, the the condition of finiteness is unnecessary, so that, for example, this procedure applies to Hilbert Spaces also. – Matematleta Aug 16 '16 at 13:34
• @Bernard: So the induction is on $j$ or $m$? – H. R. Aug 16 '16 at 13:40
• It's on $j$ indeed. – Bernard Aug 16 '16 at 13:41
• I see. To prove the theorem, you have to prove that for all $j$, the span of $(v_1,\dots,v_j)$ is the same as the span of $(e_1, \dots, e_j)$. This is stronger than your conclusion. – Bernard Aug 16 '16 at 14:30

As pointed out in the comments, the proof in the book is correct; in fact, the statement is exactly what we wanted: $\text{span}(v_1)=\text{span}(e_1)$, $\text{span}(v_1,v_2)=\text{span}(e_1,e_2)$, $\text{span}(v_1,v_2,v_3)=\text{span}(e_1,e_2,e_3)$, and go on in general for an infinite list: $\text{span}(v_1,v_2,\ldots,v_n,\ldots)=\text{span}(e_1,e_2,e_3,\ldots,e_n,\ldots)$. Note we need this for the proof of $6.37$ on page 186 of the book:

$6.37$ Upper-triangular matrix with respect to orthonormal basis

Suppose $T\in\mathcal{L}(V)$. If $T$ has an upper-triangular matrix with respect to some basis of V, then $T$ has an upper-triangular matrix with respect to some orthonormal basis of $V$.

Proof

……Because

$\text{span}(e_1,\ldots,e_j)=\text{span}(v_1,\ldots,v_j)$

for each $j$ (see $6.31$), we conclude that $\text{span}(e_1,\ldots,e_j)$ is invariant under $T$ for each $j=1,\ldots,n$. Thus, by $5.26$, $T$ has an upper triangular matrix with respect to the orthonormal basis $e_1,\ldots,e_n$.

The proof of $6.31$ has no problem. The following visualization should clarify the confusion:

Or just write out the first few steps explicitly:

$j=1$:

$\text{span}(v_1)=\text{span}(e_1)$ is simple;

$j=2$:

We have $v_2\notin\text{span}(v_1)$.

Let $1\leq k<2$, so $k=1$.

$\displaystyle\langle e_2,e_1\rangle=\frac{\langle v_2, e_1\rangle-\langle v_2,e_1\rangle}{\|v_2-\langle v_2,e_1\rangle e_1\|}=0$, so $e_1,e_2$ are orthonormal. From the picture above, it is clear that $\text{span}(v_1,v_2)=\text{span}(e_1,e_2)$.

$j=3$:

We have $v_3\notin\text{span}(v_1,v_2)$.

$\displaystyle e_3=\frac{v_3-\langle v_3, e_1\rangle e_1-\langle v_3,e_2\rangle e_2}{\|v_3-\langle v_3, e_1\rangle e_1-\langle v_3,e_2\rangle e_2\|}$

Let $1\leq k<3$, so $k=1,2$.

$\displaystyle\langle e_3,e_1\rangle=\frac{\langle v_3,e_1\rangle-\langle v_3,e_1\rangle-\langle v_3,e_2\rangle\cdot0}{\|\cdots\|}=0$

$\displaystyle\langle e_3,e_2\rangle=\frac{\langle v_3,e_2\rangle-\langle v_3,e_1\rangle\cdot0-\langle v_3,e_2\rangle}{\|\cdots\|}=0$

So $e_1,e_2,e_3$ are orthonormal.

$\vdots$

When things go too abstract in this book, it is often helpful to draw some pictures, play with $2\times 2$ matrices, or resort to other less "theoretical" books. By the way, I like this book very much.

• (+1) Thanks for the attention. I know what Gram-Schmidt is about and what it means but I have problem with the induction argument in the proof. Also, I have seen many proofs for Gram-Schmidt but this really is the worst as it confuses me so badly! :) Also, no motivation is given for the formula! This is one of the worst proofs that Axler has written in his nice book! :) – H. R. Aug 17 '16 at 13:02
• Also in $(6.32)$, $j$ should be replaced with $k$ and $m$ with $j$. I mean it should be for $1 \le k \le j$ we have verified that $\text{span}(v_1,...,v_{k-1})=\text{span}(e_1,...,e_{k-1})$ – H. R. Aug 17 '16 at 13:28
• @H.R. I don't think so….it is most straightforward to think the case for infinite list of vectors $(v_1,v_2,\ldots)$, so please drop the $m$, or let $m=\infty$! The $k$ is also of limited use: it is only a convenient name for the previous vectors $e_1, e_2,\ldots$. – Fei Li Aug 17 '16 at 14:57
• @H.R. so the proof really goes like: suppose the theorem holds for $1,2,\ldots,j-1$, then we prove it for $j$. The proof is indeed a little terse with lots of $m,j,k$ cracked in; we should never care them too much. A picture or a few more steps is helpful, but the book is for extreme beauty, as we can seen elsewhere. – Fei Li Aug 17 '16 at 15:04
• I did the review. Welcome to have a look. – Fei Li Aug 19 '16 at 14:43