[1001 1] 0102 1 Ab'=0013 -1 0000 0 L0000 2 In this case,A'x b'(and Ax b)has no solution. Case 2 Suppose that Case 1 does not apply and NBV,the set of nonbasic variables,is empty.Then A'x =b'(and Ax =b)will have a unique solution.To illustrate this,we re- call that in solving 2x1+2x2+x3=9 2x1-x2+2x3=6 x1-x2+2x3=5 the Gauss-Jordan method yielded 1 [100 A'b'=010 2 [0013J In this case,BV ={x1,x2,x3}and NBV is empty.Then the unique solution to 4'x =b' (and Ax =b)isx1 1,x2=2,x3 =3. Case 3 Suppose that Case 1 does not apply and NBV is nonempty.Then A'x =b'(and Ax=b)will have an infinite number of solutions.To obtain these,first assign each non- basic variable an arbitrary value.Then solve for the value of each basic variable in terms of the nonbasic variables.For example,suppose [1001131 01020 A'b'= 2 001011 (15) L000000 Because Case 1 does not apply,and BV ={x1,x2,x3}and NBV ={x4,xs),we have an example of Case 3:4'x b'(and Ax b)will have an infinite number of solutions.To see what these solutions look like,write down 4'x b': X1 +x4+x5=3 15.1) X2 2x4=2 (15.2) X3 +x5=1 15.3) 0x1+0x2+0c3+0x4+0x5=0 15.40 Now assign the nonbasic variables (x4 and xs)arbitrary values c and k,with x4=c and xs k.From (15.1),we find that x=3-c -k.From (15.2),we find that x2=2 -2c.From (15.3),we find that x3 1 -k.Because (15.4)holds for all values of the variables,x1=3 -c-k,x2 2 -2c,x3 1 -k,x4 c,and xs k will,for any values of c and k,be a solution to A'x b'(and Ax =b). Our discussion of the Gauss-Jordan method is summarized in Figure 6.We have de- voted so much time to the Gauss-Jordan method because,in our study of linear pro- gramming,examples of Case 3(linear systems with an infinite number of solutions)will occur repeatedly.Because the end result of the Gauss-Jordan method must always be one of Cases 1-3,we have shown that any linear system will have no solution,a unique so- lution,or an infinite number of solutions
A b In this case, A x b (and Ax b) has no solution. Case 2 Suppose that Case 1 does not apply and NBV, the set of nonbasic variables, is empty. Then A x b (and Ax b) will have a unique solution. To illustrate this, we recall that in solving 2x1 2x2 x3 9 2x1 x2 2x3 6 2x1 x2 2x3 5 the Gauss–Jordan method yielded A b In this case, BV {x1, x2, x3} and NBV is empty. Then the unique solution to A x b (and Ax b) is x1 1, x2 2, x3 3. Case 3 Suppose that Case 1 does not apply and NBV is nonempty. Then A x b (and Ax b) will have an infinite number of solutions. To obtain these, first assign each nonbasic variable an arbitrary value. Then solve for the value of each basic variable in terms of the nonbasic variables. For example, suppose A b (15) Because Case 1 does not apply, and BV {x1, x2, x3} and NBV {x4, x5}, we have an example of Case 3: A x b (and Ax b) will have an infinite number of solutions. To see what these solutions look like, write down A x b : 0x1 0x2 0x3 0x4 0x5 3 (15.1) 0x1 0x2 0x3 2x4 0x5 2 (15.2) 0x1 0x2 0x3 0x4 0x5 1 (15.3) 0x1 0x2 0x3 0x4 0x5 0 (15.4) Now assign the nonbasic variables (x4 and x5) arbitrary values c and k, with x4 c and x5 k. From (15.1), we find that x1 3 c k. From (15.2), we find that x2 2 2c. From (15.3), we find that x3 1 k. Because (15.4) holds for all values of the variables, x1 3 c k, x2 2 2c, x3 1 k, x4 c, and x5 k will, for any values of c and k, be a solution to A x b (and Ax b). Our discussion of the Gauss–Jordan method is summarized in Figure 6. We have devoted so much time to the Gauss–Jordan method because, in our study of linear programming, examples of Case 3 (linear systems with an infinite number of solutions) will occur repeatedly. Because the end result of the Gauss–Jordan method must always be one of Cases 1–3, we have shown that any linear system will have no solution, a unique solution, or an infinite number of solutions. 3 2 1 0 1 0 1 0 1 2 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 2 3 0 0 1 0 1 0 1 0 0 1 1 1 0 2 1 2 3 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 2.3 The Gauss–Jordan Method for Solving Systems of Linear Equations 31
Does A'Ib'have a row00·0lc](c≠0)2 YES NO Ax bhas Find BV no solution and NBV Is NBV empty? FIGURE 6 YES No Description of Gauss-Jordan Method Ax=bhas a Ax =b has an for Solving Linear infinite number unique solution Equations of solutions PROBLEMS Group A Use the Gauss-Jordan method to determine whether each of 2x2+2x3=4 the following linear systems has no solution,a unique solu- x1+2x2+x3=4 tion,or an infinite number of solutions.Indicate the solu- 2-x3=0 tions (if any exist). 7x1+x2 =2 1x1+2+x4=3 -x2+2x3=3 x2+X3=4 2+x3=3 x1+2x2+x3+x4=8 8x1+x2+53=1 2x1+x2+x3=4 2+2x3+x4=2 x1+2x2=6 x4=3 3x1+2=1 2x1+x2=3 Group B 3x1+2x2=4 9 Suppose that a linear system Ax=b has more variables 42x1-x2+x3+x4=6 than equations.Show that Ax b cannot have a unique x1+x2+x3 =4 solution. 5x1 x4=5 2+2x4=5 x3+0.5x4=1 2x3+x4=3 2.4 Linear Independence and Linear Dependence In this section,we discuss the concepts of a linearly independent set of vectors,a lin- early dependent set of vectors,and the rank of a matrix.These concepts will be useful in our study of matrix inverses. Before defining a linearly independent set of vectors,we need to define a linear com- bination of a set of vectors.Let V={v1.v2,...,ve}be a set of row vectors all of which have the same dimension. This section covers topics that may be omitted with no loss of continuity
32 CHAPTER 2 Basic Linear Algebra Use the Gauss–Jordan method to determine whether each of the following linear systems has no solution, a unique solution, or an infinite number of solutions. Indicate the solutions (if any exist). 1 x1 x2 x3 x4 3 1 x1 x2 x3 x4 4 1 x1 2x2 x3 x4 8 2 x1 x2 x3 4 2 x1 2x2 x3 6 3 x1 x2 1 2 2x1 x2 3 2 3x1 2x2 4 4 2x1 x2 x3 x4 6 2 x1 x2 x3 x4 4 5 x1x2 x2 x4 5 2 x2x2x 2 2x4 5 2 x2x 2x3 0.5x4 1 x2 2x3 x4 3 6 x1 2x2 2x3 4 2 x1 2x2 x3 4 2 xx1 2x2 x3 0 7 x1 x2 2x3 2 2 x1 x2 2x3 3 2 x1 x2 x3 3 8 x1 x2 x3 x4 1 2 x1 x2 2x3 x4 2 2 x1 x2 2x3 x4 3 Group B 9 Suppose that a linear system Ax b has more variables than equations. Show that Ax b cannot have a unique solution. 2.4 Linear Independence and Linear Dependence† In this section, we discuss the concepts of a linearly independent set of vectors, a linearly dependent set of vectors, and the rank of a matrix. These concepts will be useful in our study of matrix inverses. Before defining a linearly independent set of vectors, we need to define a linear combination of a set of vectors. Let V {v1, v2, . . . , vk} be a set of row vectors all of which have the same dimension. † This section covers topics that may be omitted with no loss of continuity. YES YES NO NO Does A b have a row [0 0 · · · 0 c] (c ≠ 0)? Ax = b has no solution Find BV and NBV Is NBV empty? Ax = b has a unique solution Ax = b has an infinite number of solutions FIGURE 6 Description of Gauss–Jordan Method for Solving Linear Equations PROBLEMS Group A
DEFINITION A linear combination of the vectors in V is any vector of the form civ+c2v2 …+CVk,where c,c2,+.·,ck are arbitrary scalars.■ For example,if V={[1 2],[2 1]),then 2v1-v2=2[12])-[21]=[03] v1+3v2=[12]+3[21）=[75] 0v1+3v2=[00]+3([21])=[63] are linear combinations of vectors in V.The foregoing definition may also be applied to a set of column vectors. Suppose we are given a set V={v1,v2,...,v}of m-dimensional row vectors.Let 0=[0 0...0]be the m-dimensional 0 vector.To determine whether V is a linearly independent set of vectors,we try to find a linear combination of the vectors in V that adds up to 0.Clearly,Ov Ov2 +..Ov&is a linear combination of vectors in Vthat adds up to 0.We call the linear combination of vectors in I for which c=c2 =... ck=0 the trivial linear combination of vectors in V.We may now define linearly inde- pendent and linearly dependent sets of vectors. DEFINITION■ A set of m-dimensional vectors is linearly independent if the only linear combination of vectors in V that equals 0 is the trivial linear combination. A set Vof m-dimensional vectors is linearly dependent if there is a nontrivial linear combination of the vectors in that adds up to 0.m The following examples should clarify these definitions. EXAMPLE 8 0 Vector Makes Set LD Show that any set of vectors containing the 0 vector is a linearly dependent set. Solution To illustrate,we show that if={[00],[1 0],[0 1]),then V is linearly dependent, because if,say,c 0,then c1([00])+0([1 0])+0([0 1])=[00].Thus,there is a nontrivial linear combination of vectors in Vthat adds up to 0. EXAMPLE 9 LI Set of Vectors Show that the set of vectors V={[1 0],[0 1])is a linearly independent set of vectors. Solution We try to find a nontrivial linear combination of the vectors in that yields 0.This re- quires that we find scalars c and c2(at least one of which is nonzero)satisfying cI([1 0])+c2([0 1])=[00].Thus,cI and c2 must satisfy [cI c2]=[0 0].This implies c=c2=0.The only linear combination of vectors in Vthat yields 0 is the trivial linear combination.Therefore,V is a linearly independent set of vectors. EXAMPLE 10 LD Set of Vectors Show that V={[1 2],[2 4])is a linearly dependent set of vectors. Solution Because 2([1 21)-1([2 4])=[00],there is a nontrivial linear combination with c1=2 and c2=-1 that yields 0.Thus,V is a linearly dependent set of vectors. Intuitively,what does it mean for a set of vectors to be linearly dependent?To understand the concept of linear dependence,observe that a set of vectors V is linearly dependent(as
DEFINITION ■ A linear combination of the vectors in V is any vector of the form c1v1 c2v2 ckvk, where c1, c2, . . . , ck are arbitrary scalars. ■ For example, if V {[1 2], [2 1]}, then 2v1 v2 2([1 2]) [2 1] [0 3] v1 3v2 [1 2] 3([2 1]) [7 5] 0v1 3v2 [0 0] 3([2 1]) [6 3] are linear combinations of vectors in V. The foregoing definition may also be applied to a set of column vectors. Suppose we are given a set V {v1, v2, . . . , vk} of m-dimensional row vectors. Let 0 [0 0 0] be the m-dimensional 0 vector. To determine whether V is a linearly independent set of vectors, we try to find a linear combination of the vectors in V that adds up to 0. Clearly, 0v1 0v2 0vk is a linear combination of vectors in V that adds up to 0. We call the linear combination of vectors in V for which c1 c2 ck 0 the trivial linear combination of vectors in V. We may now define linearly independent and linearly dependent sets of vectors. DEFINITION ■ A set V of m-dimensional vectors is linearly independent if the only linear combination of vectors in V that equals 0 is the trivial linear combination. ■ A set V of m-dimensional vectors is linearly dependent if there is a nontrivial linear combination of the vectors in V that adds up to 0. ■ The following examples should clarify these definitions. Show that any set of vectors containing the 0 vector is a linearly dependent set. Solution To illustrate, we show that if V {[0 0], [1 0], [0 1]}, then V is linearly dependent, because if, say, c1 0, then c1([0 0]) 0([1 0]) 0([0 1]) [0 0]. Thus, there is a nontrivial linear combination of vectors in V that adds up to 0. Show that the set of vectors V {[1 0], [0 1]} is a linearly independent set of vectors. Solution We try to find a nontrivial linear combination of the vectors in V that yields 0. This requires that we find scalars c1 and c2 (at least one of which is nonzero) satisfying c1([1 0]) c2([0 1]) [0 0]. Thus, c1 and c2 must satisfy [c1 c2] [0 0]. This implies c1 c2 0. The only linear combination of vectors in V that yields 0 is the trivial linear combination. Therefore, V is a linearly independent set of vectors. Show that V {[1 2], [2 4]} is a linearly dependent set of vectors. Solution Because 2([1 2]) 1([2 4]) [0 0], there is a nontrivial linear combination with c1 2 and c2 1 that yields 0. Thus, V is a linearly dependent set of vectors. Intuitively, what does it mean for a set of vectors to be linearly dependent? To understand the concept of linear dependence, observe that a set of vectors V is linearly dependent (as 2.4 Linear Independence and Linear Dependence 33 EXAMPLE 8 0 Vector Makes Set LD EXAMPLE 9 LI Set of Vectors EXAMPLE 1 0 LD Set of Vectors
y1=[11]=AB 2=[11] v2=[22]=AC v1=[10] B FIGURE 7 (a)Two Linearly Dependent Vectors (b)Two Linearly Independent Vectors long as 0 is not in /if and only if some vector in I can be written as a nontrivial linear combination of other vectors in /(see Problem 9 at the end of this section).For instance,in Example 10,[2 4]=2([1 2]).Thus,if a set of vectors V is linearly dependent,the vec- tors in Vare,in some way,not all“different'”vectors..By“different'”we mean that the di- rection specified by any vector in Vcannot be expressed by adding together multiples of other vectors in V.For example,in two dimensions it can be shown that two vectors are linearly dependent if and only if they lie on the same line (see Figure 7). The Rank of a Matrix The Gauss-Jordan method can be used to determine whether a set of vectors is linearly independent or linearly dependent.Before describing how this is done,we define the con- cept of the rank of a matrix. Let A be any m x n matrix,and denote the rows of 4 by r1,r2,...,r Also define R={r1,r2,·,rm DEFINITION The rank of A is the number of vectors in the largest linearly independent sub- set of R.■ The following three examples illustrate the concept of rank. EXAMPLE 11 Matrix with 0 Rank Show that rank 4 =0 for the following matrix: 4=8 Solution For the set of vectors R ={[00],[0,0]),it is impossible to choose a subset of R that is linearly independent(recall Example 8). EXAMPLE 12 Matrix with Rank of 1 Show that rank 4=1 for the following matrix:
long as 0 is not in V ) if and only if some vector in V can be written as a nontrivial linear combination of other vectors in V (see Problem 9 at the end of this section). For instance, in Example 10, [2 4] 2([1 2]). Thus, if a set of vectors V is linearly dependent, the vectors in V are, in some way, not all “different” vectors. By “different” we mean that the direction specified by any vector in V cannot be expressed by adding together multiples of other vectors in V. For example, in two dimensions it can be shown that two vectors are linearly dependent if and only if they lie on the same line (see Figure 7). The Rank of a Matrix The Gauss–Jordan method can be used to determine whether a set of vectors is linearly independent or linearly dependent. Before describing how this is done, we define the concept of the rank of a matrix. Let A be any m n matrix, and denote the rows of A by r1, r2, . . . , rm. Also define R {r1, r2, . . . , rm}. DEFINITION ■ The rank of A is the number of vectors in the largest linearly independent subset of R. ■ The following three examples illustrate the concept of rank. Show that rank A 0 for the following matrix: A Solution For the set of vectors R {[0 0], [0, 0]}, it is impossible to choose a subset of R that is linearly independent (recall Example 8). Show that rank A 1 for the following matrix: A 1 2 1 2 0 0 0 0 34 CHAPTER 2 Basic Linear Algebra EXAMPLE 1 2 Matrix with Rank of 1 EXAMPLE 1 1 Matrix with 0 Rank 3 2 x2 x1 1 v v2 1 A B C v1 = = AB = AC 1 1 1 a 2 3 v2 = 2 2 3 2 x2 x1 1 v2 v1 v2 = 1 1 1 b 2 3 v1 = 1 0 FIGURE 7 (a) Two Linearly Dependent Vectors (b) Two Linearly Independent Vectors
Solution Here R={[1 1],[22]).The set {[1 1])is a linearly independent subset of R,so rank A must be at least 1.If we try to find two linearly independent vectors in R,we fail because 2([1 1D)-[2 2]=[00].This means that rank 4 cannot be 2.Thus,rank 4 must equal 1. EXAMPLE 13 Matrix with Rank of 2 Show that rank 4 =2 for the following matrix: 4-6 Solution Here R ={[1 0],[0 1]).From Example 9,we know that R is a linearly independent set of vectors.Thus,rank A =2. To find the rank of a given matrix A,simply apply the Gauss-Jordan method to the matrix A.Let the final result be the matrix A.It can be shown that performing a sequence of EROs on a matrix does not change the rank of the matrix.This implies that rank 4 rank A.It is also apparent that the rank of 4 will be the number of nonzero rows in A. Combining these facts,we find that rank A rank 4 number of nonzero rows in A. EXAMPLE 14 Using Gauss-Jordan Method to Find Rank of Matrix Find [10 07 rank A 02 1 0 2 3 Solution The Gauss-Jordan method yields the following sequence of matrices: [100 [100 [1001 [100 [100 A=021→01 0 1 1-2 →01 0 10 023023 02 001 0 0 -7 Thus,rank A rank 4 3. How to Tell Whether a Set of Vectors Is Linearly Independent We now describe a method for determining whether a set of vectors V=(v1,v2,...,v} is linearly independent. Form the matrix A whose ith row is vi.A will have m rows.If rank 4 =m,then V is a linearly independent set of vectors,whereas if rank 4<m.then /is a linearly depen- dent set of vectors. EXAMPLE 15 A Linearly Dependent Set of Vectors Determine whether ={[1 00],[0 1 0],[11 0]}is a linearly independent set of vectors
Solution Here R {[1 1], [2 2]}. The set {[1 1]} is a linearly independent subset of R, so rank A must be at least 1. If we try to find two linearly independent vectors in R, we fail because 2([1 1]) [2 2] [0 0]. This means that rank A cannot be 2. Thus, rank A must equal 1. Show that rank A 2 for the following matrix: A Solution Here R {[1 0], [0 1]}. From Example 9, we know that R is a linearly independent set of vectors. Thus, rank A 2. To find the rank of a given matrix A, simply apply the Gauss–Jordan method to the matrix A. Let the final result be the matrix A. It can be shown that performing a sequence of EROs on a matrix does not change the rank of the matrix. This implies that rank A rank A. It is also apparent that the rank of A will be the number of nonzero rows in A. Combining these facts, we find that rank A rank A number of nonzero rows in A. Find rank A Solution The Gauss–Jordan method yields the following sequence of matrices: A → → → → A Thus, rank A rank A 3. How to Tell Whether a Set of Vectors Is Linearly Independent We now describe a method for determining whether a set of vectors V {v1, v2, . . . , vm} is linearly independent. Form the matrix A whose ith row is vi. A will have m rows. If rank A m, then V is a linearly independent set of vectors, whereas if rank A m, then V is a linearly dependent set of vectors. Determine whether V {[1 0 0], [0 1 0], [1 1 0]} is a linearly independent set of vectors. 0 0 1 0 1 0 1 0 0 0 1 2 1 0 1 0 1 0 0 0 1 2 2 0 1 0 1 0 0 0 1 2 3 0 1 2 1 0 0 0 1 3 0 2 2 1 0 0 0 1 3 0 2 2 1 0 0 0 1 1 0 2.4 Linear Independence and Linear Dependence 35 EXAMPLE 1 4 Using Gauss–Jordan Method to Find Rank of Matrix EXAMPLE 1 5 A Linearly Dependent Set of Vectors EXAMPLE 1 3 Matrix with Rank of 2