Discover Linear Algebra: A first course in linear algebra

Suppose $S$ is a set of vectors containing the zero vector. We’ll break into cases depending on what else is in $S$ besides $\mathbf{0}\text{.}$

Suppose $S$ is a collection of vectors in a vector space, and $S^{\prime }$ is a linearly dependent subcollection of $S\text{.}$ Then some vector in $S^{\prime }$ can be expressed as a linear combination of other vectors in $S^{\prime }\text{.}$ But because $S^{\prime }$ is a subcollection of $S\text{,}$ all these vectors in $S^{\prime }$ are also vectors in $S\text{.}$ So we can also say that some vector in $S$ can be expressed as a linear combination of other vectors in $S\text{,}$ making $S$ a linearly dependent set.

Suppose $S$ is a linearly independent collection of vectors in a vector space. Then no subcollection of $S$ can be linearly dependent, because if $S$ contained such a linearly dependent subcollection then Statement 1 of this proposition would imply that $S$ itself is linearly dependent, which we assume it is not. So every subcollection of $S$ must be linearly independent.

Using Statement 2 of Proposition 16.5.6, we just need to show that every vector in $S$ can be expressed as a linear combination of vectors in $S^{\prime }\text{,}$ and vice versa. However, $S$ and $S^{\prime }$ are the same set of vectors except that $S$ contains $\mathbf{w}$ while $S^{\prime }$ does not. So from the trivial expression $\mathbf{v}=1\mathbf{v}\text{,}$ we immediately have that every vector $\mathbf{v}$ in $S$ (other than $\mathbf{w}$) is a linear combination of itself (which is a vector in $S^{\prime }$), and vice versa. And we have also assumed that $\mathbf{w}$ is expressible as a linear combination of vectors in $S$ besides itself. Since the vectors in such a linear combination are also in $S^{\prime }\text{,}$ we know that $\mathbf{w}$ is expressible as a linear combination of vectors in $S^{\prime }\text{.}$

If $S$ is already linearly independent, then we have our desired linearly independent spanning set. Otherwise, there is some vector $\mathbf{w}$ in $S$ that is a linear combination of the other vectors in $S\text{.}$ If we set $S^{\prime }$ to be the subcollection of $S$ consisting of every vector except $\mathbf{w}\text{,}$ then from Lemma 17.5.4 we know that $S^{\prime }$ will remain a spanning set for the vector space. If $S^{\prime }$ is linearly independent, then we have our desired linearly independent spanning set. Otherwise, we can continue removing linearly dependent vectors in this way until we end up with a linearly independent spanning set. And since we assumed there were a finite number of vectors in $S\text{,}$ this one-by-one removal process must indeed come to an end at some point.

Write $S^{\prime }$ for the set of vectors containing both the vector $\mathbf{v}$ and every vector in $S\text{.}$ The set $S^{\prime }$ will be linearly independent if none of its vectors can be expressed as a linear combination of other vectors in the set.

So suppose $\mathbf{w}$ is a vector in $S^{\prime }\text{.}$ There are two cases to consider.

Suppose $S$ is a set of $n$ vectors in a vector space so that $S$ is a spanning set for the space. By Proposition 17.5.5, there are vectors ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_{n^{\prime }}$ in $S$ that are both linearly independent and also a spanning set for the vectors space. Since this is a subcollection of $S\text{,}$ we must have $n^{\prime }\le n\text{.}$ We’ll refer to this subcollection of $S$ as $S^{\prime }\text{.}$