Section I.Solving Linear Systems 1 Another way that linear systems can differ from the examples shown earlier is that some linear systems do not have a unique solution.This can happen in two ways. The first is that it can fail to have any solution at all. 1.12 Example Contrast the system in the last example with this one. 2+y=-3-2+m工+3y=1 x+3y=1 -5y=-5 2x+2y=0 -2p1+p% -4y=-2 Here the system is inconsistent:no pair of numbers satisfies all of the equations simultaneously.Echelon form makes this inconsistency obvious. x+3y=1 -(4/5)2+p3 -5则=-5 0=2 The solution set is empty. 1.13 Example The prior system has more equations than unknowns,but that is not what causes the inconsistency-Example 1.11 has more equations than unknowns and yet is consistent.Nor is having more equations than unknowns necessary for inconsistency,as is illustrated by this inconsistent system with the same number of equations as unknowns. x+2y=8-2ptx+2y=8 2x+4y=8 0=-8 The other way that a linear system can fail to have a unique solution is to have many solutions. 1.14 Example In this system x+y=4 2x+2y=8 any pair of numbers satisfying the first equation automatically satisfies the sec- ond.The solution set {(y)+y=4}is infinite;some of its members are (0,4),(-1,5),and (2.5,1.5).The result of applying Gauss'method here contrasts with the prior example because we do not get a contradictory equa- tion. -2p1十2x+y=4 0=0 Don't be fooled by the'0=0'equation in that example.It is not the signal that a system has many solutions
Section I. Solving Linear Systems 7 Another way that linear systems can differ from the examples shown earlier is that some linear systems do not have a unique solution. This can happen in two ways. The first is that it can fail to have any solution at all. 1.12 Example Contrast the system in the last example with this one. x + 3y = 1 2x + y = −3 2x + 2y = 0 −2ρ1+ρ2 −→ −2ρ1+ρ3 x + 3y = 1 −5y = −5 −4y = −2 Here the system is inconsistent: no pair of numbers satisfies all of the equations simultaneously. Echelon form makes this inconsistency obvious. −(4/5)ρ2+ρ3 −→ x + 3y = 1 −5y = −5 0 = 2 The solution set is empty. 1.13 Example The prior system has more equations than unknowns, but that is not what causes the inconsistency — Example 1.11 has more equations than unknowns and yet is consistent. Nor is having more equations than unknowns necessary for inconsistency, as is illustrated by this inconsistent system with the same number of equations as unknowns. x + 2y = 8 2x + 4y = 8 −2ρ1+ρ2 −→ x + 2y = 8 0 = −8 The other way that a linear system can fail to have a unique solution is to have many solutions. 1.14 Example In this system x + y = 4 2x + 2y = 8 any pair of numbers satisfying the first equation automatically satisfies the second. The solution set {(x, y) ¯ ¯ x + y = 4} is infinite; some of its members are (0, 4), (−1, 5), and (2.5, 1.5). The result of applying Gauss’ method here contrasts with the prior example because we do not get a contradictory equation. −2ρ1+ρ2 −→ x + y = 4 0 = 0 Don’t be fooled by the ‘0 = 0’ equation in that example. It is not the signal that a system has many solutions
Chapter One.Linear Systems 1.15 Example The absence of a 0=0'does not keep a system from having many different solutions.This system is in echelon form x+y+z=0 y+2=0 has no 0=0',and yet has infinitely many solutions.(For instance,each of these is a solution:(0,1,-1),(0,1/2,-1/2),(0,0,0),and (0,-,m).There are infinitely many solutions because any triple whose first component is 0 and whose second component is the negative of the third is a solution.) Nor does the presence of a'0=0'mean that the system must have many solutions.Example 1.11 shows that.So does this system,which does not have many solutions-in fact it has none-despite that when it is brought to echelon form it has a'0=0'row. 2x 、-2z=6 2x-2z=6 y+z=1-P±p3 y+2=1 2x+y-z=7 y+2=1 3y+3z=0 3y+3z=0 2x-2z=6 -p2+P3 y+2=1 -3p2+P4 0=0 0=-3 We will finish this subsection with a summary of what we've seen so far about Gauss'method. Gauss'method uses the three row operations to set a system up for back substitution.If any step shows a contradictory equation then we can stop with the conclusion that the system has no solutions.If we reach echelon form without a contradictory equation,and each variable is a leading variable in its row,then the system has a unique solution and we find it by back substitution. Finally,if we reach echelon form without a contradictory equation,and there is not a unique solution (at least one variable is not a leading variable)then the system has many solutions. The next subsection deals with the third case-we will see how to describe the solution set of a system with many solutions. Exercises 1.16 Use Gauss'method to find the unique solution for each system. (a)2+3y=13 -之=0 x-y=-1(b)3x+y=1 -E十y+之=4 1.17 Use Gauss'method to solve each system or conclude 'many solutions'or 'no solutions
8 Chapter One. Linear Systems 1.15 Example The absence of a ‘0 = 0’ does not keep a system from having many different solutions. This system is in echelon form x + y + z = 0 y + z = 0 has no ‘0 = 0’, and yet has infinitely many solutions. (For instance, each of these is a solution: (0, 1, −1), (0, 1/2, −1/2), (0, 0, 0), and (0, −π, π). There are infinitely many solutions because any triple whose first component is 0 and whose second component is the negative of the third is a solution.) Nor does the presence of a ‘0 = 0’ mean that the system must have many solutions. Example 1.11 shows that. So does this system, which does not have many solutions — in fact it has none — despite that when it is brought to echelon form it has a ‘0 = 0’ row. 2x − 2z = 6 y + z = 1 2x + y − z = 7 3y + 3z = 0 −ρ1+ρ3 −→ 2x − 2z = 6 y + z = 1 y + z = 1 3y + 3z = 0 −ρ2+ρ3 −→ −3ρ2+ρ4 2x − 2z = 6 y + z = 1 0 = 0 0 = −3 We will finish this subsection with a summary of what we’ve seen so far about Gauss’ method. Gauss’ method uses the three row operations to set a system up for back substitution. If any step shows a contradictory equation then we can stop with the conclusion that the system has no solutions. If we reach echelon form without a contradictory equation, and each variable is a leading variable in its row, then the system has a unique solution and we find it by back substitution. Finally, if we reach echelon form without a contradictory equation, and there is not a unique solution (at least one variable is not a leading variable) then the system has many solutions. The next subsection deals with the third case — we will see how to describe the solution set of a system with many solutions. Exercises X 1.16 Use Gauss’ method to find the unique solution for each system. (a) 2x + 3y = 13 x − y = −1 (b) x − z = 0 3x + y = 1 −x + y + z = 4 X 1.17 Use Gauss’ method to solve each system or conclude ‘many solutions’ or ‘no solutions’
Section I.Solving Linear Systems 9 (a)2x+2y=5(b)-x+y=1(c)x-3y+z=1 x-4y=0 E+y=2 E+y+2z=14 (d)-x-y=1(e) 4g+z=20(f)2x+z+w=5 -3x-3y=2 2x-2y+z=0 y-w=-1 +z=5 3x-z-w=0 x+y-z=10 4红+y+2z+w= 9 V 1.18 There are methods for solving linear systems other than Gauss'method.One often taught in high school is to solve one of the equations for a variable,then substitute the resulting expression into other equations.That step is repeated until there is an equation with only one variable.From that,the first number in the solution is derived,and then back-substitution can be done.This method takes longer than Gauss'method,since it involves more arithmetic operations, and is also more likely to lead to errors.To illustrate how it can lead to wrong conclusions,we will use the system x+3y=1 2x+y=-3 2x+2y=0 from Example 1.12 (a)Solve the first equation for r and substitute that expression into the second equation.Find the resulting y. (b)Again solve the first equation for r,but this time substitute that expression into the third equation.Find this y. What extra step must a user of this method take to avoid erroneously concluding a system has a solution? v 1.19 For which values of k are there no solutions,many solutions,or a unique solution to this system? x-y=1 3x-3y=k 1.20 This system is not linear,in some sense, 2sin a-cosB+3tany=3 4sin a+2cos B-2tany=10 6sin a-3cosB+tany=9 and yet we can nonetheless apply Gauss'method.Do so.Does the system have a solution? 1.21 What conditions must the constants,the b's,satisfy so that each of these systems has a solution?Hint.Apply Gauss'method and see what happens to the right side.Anton] (a)x-3y=b1 (b)x1+2x2+3x3=b1 3红+y=b2 2x1+5x2+3x3=b2 I+7y=63 T1 +8T3=b3 2x+4y=b4 1.22 True or false:a system with more unknowns than equations has at least one solution.(As always,to say 'true'you must prove it,while to say'false'you must produce a counterexample.) 1.23 Must any Chemistry problem like the one that starts this subsection-a bal- ance the reaction problem-have infinitely many solutions? 1.24 Find the coefficients a,b,and c so that the graph of f(r)=ax2+bx+c passes through the points (1,2),(-1,6),and (2,3)
Section I. Solving Linear Systems 9 (a) 2x + 2y = 5 x − 4y = 0 (b) −x + y = 1 x + y = 2 (c) x − 3y + z = 1 x + y + 2z = 14 (d) −x − y = 1 −3x − 3y = 2 (e) 4y + z = 20 2x − 2y + z = 0 x + z = 5 x + y − z = 10 (f) 2x + z + w = 5 y − w = −1 3x − z − w = 0 4x + y + 2z + w = 9 X 1.18 There are methods for solving linear systems other than Gauss’ method. One often taught in high school is to solve one of the equations for a variable, then substitute the resulting expression into other equations. That step is repeated until there is an equation with only one variable. From that, the first number in the solution is derived, and then back-substitution can be done. This method takes longer than Gauss’ method, since it involves more arithmetic operations, and is also more likely to lead to errors. To illustrate how it can lead to wrong conclusions, we will use the system x + 3y = 1 2x + y = −3 2x + 2y = 0 from Example 1.12. (a) Solve the first equation for x and substitute that expression into the second equation. Find the resulting y. (b) Again solve the first equation for x, but this time substitute that expression into the third equation. Find this y. What extra step must a user of this method take to avoid erroneously concluding a system has a solution? X 1.19 For which values of k are there no solutions, many solutions, or a unique solution to this system? x − y = 1 3x − 3y = k X 1.20 This system is not linear, in some sense, 2 sin α − cos β + 3 tan γ = 3 4 sin α + 2 cos β − 2 tan γ = 10 6 sin α − 3 cos β + tan γ = 9 and yet we can nonetheless apply Gauss’ method. Do so. Does the system have a solution? X 1.21 What conditions must the constants, the b’s, satisfy so that each of these systems has a solution? Hint. Apply Gauss’ method and see what happens to the right side. [Anton] (a) x − 3y = b1 3x + y = b2 x + 7y = b3 2x + 4y = b4 (b) x1 + 2x2 + 3x3 = b1 2x1 + 5x2 + 3x3 = b2 x1 + 8x3 = b3 1.22 True or false: a system with more unknowns than equations has at least one solution. (As always, to say ‘true’ you must prove it, while to say ‘false’ you must produce a counterexample.) 1.23 Must any Chemistry problem like the one that starts this subsection — a balance the reaction problem — have infinitely many solutions? X 1.24 Find the coefficients a, b, and c so that the graph of f(x) = ax2 +bx+c passes through the points (1, 2), (−1, 6), and (2, 3)
10 Chapter One.Linear Systems 1.25 Gauss'method works by combining the equations in a system to make new equations. (a)Can the equation 3r-2y=5 be derived,by a sequence of Gaussian reduction steps,from the equations in this system? x+y=1 4x-y=6 (b)Can the equation 5r-3y =2 be derived,by a sequence of Gaussian reduction steps,from the equations in this system? 2x+2y=5 3x+y=4 (c)Can the equation 6x-9y+5z=-2 be derived,by a sequence of Gaussian reduction steps,from the equations in the system? 2x+y-z=4 6x-3y+z=5 1.26 Prove that,where a,b,...,e are real numbers and a0,if ar+by=c has the same solution set as ax dy =e then they are the same equation.What if a =0? 1.27 Show that if ad-bc0 then ax+by=j cx+dy=k has a unique solution. 1.28 In the system ax+by=c dx+ey=f each of the equations describes a line in the ry-plane.By geometrical reasoning, show that there are three possibilities:there is a unique solution,there is no solution,and there are infinitely many solutions. 1.29 Finish the proof of Theorem 1.4. 1.30 Is there a two-unknowns linear system whose solution set is all of R2? 1.31 Are any of the operations used in Gauss'method redundant?That is,can any of the operations be synthesized from the others? 1.32 Prove that each operation of Gauss'method is reversible.That is,show that if two systems are related by a row operation S1-S2 then there is a row operation to go back S2一S1. 1.33 A box holding pennies,nickels and dimes contains thirteen coins with a total value of 83 cents.How many coins of each type are in the box?[Anton] 1.34 Four positive integers are given.Select any three of the integers,find their arithmetic average,and add this result to the fourth integer.Thus the numbers 29,23,21,and 17 are obtained.One of the original integers is:
10 Chapter One. Linear Systems 1.25 Gauss’ method works by combining the equations in a system to make new equations. (a) Can the equation 3x−2y = 5 be derived, by a sequence of Gaussian reduction steps, from the equations in this system? x + y = 1 4x − y = 6 (b) Can the equation 5x−3y = 2 be derived, by a sequence of Gaussian reduction steps, from the equations in this system? 2x + 2y = 5 3x + y = 4 (c) Can the equation 6x − 9y + 5z = −2 be derived, by a sequence of Gaussian reduction steps, from the equations in the system? 2x + y − z = 4 6x − 3y + z = 5 1.26 Prove that, where a, b, . . . , e are real numbers and a 6= 0, if ax + by = c has the same solution set as ax + dy = e then they are the same equation. What if a = 0? X 1.27 Show that if ad − bc 6= 0 then ax + by = j cx + dy = k has a unique solution. X 1.28 In the system ax + by = c dx + ey = f each of the equations describes a line in the xy-plane. By geometrical reasoning, show that there are three possibilities: there is a unique solution, there is no solution, and there are infinitely many solutions. 1.29 Finish the proof of Theorem 1.4. 1.30 Is there a two-unknowns linear system whose solution set is all of R 2 ? X 1.31 Are any of the operations used in Gauss’ method redundant? That is, can any of the operations be synthesized from the others? 1.32 Prove that each operation of Gauss’ method is reversible. That is, show that if two systems are related by a row operation S1 → S2 then there is a row operation to go back S2 → S1. ? 1.33 A box holding pennies, nickels and dimes contains thirteen coins with a total value of 83 cents. How many coins of each type are in the box? [Anton] ? 1.34 Four positive integers are given. Select any three of the integers, find their arithmetic average, and add this result to the fourth integer. Thus the numbers 29, 23, 21, and 17 are obtained. One of the original integers is:
Section I.Solving Linear Systems 11 (a)19(b)21(c)23(d)29(e)17 [Con.Prob.1955 ?1.35 Laugh at this:AHAHA TEHE TEHAW.It resulted from substituting a code letter for each digit of a simple example in addition,and it is required to identify the letters and prove the solution unique.[Am.Math.Mon.,Jan.1935] 1.36 The Wohascum County Board of Commissioners,which has 20 members,re- cently had to elect a President.There were three candidates (A,B,and C);on each ballot the three candidates were to be listed in order of preference,with no abstentions.It was found that 11 members,a majority,preferred A over B(thus the other 9 preferred B over A).Similarly,it was found that 12 members preferred C over A.Given these results,it was suggested that B should withdraw,to enable a runoff election between A and C.However,B protested,and it was then found that 14 members preferred B over C!The Board has not yet recovered from the re- sulting confusion.Given that every possible order of A,B,C appeared on at least one ballot,how many members voted for B as their first choice?[Wohascum no.2] 1.37 "This system of n linear equations with n unknowns,"said the Great Math- ematician,"has a curious property." "Good heavens!"said the Poor Nut,"What is it?" "Note,"said the Great Mathematician,"that the constants are in arithmetic progression." "It's all so clear when you explain it!"said the Poor Nut."Do you mean like 6x+9y=12and15x+18y=21?m "Quite so,"said the Great Mathematician,pulling out his bassoon."Indeed, the system has a unique solution.Can you find it?" "Good heavens!"cried the Poor Nut,"I am baffled." Are you?[Am.Math.Mon.,Jan.1963] I.2 Describing the Solution Set A linear system with a unique solution has a solution set with one element.A linear system with no solution has a solution set that is empty.In these cases the solution set is easy to describe.Solution sets are a challenge to describe only when they contain many elements. 2.1 Example This system has many solutions because in echelon form 2x+z=3 -(1/2)P1+P2 2x+ z=3 x-y-z=1 -y-(3/2)z=-1/2 3z-y=4 -(3/2)p1+pg -y-(3/2)z=-1/2 2x+z=3 -p2+p3 -y-(3/2)z=-1/2 0=0 not all of the variables are leading variables.The Gauss'method theorem showed that a triple satisfies the first system if and only if it satisfies the third. Thus,the solution set {(y,2)2x+z=3 and x-y-z 1 and 3x-y=4}
Section I. Solving Linear Systems 11 (a) 19 (b) 21 (c) 23 (d) 29 (e) 17 [Con. Prob. 1955] ? X 1.35 Laugh at this: AHAHA + TEHE = TEHAW. It resulted from substituting a code letter for each digit of a simple example in addition, and it is required to identify the letters and prove the solution unique. [Am. Math. Mon., Jan. 1935] ? 1.36 The Wohascum County Board of Commissioners, which has 20 members, recently had to elect a President. There were three candidates (A, B, and C); on each ballot the three candidates were to be listed in order of preference, with no abstentions. It was found that 11 members, a majority, preferred A over B (thus the other 9 preferred B over A). Similarly, it was found that 12 members preferred C over A. Given these results, it was suggested that B should withdraw, to enable a runoff election between A and C. However, B protested, and it was then found that 14 members preferred B over C! The Board has not yet recovered from the resulting confusion. Given that every possible order of A, B, C appeared on at least one ballot, how many members voted for B as their first choice? [Wohascum no. 2] ? 1.37 “This system of n linear equations with n unknowns,” said the Great Mathematician, “has a curious property.” “Good heavens!” said the Poor Nut, “What is it?” “Note,” said the Great Mathematician, “that the constants are in arithmetic progression.” “It’s all so clear when you explain it!” said the Poor Nut. “Do you mean like 6x + 9y = 12 and 15x + 18y = 21?” “Quite so,” said the Great Mathematician, pulling out his bassoon. “Indeed, the system has a unique solution. Can you find it?” “Good heavens!” cried the Poor Nut, “I am baffled.” Are you? [Am. Math. Mon., Jan. 1963] I.2 Describing the Solution Set A linear system with a unique solution has a solution set with one element. A linear system with no solution has a solution set that is empty. In these cases the solution set is easy to describe. Solution sets are a challenge to describe only when they contain many elements. 2.1 Example This system has many solutions because in echelon form 2x + z = 3 x − y − z = 1 3x − y = 4 −(1/2)ρ1+ρ2 −→ −(3/2)ρ1+ρ3 2x + z = 3 −y − (3/2)z = −1/2 −y − (3/2)z = −1/2 −ρ2+ρ3 −→ 2x + z = 3 −y − (3/2)z = −1/2 0 = 0 not all of the variables are leading variables. The Gauss’ method theorem showed that a triple satisfies the first system if and only if it satisfies the third. Thus, the solution set {(x, y, z) ¯ ¯ 2x + z = 3 and x − y − z = 1 and 3x − y = 4}