162 CHAPTER 9. SUBSPACES SPANS AND BASES

where B is an m× (n−1) matrix. Since n > m+ 1, it follows that (n−1) > m and soby induction, there exists a nonzero vector y ∈ Fn−1 such that By = 0. Then consider thevector

x=

(by

)

A1x has for its top entry the expression b+aTy. Letting B=

bT

1...bT

m

 , the ith entry of A1x

for i > 1 is of the form bTi y = 0. Thus if b is chosen to satisfy the equation b+aTy = 0,

then A1x= 0.■Now here is a very fundamental definition.

Definition 9.1.5 Let {u1, · · · ,ur} be vectors in Fp. They are independent if and only if theonly solution to the system of equations(

u1 · · · ur

)x= 0

is x= 0. In other words the vectors are independent means that whenever

r

∑i=1

xiui = 0

it follows that each xi = 0. The set of vectors is dependent if it is not independent. ThusTheorem 9.1.4 says that if you have more than n vectors in Fn this set of vectors will bedependent.

With this preparation, here is a major theorem.

Theorem 9.1.6 Suppose you have vectors {u1, · · · ,ur} and that this set of vectors is in-dependent. Suppose also that there are vectors {v1, · · · ,vs} and that each u j is a linearcombination of the vectors {v1, · · · ,vs} . Then r ≤ s. A little less precisely, spanning setsare at least as long as linearly independent sets.

Proof: Let ui = ∑sj=1 a jiv j. This is merely giving names to the scalars in the linear

combination which yields ui. Now suppose that s < r. Then if A is the matrix which has a jiin the jth row and the ith column, it follows from Theorem 9.1.4 that there exists a vectorin Fr such that Ax= 0 but x ̸= 0. However, then

(u1 · · · ur

)xi...

xr

 =r

∑i=1

xiui =r

∑i=1

xi

s

∑j=1

a jiv j

=s

∑j=1

r

∑i=1

a jixiv j =s

∑j=1

(Ax) j v j

=s

∑j=1

0v j = 0