# M equations, n unknowns

1. Jan 31, 2010

### choob

1. The problem statement, all variables and given/known data
prove, if S has m vectors in n dimensions and S is linearly independent, then n>=m

2. Relevant equations

3. The attempt at a solution
so far ive come up with:

there is no combination of vectors in S such that their sum is the zero vector,

there exists a vector which cannot be expressed in terms of a linear combination of other vectors

so ive started to assume that m>n (contradiction method)
however im stuck here.

im thinking of saying that if m>n, then there are more equations than unknowns in the system, but i dont know if that is helpful, and im stuck.

2. Jan 31, 2010

### HallsofIvy

Staff Emeritus
I hope you mean "except the trivial combination with all coefficients equal to 0"!

It's not clear to me what this means. What vectors are you talking about? Any vector can be expressed as a linear combination of some other vectors!

I have no idea what "equations" you are talking about. The problem said there were m vectors, not m equations.

Since the set of m vectors is linearly independent, any subset is also linearly indepependent. In particular, if m> n, then any subset of n vectors is linearly independent and so a basis. Now choose a vector in the set, v, that is NOT in that subset (which you can do since m> n). It can be written as a linear combination of the n basis vectors and you can use that to show that that subset of n+1 vectors, v together with the original n vector subset, that is NOT independent, a contradiction.

3. Jan 31, 2010

### choob

the equations correspond to the matrix which has to be reduced to give the coefficients for each vector, such that their sum is zero, if the system is linearly independent

other than that, ill post again later when i can wrap my head around what you said at the end haha

edit:

what i meant in that there exists a vector which cannot be expressed in terms of the other vectors in that set, is that if there exists v1+v2+..+v3=v4, where all those v's are vectors, then the system would be linearly dependent, because v4-(v1+v2+..+v3)=0

Last edited: Jan 31, 2010