# Proof Concerning Linear Independence And Maximal Subsets

Serge Lang's Linear Algebra has, in chapter 1, a proof which seems rather long-winded. He wants to prove the following theorem:

Theorem 3.1. let V be a vector space over the field K. Let $\{v_1,\ldots , v_m\}$ be a basis of V over K. Let $w_1,\ldots,w_n$ be elements of V, and assume that $n>m$. Then $w_1,\ldots,w_n$ are linearly dependent.

He goes on to prove this using induction applied to linear combinations of $\{v_1,\ldots , v_m\}$ equal to some $w_i$. That is: $$w_i = a_1v_1 + \cdots +a_mv_m$$

He's aiming to replace every $v_i$ with $w_i$, thus showing that every $w_j$ with $j>i$ is a linear combination of the $w_i$'s, and therefore that $w_1,\ldots,w_n$ are linearly dependent.

However, earlier in chapter 1 he introduced the term maximal subset:

Let $\{v_1,\ldots , v_n\}$ be a set of elements of a vector space V. Let $r$ be a positive integer such that $r \leqq n$. We shall say that $\{v_1,\ldots , v_r\}$ is a maximal subset of linearly independent elements if $v_1,\ldots,v_r$ are linearly independent, and if in addition, given any $v_i$ with $i > r$, the elements $v_1,\ldots,v_r,v_i$ are linearly dependent.

He then relates this to a theorem about bases:

Theorem 2.2. Let $\{v_1,\ldots,v_n\}$ be a set of generators of a vector space V. Let $\{v_1,\ldots,v_r\}$ be a maximal subset of linearly independent elements. Then $\{v_1,\ldots,v_r\}$ is a basis of V.

Now, I was wondering whether you could prove Theorem 3.1 using Theorem 2.2? To repeat Theorem 3.1 once more:

Theorem 3.1. let V be a vector space over the field K. Let $\{v_1,\ldots , v_m\}$ be a basis of V over K. Let $w_1,\ldots,w_n$ be elements of V, and assume that $n>m$. Then $w_1,\ldots,w_n$ are linearly dependent.

It seems to me like you could simply do the following:

It is given that $\{v_1,\ldots , v_m\}$ is a basis of $V$, so $\{v_1,\ldots , v_m\}$ must be the maximal subset of linearly independent elements of $V$ (I "reversed" Theorem 2.2 to conclude this). Then, according to the definition of a maximal subset, any elements $w_1,\ldots,w_n$ with $n>m$ are linearly dependent. Therefore, $w_1,\ldots,w_n$ must be linearly dependent.

Is my "reversal" of Theorem 2.2 valid - and more importantly, is my proof correct? If it is, it's shorter and simpler than Lang's by a long shot.

## 1 Answer

Unfortunately the reversal is not valid: $p\rightarrow q$ is not the same as $q\rightarrow p$ where $p$ and $q$ are statements and $\rightarrow$ indicates implication. For instance take the statement "If $n=1$, then $n$ is an integer," this true statement certainly does not let us conclude the converse: "If $n$ is an integer, then $n=1$."

However, it is worth noting that in your case the reversal is a correct statement - you just haven't proved it yet (in fact, this proof is basically what Theorem 3.1 is doing).

• Ah yes, I see now - thank you! My reversal was essentially using the result to prove the result. Commented Jun 28, 2014 at 18:02