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.

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.

share|improve this question
2  
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

1 Answer 1

up vote 2 down vote accepted

Really the contradiction argument in Chris Wong's comment is the best way to solve this. If you'd prefer a direct proof, however, here it is.

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.

share|improve this answer
    
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
1  
@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
    
Aha! That must be what I had been thinking of. –  oldrinb Mar 30 '13 at 19:14

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.