Steinitz exchange lemma

Question

How can I show this?

if $b_{1}, ..., b_{n+1}$ are linears combinations of $a_{1}, ..., a_{n}$ then $b_{1}, ..., b_{n+1}$ are linearly dependents.

In my textbook they call it Steinitz lemma. I wonder if is it equivalent this?

http://en.wikipedia.org/wiki/Steinitz_exchange_lemma

Answer 1

First observe that $$ \dim \;\mbox{span}\{a_1,\ldots,a_n\}\leq n $$ as the dimension of a vector space is the minimal number of elements in a generating family. Now by assumption, the $b_j$'s belong to the span of the $a_j$'s. So $$ \mbox{span}\{b_1,\ldots,b_{n+1}\}\subseteq \mbox{span}\{a_1,\ldots,a_n\}. $$ Hence $$ \dim\;\mbox{span}\{b_1,\ldots,b_{n+1}\}\leq n. $$ So the $b_j$'s are not linearly independent, for otherwise they would span an $n+1$ dimensional subspace.

Answer 2

Let $M$ be the $(n+1) \times n$ matrix with entries $m_{ij}$ such that $b_i = \sum_j m_{ij} a_j$. Since $M$ has rank at most $n < n+1$, there is a nonzero vector $v$ such that $M^T v = 0$. Then $\sum_i v_i b_i = \sum_i (v^T M)_i a_i = 0$.

Answer 3

To answer your question about the Exchange Lemma: the Steinitz Exchange Lemma says that if $S = \{v_1,\ldots,v_m\}$ is a linearly independent set in a vector space $V$ and $T = \{w_1,\ldots,w_n\}$ is a spanning set for $V$, then there is a subset $T' \subset T$ such that $S \cup T$ is an $n$-element spanning set for $V$.

This has the immediate numerical consequence that $\# S \leq \# T$. What you say your text calls the Exchange Lemma is precisely this numerical consequence. In practice, it is the numerical consequence which is so incredibly useful in linear algebra. (Side note: I am teaching linear algebra, and I just lectured on the Steinitz Exchange Lemma, with the consequence that every linearly independent subset in a subspace of $\mathbb{R}^n$ is contained in a basis and any two bases of a subspace have the same number of elements. It was a good day.) However, it seems to me that Steinitz's insight was to record the slightly stronger statement, which is quite straightforward to prove inductively, whereas the numerical consequence does not look to be as easy to prove.

So to answer your question: no, it is not obvious (at least to me) that what you are being asked to prove is "equivalent" to the Steinitz Exchange Lemma. The latter looks to be a subtly stronger statement (although of course they're equivalent in the sense that they're both true statements which apply in the same contexts).