# Proving replacement theorem?

I want to see if I am understanding the proof of the replacement theorem correctly.

Let $V$ be a vector space that is spanned by a set $G$ containing $n$ vectors. Let $L \subseteq V$ be a linearly independent subset containing $m$ vectors. Then $m\leq n$ and there exists a subset H of G containing exactly $n-m$ vectors s.t. $L \cup H$ generates $V$.

The proof in the book says to start with $m=0$. In that case $L=\varnothing$, the empty set.

Let's assume this theorem is true for some integer $m \geq 0$.

Let $L = \{v_j\}_{j=1}^{m+1}$ and define it as a linearly independent subset of $V$ consisting of $m+1$ vectors.

Since any subset of a linearly independent set is linearly independent as well ($S_1 \subseteq S_2 \subseteq V$), then $\{v_j\}_{j=1}^m$ is linearly independent also.

It then says to use the induction hypothesis to say that $m \geq n$. Well, ok, but that seems sort of pulled out of nowhere to me. The next step is to say that there is therefore another subset, $\{u_k\}_{k=1}^{n-m}$ of G such that $\{v_j\}_{j=1}^m \cup \{u_k\}_{k=1}^{n-m}$ spans $V$.

That being the case there are scalars $(a_j)_{j=1}^m$ and $(b_k)_{k=1}^{n-m}$ which you can multiply by the vectors $v_j$ and $u_k$. You can then add the two sets of vectors, yielding $$\sum_{j=1}^m a_j v_j + \sum_{k=1}^{n-m} b_k u_k = v_{m+1}$$

At this point I am not sure I understand things. Because we are assuming $n-m>0$ -- otherwise $v_{m+1}$ is linearly dependent. But then it says not only is $n>m$ but $n>m+1$, and that is where I am losing the plot to get to the next step.

• In the original Friedberg's text: "apply the induction hypothesis to say that $m \leq n$. Which makes sense, unlike your statement. Maybe a typo, but introduces a lot of confusion to an already tricky proof. – David Cabrera Sep 6 '16 at 19:46

I'm assuming you're working through the proof in Friedberg et al. as its very similar. I'd really encourage you to double check what you've written because there are many typos above and probably isn't coherent enough for someone without a copy of the text.

The proof in the book says to start with m=0. In that case L=$\varnothing$, the empty set.

Okay, and I hope you realize that this also proves the inequality $m \leq n$ for the base case.

Let's assume this theorem is true for some integer m $\ge$ 0.

Let L = ${v_1, v_2, .... v_m+1}$ and define it as a linearly independent subset of V consisting of m+1 vectors.

So we're going to use induction on $m$ to prove the theorem. Also, it should be $L = \{v_1, \ldots, v_{m+1} \}$.

Since any subset of a linearly independent set is linearly independent as well ($S_1 \subseteq S_2 \subseteq V$), then {$v_1, v_2, .... v_m$} is linearly independent also.

That's correct. I'll call this set $L'$.

It then says to use the induction hypothesis to say that m$\le$n. Well, ok, but that seems sort of pulled out of nowhere to me. The next step is to say that there is therefore another subset, {$u_1, u_2, .... un_m$} of G s.t. {$v_1, v_2, .... v_m$} $\cup$ {$u_1, u_2, .... u_{n-m}$} generates V.

It isn't pulled out of nowhere because it follows from the induction hypothesis. As we have assumed it for some $m \geq 0$, we can apply the theorem to $\{v_1, \ldots, v_m\}$ which gives us the inequality $m \leq n$ and the set $H' = \{u_1, \ldots, u_{n-m}\} \subset G$ such that $L' \cup H'$ generates $V$.

That being the case there are scalars $a_1, a_2, .... a_m$ and $b_1, b_2, .... b_{n-m}$ which you can multiply by the vectors $v_i$ and $u_i$. You can then add th two sets of vectors, yielding $$a_1 v_1 + a_2v_2 + ... + a_mv_m + b_1u_1 + b_2u_2 + ... b_{n-m}u_{n-m} = v_{m+1} \tag{*}$$

We can do this as $L' \cup H'$ generates $V$.

