# Help Understanding Proof of Replacement Theorem?

Sorry if this is a trivial question.

The book is Linear Algebra Done Right by Axler, page 25-26.

Theorem: In a finite-dimensional vector space, the length of every linearly independent list of vectors is less than or equal to the length of every spanning list of vectors.

Proof: Suppose that $(u_1 ,\ldots, u_m)$ is linearly independent in $V$ and that $(w_1,\ldots ,w_n)$ spans V. We need to prove that $m \leq n$. We do so through the multistep process described below; note that in each step we add one of the $u$'s and remove one of the $w$'s.

Step 1: The list $(w_1,\ldots, w_n)$ spans $V$, and thus adjoining any vector to it produces a linearly dependent list. In particular, the list $(u_1,w_1, \ldots,w_n)$ is linearly dependent.

Question: Why is $(u_1,w_1, \ldots,w_n)$ is linearly dependent?

• Just a small comment: I don't really like the use of the word "produces" in Step 1 as $\{w_1, \ldots, w_n\}$ could very well be linearly dependent to start with. It just gives me the impression that $\{w_1, \ldots, w_n\}$ is linearly independent which doesn't have to be the case. In general though, if $S$ is linearly independent and $v \in V$ and $v \notin S$ then $S \cup \{v\}$ is linearly dependent if and only if $v \in$ span$(S)$. – user70962 May 17 '13 at 11:07

## 4 Answers

Since $\{w_1,\ldots,w_n\}$ spans $V$, and $u_1\in V$, there exist $a_i$ such that $u_1=a_1w_1+\cdots+a_nw_n$. So $(-1)u_1+a_1w_1+\cdots+a_nw_n=0$ and therefore the adjoined set is linearly dependent.

$\{w_1,...,w_n\}\,$ spans $\,V\,\Longrightarrow\,\, \forall u_i\in V\,\,\text{we can write }\,\,u_1=a_1w_1+...+a_nw_n\,\,,\,a_i\,$ scalars in the definition field , so$$a_1w_1+...a_nw_n+(-1)u_1=0$$and not all the scalars are zero (since at least $\,-1\neq 0\,$) and thus $\{u_1,w_i,...,w_n\}\,$ linearly dependent.

If $(w_1, ..., w_n)$ spans $V$, then $u_1\in V$ can be written as a linear combination of the $w_i$, so the list $(u_1, w_1,...,w_n)$ is linearly dependent.

Here is a proof of the result I mention in the comment I made above which might be helpful to someone who comes across this question.

Let $V$ be a vector space over the field $F$. If $S \subset V$ is linearly independent and $v \in V$ and $v \notin S$ then $S \cup \{v\}$ is linearly dependent if and only if $v \in$ span$(S)$.

Proof:

($\Rightarrow$) If $S \cup \{v\}$ is linearly dependent then there exists finitely many distinct vectors $u_1, \ldots, u_n \in S \cup \{v\}$ and scalars, not all zero, $a_1, \ldots, a_n \in F$ such that

$$a_1u_1 + \dots + a_nu_n = 0.$$

Now one of the $u_i$'s must be equal to $v$, as otherwise we would have a case of linear dependence for $S$, so after re-ordering let $u_1 = v$ and we have

$$a_1v + a_2u_2 + \dots + a_nu_n = 0$$

And solving for $v$:

$$v = (-a_1^{-1}a_2)u_2 + \dots + (-a_1^{-1}a_n)u_n.$$

As $u_2, \ldots, u_n \in S$ we have $v \in$ span$(S)$.

($\Leftarrow$) If $v \in$ span$(S)$ then we can write, for $u_1,\ldots,u_n \in S$ and $a_1,\ldots, a_n \in F$,

$$v = a_1u_1 + \dots + a_nu_n$$

As $v \notin S$ we have,

$$a_1u_1 + \dots + a_nu_n + (-1)v = 0.$$

Therefore, $S \cup \{v\}$ is linearly dependent. $\Box$

Hope this helps someone!