18.5. LINEAR INDEPENDENCE 401

Proof: By assumption, uk = ∑si=1 aikvi for a suitable choice of the scalars aik. Then

the matrix whose ikth entry is aik has more columns than rows if s < r. Thus there is x ̸= 0such that ∑

rk=1 aikxk = 0 for each i thanks to Theorem 18.5.2. Now

r

∑k=1

xkuk =r

∑k=1

xk

s

∑i=1

aikvi =s

∑i=1

(r

∑k=1

aikxk

)vi =

s

∑i=1

0vi = 0

contradicting linear independence of {u1, · · · ,ur} and so you must have s ≥ r.Now is the very important idea of a basis and dimension.

Definition 18.5.4 Let V be a subspace of Fn. Then {u1, · · · ,ur} is called a basisfor V if each ui ∈ V and span(u1, · · · ,ur) = V and {u1, · · · ,ur} is linearly independent.In words, {u1, · · · ,ur} spans and is independent.

Theorem 18.5.5 Let {u1, · · · ,ur} and {v1, · · · ,vs} be bases for V . Then s = r.

Proof: From Theorem 18.5.3, r ≤ s since ui ∈ span(v1, · · · ,vs) and {u1, · · · ,ur} isindependent. Then also r ≥ s by the same reasoning.

Definition 18.5.6 Let V be a subspace of Fn. Then the dimension of V is the num-ber of vectors in a basis. This is well defined by Theorem 18.5.5.

Observation 18.5.7 The dimension of Fn is n. This is obvious because if x∈Fn, wherex =

(x1 · · · xn

)T, then x= ∑

ni=1 xiei which shows that {e1, · · · ,en} is a spanning

set. However, these vectors are clearly independent because if

∑i

xiei = 0,

then 0 =(

x1 · · · xn)T and so each xi = 0. Thus {e1, · · · ,en} is also linearly inde-

pendent.

The next lemma says that if you have a vector not in the span of a linearly independentset, then you can add it in and the resulting longer list of vectors will still be linearlyindependent.

Lemma 18.5.8 Suppose v /∈ span(u1, · · · ,uk) and {u1, · · · ,uk} is linearly indepen-dent. Then {u1, · · · ,uk,v} is also linearly independent.

Proof: Suppose ∑ki=1 ciui+dv= 0. It is required to verify that each ci = 0 and that d =

0. But if d ̸= 0, then you can solve for v as a linear combination of the vectors, {u1, · · · ,uk},v = −∑

ki=1( ci

d

)ui contrary to assumption. Therefore, d = 0. But then ∑

ki=1 ciui = 0 and

the linear independence of {u1, · · · ,uk} implies each ci = 0 also.It turns out that every nonzero subspace equals the span of linearly independent vectors.

This is the content of the next theorem.

Theorem 18.5.9 V is a nonzero subspace of Fn if and only if it has a basis.