22 Chapter One.Linear Systems 3.4 Definition A column or row vector of all zeros is a zero vector,denoted 0. There are many different zero vectors,e.g.,the one-tall zero vector,the two-tall zero vector,etc.Nonetheless,people often refer to "the"zero vector,expecting that the size of the one being discussed will be clear from the context. 3.5 Example Some homogeneous systems have the zero vector as their only solution. 6r+4切=0-n3x+2到+8=0 3x+2y+z=0 3x+2y+z=0 -2z=02P y+z=0 y+2=0 y+z=0 -2z=0 3.6 Example Some homogeneous systems have many solutions.One example is the Chemistry problem from the first page of this book. 7x-7z=0 7x-7z =0 8x+y-5z-2k=0-(8/I)2+p2 y+3z-2w=0 y-3z=0 y-3z=0 3y-6z-k=0 3y-6z-w=0 7x-7x=0 -P2+P3 y+3z-2w=0 -3p2+P4 -6z+2w=0 -15z+5w=0 7x-7x =0 -(6/2)P3+P4 y+3z-2w=0 -6x+2D=0 0=0 The solution set: /3 1/3 D w∈R} 1 has many vectors besides the zero vector (if we interpret w as a number of molecules then solutions make sense only when w is a nonnegative multiple of 3) We now have the terminology to prove the two parts of Theorem 3.1.The first lemma deals with unrestricted combinations. 3.7 Lemma For any homogeneous linear system there exist vectors B1,..., B&such that the solution set of the system is {c13+…+ck|C1,,ck∈R} where k is the number of free variables in an echelon form version of the system
22 Chapter One. Linear Systems 3.4 Definition A column or row vector of all zeros is a zero vector , denoted ~0. There are many different zero vectors, e.g., the one-tall zero vector, the two-tall zero vector, etc. Nonetheless, people often refer to “the” zero vector, expecting that the size of the one being discussed will be clear from the context. 3.5 Example Some homogeneous systems have the zero vector as their only solution. 3x + 2y + z = 0 6x + 4y = 0 y + z = 0 −2ρ1+ρ2 −→ 3x + 2y + z = 0 −2z = 0 y + z = 0 ρ2↔ρ3 −→ 3x + 2y + z = 0 y + z = 0 −2z = 0 3.6 Example Some homogeneous systems have many solutions. One example is the Chemistry problem from the first page of this book. 7x − 7z = 0 8x + y − 5z − 2k = 0 y − 3z = 0 3y − 6z − k = 0 −(8/7)ρ1+ρ2 −→ 7x − 7z = 0 y + 3z − 2w = 0 y − 3z = 0 3y − 6z − w = 0 −ρ2+ρ3 −→ −3ρ2+ρ4 7x − 7z = 0 y + 3z − 2w = 0 −6z + 2w = 0 −15z + 5w = 0 −(5/2)ρ3+ρ4 −→ 7x − 7z = 0 y + 3z − 2w = 0 −6z + 2w = 0 0 = 0 The solution set: { 1/3 1 1/3 1 w ¯ ¯ w ∈ R} has many vectors besides the zero vector (if we interpret w as a number of molecules then solutions make sense only when w is a nonnegative multiple of 3). We now have the terminology to prove the two parts of Theorem 3.1. The first lemma deals with unrestricted combinations. 3.7 Lemma For any homogeneous linear system there exist vectors β~ 1, . . . , β~ k such that the solution set of the system is {c1β~ 1 + · · · + ckβ~ k ¯ ¯ c1, . . . , ck ∈ R} where k is the number of free variables in an echelon form version of the system
Section I.Solving Linear Systems 23 Before the proof,we will recall the back substitution calculations that were done in the prior subsection.Imagine that we have brought a system to this echelon form. x+2y-z+2w=0 -3y+2=0 一D=0 We next perform back-substitution to express each variable in terms of the free variable z.Working from the bottom up,we get first that w is 0.2, next that y is(1/3).z,and then substituting those two into the top equation x+2((1/3)z)-z+2(0)=0 gives x =(1/3).z.So,back substitution gives a parametrization of the solution set by starting at the bottom equation and using the free variables as the parameters to work row-by-row to the top.The proof below follows this pattern. Comment:That is,this proof just does a verification of the bookkeeping in back substitution to show that we haven't overlooked any obscure cases where this procedure fails,say,by leading to a division by zero.So this argument, while quite detailed,doesn't give us any new insights.Nevertheless,we have written it out for two reasons.The first reason is that we need the result-the computational procedure that we employ must be verified to work as promised. The second reason is that the row-by-row nature of back substitution leads to a proof that uses the technique of mathematical induction.*This is an important, and non-obvious,proof technique that we shall use a number of times in this book.Doing an induction argument here gives us a chance to see one in a setting where the proof material is easy to follow,and so the technique can be studied. Readers who are unfamiliar with induction arguments should be sure to master this one and the ones later in this chapter before going on to the second chapter. PRoOF.First use Gauss'method to reduce the homogeneous system to echelon form.We will show that each leading variable can be expressed in terms of free variables.That will finish the argument because then we can use those free variables as the parameters.That is,the B's are the vectors of coefficients of the free variables(as in Example 3.6,where the solution is x=(1/3)w,y=w, z=(1/3)w,and w =w). We will proceed by mathematical induction,which has two steps.The base step of the argument will be to focus on the bottom-most non-'0=0'equation and write its leading variable in terms of the free variables.The inductive step of the argument will be to argue that if we can express the leading variables from the bottom t rows in terms of free variables,then we can express the leading variable of the next row up-the t+1-th row up from the bottom-in terms of free variables.With those two steps,the theorem will be proved because by the base step it is true for the bottom equation,and by the inductive step the fact that it is true for the bottom equation shows that it is true for the next one up,and then another application of the inductive step implies it is true for third equation up,etc. More information on mathematical induction is in the appendix
Section I. Solving Linear Systems 23 Before the proof, we will recall the back substitution calculations that were done in the prior subsection. Imagine that we have brought a system to this echelon form. x + 2y − z + 2w = 0 −3y + z = 0 −w = 0 We next perform back-substitution to express each variable in terms of the free variable z. Working from the bottom up, we get first that w is 0 · z, next that y is (1/3) · z, and then substituting those two into the top equation x + 2((1/3)z) − z + 2(0) = 0 gives x = (1/3) · z. So, back substitution gives a parametrization of the solution set by starting at the bottom equation and using the free variables as the parameters to work row-by-row to the top. The proof below follows this pattern. Comment: That is, this proof just does a verification of the bookkeeping in back substitution to show that we haven’t overlooked any obscure cases where this procedure fails, say, by leading to a division by zero. So this argument, while quite detailed, doesn’t give us any new insights. Nevertheless, we have written it out for two reasons. The first reason is that we need the result — the computational procedure that we employ must be verified to work as promised. The second reason is that the row-by-row nature of back substitution leads to a proof that uses the technique of mathematical induction.∗ This is an important, and non-obvious, proof technique that we shall use a number of times in this book. Doing an induction argument here gives us a chance to see one in a setting where the proof material is easy to follow, and so the technique can be studied. Readers who are unfamiliar with induction arguments should be sure to master this one and the ones later in this chapter before going on to the second chapter. Proof. First use Gauss’ method to reduce the homogeneous system to echelon form. We will show that each leading variable can be expressed in terms of free variables. That will finish the argument because then we can use those free variables as the parameters. That is, the β~’s are the vectors of coefficients of the free variables (as in Example 3.6, where the solution is x = (1/3)w, y = w, z = (1/3)w, and w = w). We will proceed by mathematical induction, which has two steps. The base step of the argument will be to focus on the bottom-most non-‘0 = 0’ equation and write its leading variable in terms of the free variables. The inductive step of the argument will be to argue that if we can express the leading variables from the bottom t rows in terms of free variables, then we can express the leading variable of the next row up— the t + 1-th row up from the bottom— in terms of free variables. With those two steps, the theorem will be proved because by the base step it is true for the bottom equation, and by the inductive step the fact that it is true for the bottom equation shows that it is true for the next one up, and then another application of the inductive step implies it is true for third equation up, etc. ∗ More information on mathematical induction is in the appendix
3 Chapter One.Linear Systems For the base step,consider the bottom-most non-'0=0'equation (the case where all the equations are0=0'is trivial).We call that the m-th row: am.em Tem am.em+1Tem+1+..+am.nIn =0 where am.0.(The notation here has'stand for 'leading',so am.m means "the coefficient,from the row m of the variable leading row m".)Either there are variables in this equation other than the leading one rem or else there are not.If there are other variables e+1,etc.,then they must be free variables because this is the bottom non-0=0'row.Move them to the right and divide by am.em xtm=(-am,lm+1/am,lm)）xtm+1+…+（-am,n/am,lm)xn to express this leading variable in terms of free variables.If there are no free variables in this equation then =0(see the "tricky point"noted following this proof). For the inductive step,we assume that for the m-th equation,and for the (m-1)-th equation,...and for the (m-t)-th equation,we can express the leading variable in terms of free variables (where 0<t<m).To prove that the same is true for the next equation up,the (m-(t+1))-th equation,we take each variable that leads in a lower-down equation,...and substitute its expression in terms of free variables.The result has the form am-(t+1).m(()+sums of multiples of free variables =0 where ()0.We move the free variables to the right-hand side and divide by am-()to end with expressed in terms of free variables. Because we have shown both the base step and the inductive step,by the principle of mathematical induction the proposition is true. QED We say that the set {cB+...+ckB c1,...,ck ER}is generated by or spanned by the set of vectors (B,...,Bk).There is a tricky point to this definition.If a homogeneous system has a unique solution,the zero vector, then we say the solution set is generated by the empty set of vectors.This fits with the pattern of the other solution sets:in the proof above the solution set is derived by taking the c's to be the free variables and if there is a unique solution then there are no free variables. This proof incidentally shows,as discussed after Example 2.4,that solution sets can always be parametrized using the free variables. The next lemma finishes the proof of Theorem 3.1 by considering the par- ticular solution part of the solution set's description. 3.8 Lemma For a linear system,where pis any particular solution,the solution set equals this set. p+hh satisfies the associated homogeneous system}
24 Chapter One. Linear Systems For the base step, consider the bottom-most non-‘0 = 0’ equation (the case where all the equations are ‘0 = 0’ is trivial). We call that the m-th row: am,`mx`m + am,`m+1x`m+1 + · · · + am,nxn = 0 where am,`m 6= 0. (The notation here has ‘`’ stand for ‘leading’, so am,`m means “the coefficient, from the row m of the variable leading row m”.) Either there are variables in this equation other than the leading one x`m or else there are not. If there are other variables x`m+1, etc., then they must be free variables because this is the bottom non-‘0 = 0’ row. Move them to the right and divide by am,`m x`m = (−am,`m+1/am,`m)x`m+1 + · · · + (−am,n/am,`m)xn to express this leading variable in terms of free variables. If there are no free variables in this equation then x`m = 0 (see the “tricky point” noted following this proof). For the inductive step, we assume that for the m-th equation, and for the (m − 1)-th equation, . . . , and for the (m − t)-th equation, we can express the leading variable in terms of free variables (where 0 ≤ t < m). To prove that the same is true for the next equation up, the (m − (t + 1))-th equation, we take each variable that leads in a lower-down equation x`m, . . . , x`m−t and substitute its expression in terms of free variables. The result has the form am−(t+1),`m−(t+1)x`m−(t+1) + sums of multiples of free variables = 0 where am−(t+1),`m−(t+1) 6= 0. We move the free variables to the right-hand side and divide by am−(t+1),`m−(t+1) , to end with x`m−(t+1) expressed in terms of free variables. Because we have shown both the base step and the inductive step, by the principle of mathematical induction the proposition is true. QED We say that the set {c1β~ 1 + · · · + ckβ~ k ¯ ¯ c1, . . . , ck ∈ R} is generated by or spanned by the set of vectors {β~ 1, . . . , β~ k}. There is a tricky point to this definition. If a homogeneous system has a unique solution, the zero vector, then we say the solution set is generated by the empty set of vectors. This fits with the pattern of the other solution sets: in the proof above the solution set is derived by taking the c’s to be the free variables and if there is a unique solution then there are no free variables. This proof incidentally shows, as discussed after Example 2.4, that solution sets can always be parametrized using the free variables. The next lemma finishes the proof of Theorem 3.1 by considering the particular solution part of the solution set’s description. 3.8 Lemma For a linear system, where ~p is any particular solution, the solution set equals this set. {~p + ~h ¯ ¯ ~h satisfies the associated homogeneous system}
Section I.Solving Linear Systems 25 PRooF.We will show mutual set inclusion,that any solution to the system is in the above set and that anything in the set is a solution to the system.* For set inclusion the first way,that if a vector solves the system then it is in the set described above,assume that s solves the system.Then s-p solves the associated homogeneous system since for each equation index i, ai,1(81-P1)+.+ai,n(sn -Pn)=(ai,181+...+ai,nsn) -（(a,1p1+…+ai,nPn） di-di =0 where pj and sj are the j-th components of p and s.We can write s-p as h, where h solves the associated homogeneous system,to express s in the required p+h form. For set inclusion the other way,take a vector of the form p+h,where p solves the system and h solves the associated homogeneous system,and note that it solves the given system:for any equation index i, ai,1(P1 +h1)+..+ai.n(Pn +hn)=(ai,1p1+...+ai.npn) +(ai,1h1+…+ai,nhn） =d:+0 =di where hj is the j-th component of h. QED The two lemmas above together establish Theorem 3.1.We remember that theorem with the slogan "General =Particular+Homogeneous". 3.9 Example This system illustrates Theorem 3.1. x+2y-z=1 2x+4y =2 y-3z=0 Gauss'method x+2y-z=1 x+2y-z=1 -2p12 2z=02-3 y-3z=0 y-3z=0 2z=0 shows that the general solution is a singleton set. More information on equality of sets is in the appendix
Section I. Solving Linear Systems 25 Proof. We will show mutual set inclusion, that any solution to the system is in the above set and that anything in the set is a solution to the system.∗ For set inclusion the first way, that if a vector solves the system then it is in the set described above, assume that ~s solves the system. Then ~s − ~p solves the associated homogeneous system since for each equation index i, ai,1(s1 − p1) + · · · + ai,n(sn − pn) = (ai,1s1 + · · · + ai,nsn) − (ai,1p1 + · · · + ai,npn) = di − di = 0 where pj and sj are the j-th components of ~p and ~s. We can write ~s − ~p as ~h, where ~h solves the associated homogeneous system, to express ~s in the required ~p + ~h form. For set inclusion the other way, take a vector of the form ~p + ~h, where ~p solves the system and ~h solves the associated homogeneous system, and note that it solves the given system: for any equation index i, ai,1(p1 + h1) + · · · + ai,n(pn + hn) = (ai,1p1 + · · · + ai,npn) + (ai,1h1 + · · · + ai,nhn) = di + 0 = di where hj is the j-th component of ~h. QED The two lemmas above together establish Theorem 3.1. We remember that theorem with the slogan “General = Particular + Homogeneous”. 3.9 Example This system illustrates Theorem 3.1. x + 2y − z = 1 2x + 4y = 2 y − 3z = 0 Gauss’ method −2ρ1+ρ2 −→ x + 2y − z = 1 2z = 0 y − 3z = 0 ρ2↔ρ3 −→ x + 2y − z = 1 y − 3z = 0 2z = 0 shows that the general solution is a singleton set. { 1 0 0 } ∗ More information on equality of sets is in the appendix
26 Chapter One.Linear Systems That single vector is,of course,a particular solution.The associated homoge- neous system reduces via the same row operations x+2y-z=0 x+2y-2=0 2x+4y =0 -2p1十P22-g3 y-3z=0 y-32=0 2z=0 to also give a singleton set 0 As the theorem states,and as discussed at the start of this subsection,in this single-solution case the general solution results from taking the particular solu- tion and adding to it the unique solution of the associated homogeneous system. 3.10 Example Also discussed there is that the case where the general solution set is empty fits the 'General Particular+Homogeneous'pattern.This system illustrates.Gauss'method x+2+0=-1 2x-y+w=3 -2pt%工+2+0=-1 -y-2z-w=5 x+y+3z+2w=1 -P1+P3 y+2z+w=2 shows that it has no solutions.The associated homogeneous system,of course, has a solution. x+2十=0 x+z+w=0 2x-y+w=0 -2p1+p2P2+3 -y-2z-w=0 x+y+3z+2w=0 -P1+P3 0=0 In fact,the solution set of the homogeneous system is infinite. z,w∈R} However,because no particular solution of the original system exists,the general solution set is empty-there are no vectors of the form p+h because there are no p's. 3.11 Corollary Solution sets of linear systems are either empty,have one element,or have infinitely many elements. PROoF.We've seen examples of all three happening so we need only prove that those are the only possibilities. First,notice a homogeneous system with at least one non-0 solution has infinitely many solutions because the set of multiples su is infinite-if s1 then s=(s-1)is easily seen to be non-0,and so si
26 Chapter One. Linear Systems That single vector is, of course, a particular solution. The associated homogeneous system reduces via the same row operations x + 2y − z = 0 2x + 4y = 0 y − 3z = 0 −2ρ1+ρ2 −→ ρ2↔ρ3 −→ x + 2y − z = 0 y − 3z = 0 2z = 0 to also give a singleton set. { 0 0 0 } As the theorem states, and as discussed at the start of this subsection, in this single-solution case the general solution results from taking the particular solution and adding to it the unique solution of the associated homogeneous system. 3.10 Example Also discussed there is that the case where the general solution set is empty fits the ‘General = Particular+Homogeneous’ pattern. This system illustrates. Gauss’ method x + z + w = −1 2x − y + w = 3 x + y + 3z + 2w = 1 −2ρ1+ρ2 −→ −ρ1+ρ3 x + z + w = −1 −y − 2z − w = 5 y + 2z + w = 2 shows that it has no solutions. The associated homogeneous system, of course, has a solution. x + z + w = 0 2x − y + w = 0 x + y + 3z + 2w = 0 −2ρ1+ρ2 −→ −ρ1+ρ3 ρ2+ρ3 −→ x + z + w = 0 −y − 2z − w = 0 0 = 0 In fact, the solution set of the homogeneous system is infinite. { −1 −2 1 0 z + −1 −1 0 1 w ¯ ¯ z, w ∈ R} However, because no particular solution of the original system exists, the general solution set is empty— there are no vectors of the form ~p +~h because there are no ~p ’s. 3.11 Corollary Solution sets of linear systems are either empty, have one element, or have infinitely many elements. Proof. We’ve seen examples of all three happening so we need only prove that those are the only possibilities. First, notice a homogeneous system with at least one non-~0 solution ~v has infinitely many solutions because the set of multiples s~v is infinite — if s 6= 1 then s~v − ~v = (s − 1)~v is easily seen to be non-~0, and so s~v 6= ~v