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?

  • $\begingroup$ 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)$. $\endgroup$ – user70962 May 17 '13 at 11:07

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


($\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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.