Page 206 - Matrix Analysis & Applied Linear Algebra

4.4 Basis and Dimension 201
Example 4.4.5

Problem: If S r = {v 1 , v 2 ,..., v r } is a linearly independent subset of an
n -dimensional space V, where r< n, explain why it must be possible to find
extension vectors {v r+1 ,..., v n } from V such that
S n = {v 1 ,..., v r , v r+1 ,..., v n }
is a basis for V.
Solution 1: r< n means that span (S r ) = V, and hence there exists a vector
v r+1 ∈V such that v r+1 /∈ span (S r ) . The extension set S r+1 = S r ∪{v r+1 } is
an independent subset of V containing r+1 vectors—recall (4.3.15). Repeating
this process generates independent subsets S r+2 , S r+3 ,..., and eventually leads
to a maximal independent subset S n ⊂V containing n vectors.
Solution 2: The first solution shows that it is theoretically possible to find
extension vectors, but the argument given is not much help in actually computing
them. It is easy to remedy this situation. Let {b 1 , b 2 ,..., b n } be any basis for
V, and place the given v i ’s along with the b i ’s as columns in a matrix

A = v 1 |···| v r | b 1 |···| b n .
Clearly, R (A)= V so that the set of basic columns from A is a basis for V.
Observe that {v 1 , v 2 ,..., v r } are basic columns in A because no one of these is
a combination of preceding ones. Therefore, the remaining n − r basic columns

must be a subset of {b 1 , b 2 ,..., b n } —say they are b j 1 , b j 2 ,..., b j n−r . The
complete set of basic columns from A, and a basis for V, is the set

.
B = v 1 ,..., v r , b j 1 ,..., b j n−r
For example, to extend the independent set
1   0 

 
 
S =  0   0 
−1 1
  ,  
 
 
2 −2
4
to a basis for , append the standard basis {e 1 , e 2 , e 3 , e 4 } to the vectors in
S, and perform the reduction
1 01000 10100 0
   
 0 00100   01100 −1/2 
 .
−1 10010  −→ E A =  00010 0
A = 
2 −20001 00001 1/2
This reveals that {A ∗1 , A ∗2 , A ∗4 , A ∗5 } are the basic columns in A, and there-
fore
1 0 0 0
       
 
 
 ,
B =  0   0    ,  0 
 ,
 1 
−1 1 0 1
   
 
 
2 −2 0 0
4
is a basis for that contains S.