# how to prove fact about linear combinations of basis vectors using relationship between matrix columns?

How do we prove that if $\{v_1,...,v_m\}$ and $\{w_1,...,w_m\}$ are bases for a real vector space, then there are at most $m$ real numbers $\lambda$ such that $v_1+\lambda w_1,...,v_m+\lambda w_m$ are linearly dependent, using the following fact?

If $A=(a_{ij})$ is an $m\times n$ matrix with no all-zero column and $n>m$, and $k$ is minimal such that the first $k$ columns of A are linearly dependent, then there exist scalars $b_1,...,b_k$ such that $\Sigma_{j=1}^k a_{ij}b_j =0 \:\forall i$ but for any distinct scalars $\lambda_1,...,\lambda_k$, there exists $i$ such that $\Sigma_{j=1}^k a_{ij}b_j\lambda_j \not= 0$.

I think we should assume $n>m$ and let $A=(a_{ij})$ be such that $\Sigma_{i=1}^m a_{ij}(v_i+\lambda w_i) =0 \:\forall j$. Then we've got a matrix $A$ as in the second paragraph, but I can't see how to use the scalars $b_j$. Can they be interpreted as components of $v_i$ or $w_i$? And how do we get around the fact that we're summing over $i$ here and over $j$ in the second paragraph?

(The problem can be solved easily using determinants, but I need to do it using the second paragraph!)

Many thanks for any help with this!

-
But this isn't a matrix, because the $v_i$'s and $w_i$'s are vectors, not scalars. – Harry Macpherson May 30 '12 at 19:26
Answering my own question here... Use $\Sigma_i a_{ij}(v_i + \lambda_j w_i) = 0\:\forall j$ to get $\Sigma_{i,j} a_{ij}b_j(v_i + \lambda_j w_i) = 0$, which implies $\Sigma_{i,j} a_{ij}b_j \lambda_j w_i = 0$. Since the $w_i$ form a basis, this means $\Sigma_{i,j} a_{ij}b_j \lambda_j = 0$, which is a contradiction by the second paragraph. – Harry Macpherson May 30 '12 at 21:18
And how do you show such a matrix $A$ exists? – Keivan May 30 '12 at 21:27

Let's suppose there exist more than $m$ $\lambda_j$ such that the set $\{v_i - \lambda_jw_i \}_{1\le i\le m}$ is linearly dependent.

By definition, for every such $\lambda_j$ there exist scalars $\alpha_{ij}$ such that $\sum_{i=1}^m \alpha_{ij}(v_i - \lambda_jw_i) = 0$.

Now we have our matrix. The elements $b_j$ of your preposition are not important and we can, without loss of generality, suppose that $\sum_{j=1}^k \alpha_{ij} = 0$ (the equation $\sum_{i=1}^m \alpha_{ij}(v_i - \lambda_jw_i) = 0$ is still valid if we multiply the left side by $b_j$ ).

So, let's use the preposition:

\begin{align} 0 &= \Biggl(\sum_{j=1}^k \alpha_{ij}\Biggr)(v_i - \lambda_jw_i) = \sum_{j=1}^k \alpha_{ij}(v_i - \lambda_jw_i) =\\&= \sum_{j=1}^k \alpha_{ij}v_i - \sum_{j=1}^k \alpha_{ij}\lambda_jw_i = -\Biggl(\sum_{j=1}^k \alpha_{ij}\lambda_j\Biggr)w_i \end{align}

so $w_i = 0$ which contradict the fact that $\{w_i\}_{1\le i\le m}$ is a base.

-