# A family of $n$ non-zero vectors of an $(n-1)$-dimensional vector space must be linearly dependent

I was bored earlier and began to think of the pigeonhole principle, and it came to me that it could be used to show that a family of $n$ non-zero vectors of an $(n-1)$-dimensional vector space must be linearly dependent... but I quickly lost mental track of how I came to that conclusion. I don't need rigorous proof and it's not for any homework problems, I'm just hoping someone might be able to contribute some insight I seem to now have lost.

-
Well, if they were linearly independent, then their span would be an $n$-dimensional vector space; a contradiction. – Christopher A. Wong Mar 29 '13 at 4:47
thanks @dineshdileep -- I was wondering what I screwed up! – oldrinb Mar 29 '13 at 5:04
@ChristopherA.Wong right, I'm familiar with that contradiction. I just figured there might be a trivial way of doing it by the pigeonhole principle... hmm... thanks though! :-) – oldrinb Mar 29 '13 at 5:04

Any $n-1$ dimensional vector space is spanned by $n-1$ vectors. Let's call them $v_1,\ldots, v_{n-1}$. Now, suppose that you have your family of $n$ non-zero vectors, $w_1,\ldots, w_{n-1}$. Each may be written as a linear combination of the $n-1$ $v_i$ vectors, so we may perform gaussian elimination on $w_1,\ldots, w_{n-1}$. This must at least reduce to one $w_i$ which can be written as a sum of the other $w_j$, which implies the conclusion.
Right, that agrees with the less-general geometric proof in terms of intersecting $n-1$ hyperplanes, I think. Do you know of a means of proving it via the pigeonhole principle? – oldrinb Mar 29 '13 at 5:17
@oldrinb A basis of an $n-1$ dimensional space consists of $n-1$ vectors. These are the holes. Your family of $n$ non-zero vectors are the pigeons. – Alexander Gruber Mar 29 '13 at 5:59