Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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