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!
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?
linear-algebra induction
H. R.
H. R.H. R.
$\begingroup$ 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. $\endgroup$ – Bernard Aug 16 '16 at 13:26
$\begingroup$ 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. $\endgroup$ – Matematleta Aug 16 '16 at 13:34
$\begingroup$ @Bernard: So the induction is on $j$ or $m$? $\endgroup$ – H. R. Aug 16 '16 at 13:40
$\begingroup$ It's on $j$ indeed. $\endgroup$ – Bernard Aug 16 '16 at 13:41
$\begingroup$ 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. $\endgroup$ – 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$.
$\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;
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)$.
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.
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.
Fei LiFei Li
$\begingroup$ (+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! :) $\endgroup$ – H. R. Aug 17 '16 at 13:02
$\begingroup$ 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})$ $\endgroup$ – H. R. Aug 17 '16 at 13:28
$\begingroup$ @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$. $\endgroup$ – Fei Li Aug 17 '16 at 14:57
$\begingroup$ @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. $\endgroup$ – Fei Li Aug 17 '16 at 15:04
$\begingroup$ I did the review. Welcome to have a look. $\endgroup$ – Fei Li Aug 19 '16 at 14:43
Not the answer you're looking for? Browse other questions tagged linear-algebra induction or ask your own question.
Is "Linear Algebra Done Right 3rd edition" good for a beginner?
Proof of Gram-Schmidt process using strong induction
Proper subset of span of only one vector
Problem with the proof for the Gram-Schmidt orthonormalisation-process
Extension to the complex numbers for ex. 12 in ch. 6 of Axler's "Linear Algebra Done Right"
Help me understand my linear algebra book
Prove the following linear algebra theorem
$w$ is in the span
The Redundancy of applying the Gram-Schmidt Procedure on an orthogonal subset of $V$.
Prove span is the smallest containing subspace
Linear Dependence lemma - an unclear moment from the proof
Proof of Gram-Schmidt for countable sets