402 CHAPTER 18. LINEAR FUNCTIONS

Proof: Pick a nonzero vector of V,u1. If V = span{u1} , then stop. You have foundyour basis. If V ̸= span(u1) , then there exists u2 a vector of V which is not a vector inspan(u1) . Consider span(u1,u2) . By Lemma 18.5.8, {u1,u2} is linearly independent.If V = span(u1,u2) , stop. You have found a basis. Otherwise, pick u3 /∈ span(u1,u2) .Continue this way until you obtain a basis. The process must stop after fewer than n+ 1iterations because if it didn’t, then there would be a linearly independent set of more thann vectors which is impossible because there is a spanning set of n vectors from the aboveobservation.

The following is a fundamental result. It includes the idea that you can enlarge a linearlyindependent set of vectors to obtain a basis.

Theorem 18.5.10 If V is a subspace of Fn and the dimension of V is m, then m ≤ nand also if {u1, · · · ,um} is an independent set of vectors of V , then this set of vectors is abasis for V . Also, if you have a linearly independent set of vectors of V,{u1, · · · ,uk} fork ≤ m = dim(V ) , there is a linearly independent set of vectors {u1, · · · ,uk,vk+1, · · ·vm}which is a basis for V .

Proof: If the dimension of V is m, then it has a basis of m vectors. It follows m ≤n because if not, you would have an independent set of vectors which is longer than aspanning set of vectors {e1, · · · ,en} contrary to Theorem 18.5.3.

Next, if {u1, · · · ,um} is an independent set of vectors of V , then if it fails to span V, itmust be there is a vector w which is not in this span. But then by Lemma 18.5.8, you couldadd w to the list of vectors and get an independent set of m+1 vectors. However, the factthat V is of dimension m means there is a spanning set having only m vectors and so thiscontradicts Lemma 18.5.8. Thus {u1, · · · ,um} must be a spanning set.

Finally, if k = m, the vectors {u1, · · · ,uk} must span V since if not, you could addanother vector which is not in this list to the list and get an independent set which is longerthan a spanning set contrary to Theorem 18.5.3. Thus assume k < m. The set of vectors{u1, · · · ,uk} cannot span V because if it did, the dimension of V would be k not m. Thusthere is a vector vk+1 not in this span. Then by Lemma 18.5.8, {u1, · · · ,uk,vk+1} isindependent. If it spans V , stop. You have your basis. Otherwise, there is a vk+2 notin the span and so you can add it in and get an independent set {u1, · · · ,uk,vk+1,vk+2}.Continue this process till it stops. It must stop since otherwise, you would be able to get anindependent set of vectors larger than m which is the dimension of V, contrary to Theorem18.5.3.

Definition 18.5.11 The rank of a matrix A is the dimension of Im(A) which is thesame as the column space of A.

Theorem 18.5.12 Let A be an n×n matrix. Then A−1 exists if and only if the rankof A equals n.

Proof: This follows from Theorem 18.2.27 which says that A has an inverse if and onlyif each column of A is a pivot column if and only if the rank of A is n.