At this point I am not sure I understand things. Because we are assuming n-m>0 -- otherwise $v_{m+1}$ is linearly dependent. But then it says not only is n>m but n>m+1, and that is where I am losing the plot to get to the next step.

What follows is this:

Note that $n - m > 0$, lest $v_{m +1}$ is a linear combination of $v_1, \ldots, v_m$ which by Theorem 1.7 (pg 39) contradicts the assumption that $L$ is linearly independent.

Do you understand why it must be $n - m >0$? Well if we had $n - m = 0$ then $H' = \emptyset$ and this would mean that $(\text{*})$ is only composed of vectors of $L'$ and therefore, $L' \cup \{v_{m+1}\} = L$ would be linearly dependent as $v_{m+1} \in \operatorname{span}(L')$, but that would be a contradiction.

Hence $n > m$; that is, $n \geq m +1$.

Why? Because another way of expressing $n > m$, as $n$ and $m$ are integers, is $n \geq m +1$. That's all there is to it.

Moreover, some $b_i$, say $b_1$ is nonzero, for otherwise we obtain the same contradiction. Solving $(\text{*})$ for $u_1$ gives

$$u_1 = (-b_1^{-1}a_1)v_1 + \cdots + (-b_1^{-1}am)v_m + (-b_1)v_{m + 1} + (-b_1^{-1}b_2)u_2 + \cdots + (-b_1^{-1}b_{n-m})u_{n-m}$$

Of course. If $b_i$ were all zero in $(\text{*})$ it would again only be composed of vectors of $L'$ and we know that that can't be the case for the same reason as above.

Let $H = \{u_2, \ldots, u_{n-m}\}$. Then $u_1 \in \operatorname{span}(L \cup H)$ and because $v_1, \ldots, v_m,u_2,\ldots,u_{n-m}$ are clearly in $\operatorname{span}(L \cup H)$, it follows that

$$L' \cup H' = \{v_1, \ldots, v_m, u_1, \ldots, u_{n-m}\} \subseteq \operatorname{span}(L \cup H).$$

This should be clear.

Because $L' \cup H'$ generates $V$, Theorem 1.5 (pg 30) implies that $\operatorname{span}(L \cup H)$ generators $V$.

To see why you can apply Theorem 1.5 you must remember that if $S \subseteq V$ then $\operatorname{span}(S)$ is a subspace of $V$ and therefore, by Theorem 1.5, if $W \subseteq \operatorname{span}(S)$ then $\operatorname{span}(W) \subseteq \operatorname{span}(S)$. So we have that $V = \operatorname{span}(L' \cup H') \subseteq \operatorname{span}(L \cup H)$ and since obviously, $\operatorname{span}(L \cup H) \subseteq V$ we have $\operatorname{span}(L \cup H) = V$.

Since $H$ is a subset of $G$ which contains $(n - m) - 1 = n - (m +1)$ vectors the theorem is true for $m + 1$. This completes the induction.

This should be clear.

Hope this helps!

• that does help, thanks. I am trying to work these through because I am probably still shaky on some definitions. It was just that sometimes I found bits of the proof in he text hard to follow. (I think I like "Linear Algebra Done Right" a bit better). – Jesse Jun 17 '13 at 11:29
• also i think i got hung up on the idea that n>m+1 as opposed to just n>m. – Jesse Jun 17 '13 at 11:41
• @Jesse That happens to everyone. Whenever you read a proof always try to justify everything it says by making sure how something follows from so and so theorem. I'm not a fan of Linear Algebra Done Right because it does everything over $\mathbb{R}$ and $\mathbb{C}$ while Friedberg over arbitrary fields. Also, Axler avoids determinants which I'm not a fan of. But if you can learn something somewhere else go for it, but I'd insist on trying to understand a proof in Friedberg always because its a really good text. – user70962 Jun 17 '13 at 12:36
• To make sure you've understood the Replacement Theorem try proving the Corollaries that follow. They aren't difficult to prove and its good practice on how to apply the theorem. There are also good problems in this section which you should definitely attempt. – user70962 Jun 17 '13 at 12:38