Lecture notes in linear algebra pdf

advanced linear algebra lecture notes pdf and linear algebra vector spaces lecture notes, lecture notes on elementary linear algebra lecture notes on probability statistics and linear algebra
Prof.SteveBarros Profile Pic
Prof.SteveBarros,United Kingdom,Teacher
Published Date:28-07-2017
Your Website URL(Optional)
Comment
LINEARALGEBRA JimHefferon Thirdedition http://joshua.smcvt.edu/linearalgebraContents Chapter One: Linear Systems I Solving Linear Systems . . . . . . . . . . . . . . . . . . . . . . . . 1 I.1 Gauss’s Method . . . . . . . . . . . . . . . . . . . . . . . . . 2 I.2 Describing the Solution Set . . . . . . . . . . . . . . . . . . . 13 I.3 General= Particular+Homogeneous . . . . . . . . . . . . . . 23 II Linear Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 II.1 Vectors in Space . . . . . . . . . . . . . . . . . . . . . . . . 35 II.2 Length and Angle Measures . . . . . . . . . . . . . . . . . . 42 III Reduced Echelon Form . . . . . . . . . . . . . . . . . . . . . . . . 50 III.1 Gauss-Jordan Reduction . . . . . . . . . . . . . . . . . . . . . 50 III.2 The Linear Combination Lemma . . . . . . . . . . . . . . . . 56 Topic: Computer Algebra Systems . . . . . . . . . . . . . . . . . . . 65 Topic: Accuracy of Computations . . . . . . . . . . . . . . . . . . . . 67 Topic: Analyzing Networks . . . . . . . . . . . . . . . . . . . . . . . . 71 Chapter Two: Vector Spaces I Definition of Vector Space . . . . . . . . . . . . . . . . . . . . . . 78 I.1 Definition and Examples . . . . . . . . . . . . . . . . . . . . 78 I.2 Subspaces and Spanning Sets . . . . . . . . . . . . . . . . . . 90 II Linear Independence . . . . . . . . . . . . . . . . . . . . . . . . . 101 II.1 Definition and Examples . . . . . . . . . . . . . . . . . . . . 101 III Basis and Dimension . . . . . . . . . . . . . . . . . . . . . . . . . 114 III.1 Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 III.2 Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 III.3 Vector Spaces and Linear Systems . . . . . . . . . . . . . . . 127 III.4 Combining Subspaces . . . . . . . . . . . . . . . . . . . . . . 135 Topic: Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144Topic: Crystals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 Topic: Voting Paradoxes . . . . . . . . . . . . . . . . . . . . . . . . . 150 Topic: Dimensional Analysis . . . . . . . . . . . . . . . . . . . . . . . 156 Chapter Three: Maps Between Spaces I Isomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 I.1 Definition and Examples . . . . . . . . . . . . . . . . . . . . 165 I.2 Dimension Characterizes Isomorphism . . . . . . . . . . . . . 175 II Homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 II.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 II.2 Range space and Null space . . . . . . . . . . . . . . . . . . . 191 III Computing Linear Maps . . . . . . . . . . . . . . . . . . . . . . . 204 III.1 Representing Linear Maps with Matrices . . . . . . . . . . . 204 III.2 Any Matrix Represents a Linear Map . . . . . . . . . . . . . 215 IV Matrix Operations . . . . . . . . . . . . . . . . . . . . . . . . . . 224 IV.1 Sums and Scalar Products . . . . . . . . . . . . . . . . . . . . 224 IV.2 Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . 228 IV.3 Mechanics of Matrix Multiplication . . . . . . . . . . . . . . 237 IV.4 Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 V Change of Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 V.1 Changing Representations of Vectors . . . . . . . . . . . . . . 254 V.2 Changing Map Representations . . . . . . . . . . . . . . . . . 259 VI Projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 VI.1 Orthogonal Projection Into a Line . . . . . . . . . . . . . . 267 VI.2 Gram-Schmidt Orthogonalization . . . . . . . . . . . . . . . 272 VI.3 Projection Into a Subspace . . . . . . . . . . . . . . . . . . . 277 Topic: Line of Best Fit . . . . . . . . . . . . . . . . . . . . . . . . . . 287 Topic: Geometry of Linear Maps . . . . . . . . . . . . . . . . . . . . 293 Topic: Magic Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 Topic: Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . . . 305 Topic: Orthonormal Matrices . . . . . . . . . . . . . . . . . . . . . . 311 Chapter Four: Determinants I Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 I.1 Exploration . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 I.2 Properties of Determinants . . . . . . . . . . . . . . . . . . . 323 I.3 The Permutation Expansion . . . . . . . . . . . . . . . . . . 328 I.4 Determinants Exist . . . . . . . . . . . . . . . . . . . . . . . 338 II Geometry of Determinants . . . . . . . . . . . . . . . . . . . . . . 346 II.1 Determinants as Size Functions . . . . . . . . . . . . . . . . . 346 III Laplace’s Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . 353 III.1 Laplace’s Expansion . . . . . . . . . . . . . . . . . . . . . . 353 Topic: Cramer’s Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 Topic: Speed of Calculating Determinants . . . . . . . . . . . . . . . 362 Topic: Chiò’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 366 Topic: Projective Geometry . . . . . . . . . . . . . . . . . . . . . . . 370 Chapter Five: Similarity I Complex Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . 383 I.1 Polynomial Factoring and Complex Numbers . . . . . . . . 384 I.2 Complex Representations . . . . . . . . . . . . . . . . . . . . 386 II Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388 II.1 Definition and Examples . . . . . . . . . . . . . . . . . . . . 388 II.2 Diagonalizability . . . . . . . . . . . . . . . . . . . . . . . . . 393 II.3 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . 397 III Nilpotence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 III.1 Self-Composition . . . . . . . . . . . . . . . . . . . . . . . . 408 III.2 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412 IV Jordan Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 IV.1 Polynomials of Maps and Matrices . . . . . . . . . . . . . . 423 IV.2 Jordan Canonical Form . . . . . . . . . . . . . . . . . . . . . 431 Topic: Method of Powers . . . . . . . . . . . . . . . . . . . . . . . . . 446 Topic: Stable Populations . . . . . . . . . . . . . . . . . . . . . . . . 450 Topic: Page Ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . 452 Topic: Linear Recurrences . . . . . . . . . . . . . . . . . . . . . . . . 456 Topic: Coupled Oscillators . . . . . . . . . . . . . . . . . . . . . . . . 464 Appendix Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A-1 Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A-2 Techniques of Proof . . . . . . . . . . . . . . . . . . . . . . . . . . A-3 Sets, Functions, and Relations . . . . . . . . . . . . . . . . . . . . . A-5  Starred subsections are optional.ChapterOne Linear Systems I Solving Linear Systems Systems of linear equations are common in science and mathematics. These two examples from high school science Onan give a sense of how they arise. The first example is from Statics. Suppose that we have three objects, we know that one has a mass of 2 kg, and we want to find the two unknown masses. Experimentation with a meter stick produces these two balances. 40 50 25 50 c c 2 2 h h 15 25 For the masses to balance we must have that the sum of moments on the left equals the sum of moments on the right, where the moment of an object is its mass times its distance from the balance point. That gives a system of two linear equations. 40h+15c=100 25c=50+50h The second example is from Chemistry. We can mix, under controlled conditions, toluene C H and nitric acid HNO to produce trinitrotoluene 7 8 3 C H O N along with the byproduct water (conditions have to be very well 7 5 6 3 controlled—trinitrotoluene is better known as TNT). In what proportion should we mix them? The number of atoms of each element present before the reaction xC H + yHNO zC H O N + wH O 7 8 3 7 5 6 3 22 Chapter One. Linear Systems must equal the number present afterward. Applying that in turn to the elements C, H, N, and O gives this system. 7x=7z 8x+1y=5z+2w 1y=3z 3y=6z+1w Both examples come down to solving a system of equations. In each system, the equations involve only the first power of each variable. This chapter shows how to solve any such system of equations. I.1 Gauss’s Method 1.1 Definition A linear combination ofx , ...,x has the form 1 n a x +a x +a x ++a x 1 1 2 2 3 3 n n where the numbersa ;:::;a 2R are the combination’s coefficients. A linear 1 n equation in the variablesx , ...,x has the forma x +a x +a x ++ 1 n 1 1 2 2 3 3 a x =d whered2R is the constant. n n n Ann-tuple (s ;s ;:::;s )2R is a solution of, or satisfies, that equation 1 2 n if substituting the numberss , ...,s for the variables gives a true statement: 1 n a s +a s ++a s =d. A system of linear equations 1 1 2 2 n n a x + a x ++ a x = d 1;1 1 1;2 2 1;n n 1 a x + a x ++ a x = d 2;1 1 2;2 2 2;n n 2 . . . a x +a x ++a x = d m;1 1 m;2 2 m;n n m has the solution(s ;s ;:::;s ) if thatn-tuple is a solution of all of the equations. 1 2 n 1.2 Example The combination3x +2x ofx andx is linear. The combination 1 2 1 2 2 3x +2x is not a linear function ofx andx , nor is3x +2sin(x ). 2 1 2 1 2 1 We usually take x , ..., x to be unequal to each other because in a 1 n sum with repeats we can rearrange to make the elements unique, as with 2x+3y+4x=6x+3y. We sometimes include terms with a zero coefficient, as inx-2y+0z, and at other times omit them, depending on what is convenient.Section I. Solving Linear Systems 3 1.3 Example The ordered pair (-1;5) is a solution of this system. 3x +2x =7 1 2 -x + x =6 1 2 In contrast, (5;-1) is not a solution. Findingthesetofallsolutionsissolving thesystem. Wedon’tneedguesswork or good luck, there is an algorithm that always works. This algorithm is Gauss’s Method (or Gaussian elimination or linear elimination). 1.4 Example To solve this system 3x =9 3 x +5x -2x =2 1 2 3 1 x +2x =3 1 2 3 we transform it, step by step, until it is in a form that we can easily solve. The first transformation rewrites the system by interchanging the first and third row. 1 x +2x =3 1 2 3 swap row 1 with row 3 x +5x -2x =2 1 2 3 3x =9 3 The second transformation rescales the first row by a factor of3. x +6x =9 1 2 multiply row 1 by 3 x +5x -2x =2 1 2 3 3x =9 3 The third transformation is the only nontrivial one in this example. We mentally multiply both sides of the first row by -1, mentally add that to the second row, and write the result in as the new second row. x + 6x = 9 1 2 add -1 times row 1 to row 2 -x -2x =-7 2 3 3x = 9 3 These steps have brought the system to a form where we can easily find the value of each variable. The bottom equation shows thatx =3. Substituting3 3 forx in the middle equation shows thatx =1. Substituting those two into 3 2 the top equation gives thatx =3. Thus the system has a unique solution; the 1 solution set is f(3;1;3)g. We will use Gauss’s Method throughout the book. It is fast and easy. We will now show that it is also safe: Gauss’s Method never loses solutions nor does it ever pick up extraneous solutions, so that a tuple is a solution to the system before we apply the method if and only if it is a solution after.4 Chapter One. Linear Systems 1.5 Theorem (Gauss’s Method) If a linear system is changed to another by one of these operations (1) an equation is swapped with another (2) an equation has both sides multiplied by a nonzero constant (3) an equation is replaced by the sum of itself and a multiple of another then the two systems have the same set of solutions. Each of the three operations has a restriction. Multiplying a row by0 is not allowed because obviously that can change the solution set. Similarly, adding a multiple of a row to itself is not allowed because adding -1 times the row to itself has the effect of multiplying the row by0. And we disallow swapping a row with itself, to make some results in the fourth chapter easier. Besides, it’s pointless. Proof We will cover the equation swap operation here. The other two cases are similar and are Exercise 33. Consider a linear system. a x + a x ++ a x = d 1;1 1 1;2 2 1;n n 1 . . . a x + a x ++ a x = d i;1 1 i;2 2 i;n n i . . . a x + a x ++ a x = d j;1 1 j;2 2 j;n n j . . . a x +a x ++a x = d m;1 1 m;2 2 m;n n m The tuple (s ;:::;s ) satisfies this system if and only if substituting the values 1 n for the variables, the s’s for the x’s, gives a conjunction of true statements: a s +a s ++a s =d and ... a s +a s ++a s =d and 1;1 1 1;2 2 1;n n 1 i;1 1 i;2 2 i;n n i ... a s +a s ++a s =d and ... a s +a s ++a s = j;1 1 j;2 2 j;n n j m;1 1 m;2 2 m;n n d . m In a list of statements joined with ‘and’ we can rearrange the order of the statements. Thus this requirement is met if and only ifa s +a s ++ 1;1 1 1;2 2 a s =d and ... a s +a s ++a s =d and ... a s +a s + 1;n n 1 j;1 1 j;2 2 j;n n j i;1 1 i;2 2 +a s =d and ... a s +a s ++a s =d . This is exactly i;n n i m;1 1 m;2 2 m;n n m the requirement that (s ;:::;s ) solves the system after the row swap. QED 1 nSection I. Solving Linear Systems 5 1.6 Definition The three operations from Theorem 1.5 are the elementary re- duction operations, or row operations, or Gaussian operations. They are swapping, multiplying by a scalar (or rescaling), and row combination. When writing out the calculations, we will abbreviate ‘row i’ by ‘ ’. For i instance, we will denote a row combination operation byk + , with the row i j that changes written second. To save writing we will often combine addition steps when they use the same , as in the next example. i 1.7 Example Gauss’s Method systematically applies the row operations to solve a system. Here is a typical case. x+ y =0 2x- y+3z=3 x-2y- z=3 We begin by using the first row to eliminate the2x in the second row and thex in the third. To get rid of the2x we mentally multiply the entire first row by -2, add that to the second row, and write the result in as the new second row. To eliminate thex in the third row we multiply the first row by -1, add that to the third row, and write the result in as the new third row. x+ y =0 -2 + 1 2 -3y+3z=3 - + 1 3 -3y- z=3 We finish by transforming the second system into a third, where the bottom equation involves only one unknown. We do that by using the second row to eliminate they term from the third row. x+ y =0 - + 2 3 -3y+ 3z=3 -4z=0 Now finding the system’s solution is easy. The third row givesz=0. Substitute that back into the second row to gety=-1. Then substitute back into the first row to getx=1. 1.8 Example For the Physics problem from the start of this chapter, Gauss’s Method gives this. 40h+15c=100 5=4 + 40h+ 15c=100 1 2 -50h+25c= 50 (175=4)c=175 Soc=4, and back-substitution gives thath=1. (We will solve the Chemistry problem later.)6 Chapter One. Linear Systems 1.9 Example The reduction x+ y+ z=9 x+ y+ z= 9 -2 + 1 2 2x+4y-3z=1 2y-5z=-17 -3 + 1 3 3x+6y-5z=0 3y-8z=-27 x+ y+ z= 9 -(3=2) + 2 3 2y- 5z= -17 -(1=2)z=-(3=2) shows thatz=3,y=-1, andx=7. As illustrated above, the point of Gauss’s Method is to use the elementary reduction operations to set up back-substitution. 1.10Definition In each row of a system, the first variable with a nonzero coefficient is the row’s leading variable. A system is in echelon form if each leading variable is to the right of the leading variable in the row above it, except for the leading variable in the first row, and any all-zero rows are at the bottom. 1.11 Example The prior three examples only used the operation of row combina- tion. This linear system requires the swap operation to get it into echelon form because after the first combination x- y =0 x-y =0 2x-2y+ z+2w=4 -2 + z+2w=4 1 2 y + w=0 y + w=0 2z+ w=5 2z+ w=5 the second equation has no leadingy. We exchange it for a lower-down row that has a leadingy. x-y =0   y + w=0 2 3 z+2w=4 2z+ w=5 (Had there been more than one suitable row below the second then we could have used any one.) With that, Gauss’s Method proceeds as before. x-y = 0 -2 + y + w= 0 3 4 z+ 2w= 4 -3w=-3 Back-substitution givesw=1,z=2 ,y=-1, andx=-1.Section I. Solving Linear Systems 7 Strictly speaking, to solve linear systems we don’t need the row rescaling operation. We have introduced it here because it is convenient and because we will use it later in this chapter as part of a variation of Gauss’s Method, the Gauss-Jordan Method. All of the systems so far have the same number of equations as unknowns. All of them have a solution and for all of them there is only one solution. We finish this subsection by seeing other things that can happen. 1.12 Example This system has more equations than variables. x+3y= 1 2x+ y=-3 2x+2y=-2 Gauss’s Method helps us understand this system also, since this x+ 3y= 1 -2 + 1 2 -5y=-5 -2 + 1 3 -4y=-4 shows that one of the equations is redundant. Echelon form x+ 3y= 1 -(4=5) + 2 3 -5y=-5 0= 0 gives thaty=1 andx=-2. The ‘0=0’ reflects the redundancy. Gauss’s Method is also useful on systems with more variables than equations. The next subsection has many examples. Another way that linear systems can differ from the examples shown above is that some linear systems do not have a unique solution. This can happen in two ways. The first is that a system can fail to have any solution at all. 1.13 Example Contrast the system in the last example with this one. x+3y= 1 x+ 3y= 1 -2 + 1 2 2x+ y=-3 -5y=-5 -2 + 1 3 2x+2y= 0 -4y=-2 Here the system is inconsistent: no pair of numbers (s ;s ) satisfies all three 1 2 equations simultaneously. Echelon form makes the inconsistency obvious. x+ 3y= 1 -(4=5) + 2 3 -5y=-5 0= 2 The solution set is empty.8 Chapter One. Linear Systems 1.14 Example The prior system has more equations than unknowns but that is not what causes the inconsistency—Example 1.12 has more equations than unknowns and yet is consistent. Nor is having more equations than unknowns necessary for inconsistency, as we see with this inconsistent system that has the same number of equations as unknowns. x+2y=8 -2 + x+2y= 8 1 2 2x+4y=8 0=-8 Instead, inconsistency has to do with the interaction of the left and right sides; in the first system above the left side’s second equation is twice the first but the right side’s second constant is not twice the first. Later we will have more to say about dependencies between a system’s parts. The other way that a linear system can fail to have a unique solution, besides having no solutions, is to have many solutions. 1.15 Example In this system x+ y=4 2x+2y=8 any pair of numbers satisfying the first equation also satisfies the second. The solution setf(x;y)jx+y=4g is infinite; some example member pairs are (0;4), (-1;5), and (2:5;1:5). The result of applying Gauss’s Method here contrasts with the prior example because we do not get a contradictory equation. x+y=4 -2 + 1 2 0=0 Don’t be fooled by that example: a0=0 equation is not the signal that a system has many solutions. 1.16 Example The absence of a0=0 equation does not keep a system from having many different solutions. This system is in echelon form, has no 0 = 0, but has infinitely many solutions, including (0;1;-1), (0;1=2;-1=2), (0;0;0), and (0;-;) (any triple whose first component is0 and whose second component is the negative of the third is a solution). x+y+z=0 y+z=0 Nor does the presence of 0 = 0 mean that the system must have many solutions. Example 1.12 shows that. So does this system, which does not haveSection I. Solving Linear Systems 9 any solutions at all despite that in echelon form it has a0=0 row. 2x -2z=6 2x -2z=6 y+ z=1 - + y+ z=1 1 3 2x+ y- z=7 y+ z=1 3y+3z=0 3y+3z=0 2x -2z= 6 - + y+ z= 1 2 3 -3 + 0= 0 2 4 0=-3 In summary, Gauss’s Method uses the 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—that is, at least one variable is not a leading variable— then the system has many solutions. The next subsection explores the third case. We will see that such a system must have infinitely many solutions and we will describe the solution set. Note. In the exercises here, and in the rest of the book, you must justify all of your answers. For instance, if a question asks whether a system has a solution then you must justify a yes response by producing the solution and must justify a no response by showing that no solution exists. Exercises X 1.17 Use Gauss’s Method to find the unique solution for each system. (a) 2x+3y= 13 (b) x -z=0 x- y=-1 3x+y =1 -x+y+z=4 1.18 Each system is in echelon form. For each, say whether the system has a unique solution, no solution, or infinitely many solutions. (a) -3x+ 2y=0 (b) x+y =4 (c) x+y =4 (d) x+y=4 -2y=0 y-z=0 y -z=0 0=4 0=0 (e) 3x+6y+ z=-0:5 (f) x-3y=2 (g) 2x+2y=4 (h) 2x+y=0 -z= 2:5 0=0 y=1 0=4 (i) x-y=-1 (j) x+y-3z=-1 0= 0 y- z= 2 0= 4 z= 0 0= 010 Chapter One. Linear Systems X 1.19 Use Gauss’s Method to solve each system or conclude ‘many solutions’ or ‘no solutions’. (a) 2x+2y=5 (b) -x+y=1 (c) x-3y+ z= 1 (d) -x- y=1 x-4y=0 x+y=2 x+ y+2z=14 -3x-3y=2 (e) 4y+z=20 (f) 2x + z+w= 5 2x-2y+z= 0 y -w=-1 x +z= 5 3x - z-w= 0 x+ y-z=10 4x+y+2z+w= 9 1.20 Solve each system or conclude ‘many solutions’ or ‘no solutions’. Use Gauss’s Method. (a) x+y+ z=5 (b) 3x + z= 7 (c) x+3y+ z=0 x-y =0 x- y+3z= 4 -x- y =2 y+2z=7 x+2y-5z=-1 -x+ y+2z=8 X 1.21 We can solve linear systems by methods other than Gauss’s. One often taught in high school is to solve one of the equations for a variable, then substitute the resulting expression into other equations. Then we repeat that step until there is an equation with only one variable. From that we get the first number in the solution and then we get the rest with back-substitution. This method takes longer than Gauss’s 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.13. (a) Solve the first equation forx and substitute that expression into the second equation. Find the resultingy. (b) Again solve the first equation forx, but this time substitute that expression into the third equation. Find thisy. What extra step must a user of this method take to avoid erroneously concluding a system has a solution? X 1.22 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.23 This system is not linear in that it says sin instead of 2sin - cos +3tan = 3 4sin +2cos -2tan =10 6sin -3cos + tan = 9 and yet we can apply Gauss’s Method. Do so. Does the system have a solution? X 1.24 What conditions must the constants, the b’s, satisfy so that each of these systems has a solution? Hint. Apply Gauss’s Method and see what happens to the right side.Section I. Solving Linear Systems 11 (a) x-3y=b (b) x +2x +3x =b 1 1 2 3 1 3x+ y=b 2x +5x +3x =b 2 1 2 3 2 x+7y=b x +8x =b 3 1 3 3 2x+4y=b 4 1.25 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.26 Must any Chemistry problem like the one that starts this subsection—a balance the reaction problem—have infinitely many solutions? 2 X 1.27 Find the coefficientsa,b, andc so that the graph off(x)=ax +bx+c passes through the points (1;2), (-1;6), and (2;3). 1.28 After Theorem 1.5 we note that multiplying a row by0 is not allowed because that could change a solution set. Give an example of a system with solution setS 0 where after multiplying a row by0 the new system has a solution setS andS is 1 0 a proper subset ofS , that is,S =6 S . Give an example whereS =S . 1 0 1 0 1 1.29 Gauss’s Method works by combining the equations in a system to make new equations. (a) Can we derive the equation3x-2y=5 by a sequence of Gaussian reduction steps from the equations in this system? x+y=1 4x-y=6 (b) Can we derive the equation5x-3y=2 with a sequence of Gaussian reduction steps from the equations in this system? 2x+2y=5 3x+ y=4 (c) Can we derive6x-9y+5z=-2 by a sequence of Gaussian reduction steps from the equations in the system? 2x+ y-z=4 6x-3y+z=5 1.30 Prove that, wherea;b;c;d;e are real numbers witha6=0, if this linear equation ax+by=c has the same solution set as this one ax+dy=e then they are the same equation. What ifa=0? 1.31 Show that ifad-bc=6 0 then ax+by= j cx+dy=k has a unique solution. X 1.32 In the system ax+by=c dx+ey=f each of the equations describes a line in thexy-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.12 Chapter One. Linear Systems 1.33 Finish the proof of Theorem 1.5. 2 1.34 Is there a two-unknowns linear system whose solution set is all of R ? X 1.35 Are any of the operations used in Gauss’s Method redundant? That is, can we make any of the operations from a combination of the others? 1.36 Prove that each operation of Gauss’s Method is reversible. That is, show that if two systems are related by a row operationS S then there is a row operation 1 2 to go backS S . 2 1 ? 1.37 Anton A box holding pennies, nickels and dimes contains thirteen coins with a total value of83 cents. How many coins of each type are in the box? (These are US coins; a penny is1 cent, a nickel is5 cents, and a dime is10 cents.) ? 1.38 Con. Prob. 1955 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: (a) 19 (b) 21 (c) 23 (d) 29 (e) 17 ? 1.39 Am. Math. Mon., Jan. 1935 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. ? 1.40 Wohascum no. 2 The Wohascum County Board of Commissioners, which has 20 members, recently had to elect a President. There were three candidates (A,B, andC); 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, preferredA over B (thus the other 9 preferredB overA). Similarly, it was found that 12 members preferredC overA. Given these results, it was suggested thatB should withdraw, to enable a runoff election between A andC. However, B protested, and it was then found that 14 members preferredB overC The Board has not yet recovered from the resulting confusion. Given that every possible order ofA,B,C appeared on at least one ballot, how many members voted forB as their first choice? ? 1.41 Am. Math. Mon., Jan. 1963 “This system of n linear equations with n un- knowns,” 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 and15x+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?Section I. Solving Linear Systems 13 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 2x + z= 3 -(1=2) + 1 2 x-y-z=1 -y-(3=2)z=-1=2 -(3=2) + 1 3 3x-y =4 -y-(3=2)z=-1=2 2x + z= 3 - + 2 3 -y-(3=2)z=-1=2 0= 0 not all of the variables are leading variables. Theorem 1.5 shows that an (x;y;z) satisfies the first system if and only if it satisfies the third. So we can describe the solution set f(x;y;z)j2x+z=3 andx-y-z=1 and3x-y=4g in this way. f(x;y;z)j2x+z=3 and -y-3z=2=-1=2g () This description is better because it has two equations instead of three but it is not optimal because it still has some hard to understand interactions among the variables. To improve it, use the variable that does not lead any equation,z, to describe the variables that do lead,x andy. The second equation givesy=(1=2)-(3=2)z and the first equation givesx=(3=2)-(1=2)z. Thus we can describe the solution set as this set of triples. f((3=2)-(1=2)z; (1=2)-(3=2)z;z)jz2Rg () Compared with (), the advantage of () is thatz can be any real number. This makes the job of deciding which tuples are in the solution set much easier. For instance, takingz=2 shows that (1=2;-5=2;2) is a solution. 2.2 Definition In an echelon form linear system the variables that are not leading are free. 2.3 Example Reduction of a linear system can end with more than one variable14 Chapter One. Linear Systems free. Gauss’s Method on this system x+ y+ z- w= 1 x+ y+ z- w= 1 y- z+ w=-1 -3 + y- z+ w=-1 1 3 3x +6z-6w= 6 -3y+3z-3w= 3 -y+ z- w= 1 -y+ z- w= 1 x+y+z-w= 1 3 + y-z+w=-1 2 3  + 2 4 0= 0 0= 0 leavesx andy leading and bothz andw free. To get the description that we prefer, we work from the bottom. We first express the leading variabley in terms ofz andw, asy=-1+z-w. Moving up to the top equation, substituting for y givesx+(-1+z-w)+z-w=1 and solving forx leavesx=2-2z+2w. The solution set f(2-2z+2w;-1+z-w;z;w)jz;w2Rg () has the leading variables expressed in terms of the variables that are free. 2.4 Example The list of leading variables may skip over some columns. After this reduction 2x-2y =0 2x-2y =0 z+3w=2 -(3=2) + z+3w=2 1 3 3x-3y =0 -(1=2) + 0=0 1 4 x- y+2z+6w=4 2z+6w=4 2x-2y =0 -2 + z+3w=2 2 4 0=0 0=0 x andz are the leading variables, notx andy. The free variables arey andw and so we can describe the solution set as f(y;y;2-3w;w)jy;w2Rg. For instance, (1;1;2;0) satisfies the system—takey=1 andw=0. The four-tuple (1;0;5;4) is not a solution since its first coordinate does not equal its second. A variable that we use to describe a family of solutions is a parameter. We say that the solution set in the prior example is parametrized withy andw. The terms ‘parameter’ and ‘free variable’ do not mean the same thing. In the prior exampley andw are free because in the echelon form system they do not lead. They are parameters because we used them to describe the set of solutions. Had we instead rewritten the second equation asw=2=3-(1=3)z then the free variables would still bey andw but the parameters would bey andz.Section I. Solving Linear Systems 15 In the rest of this book we will solve linear systems by bringing them to echelon form and then parametrizing with the free variables. 2.5 Example This is another system with infinitely many solutions. x+2y =1 x+ 2y =1 -2 + 1 2 2x +z =2 -4y+z =0 -3 + 1 3 3x+2y+z-w=4 -4y+z-w=1 x+ 2y =1 - + 2 3 -4y+z =0 -w=1 The leading variables are x, y, and w. The variable z is free. Notice that, although there are infinitely many solutions, the value ofw doesn’t vary but is constantw=-1. To parametrize, writew in terms ofz withw=-1+0z. Theny = (1=4)z. Substitute fory in the first equation to getx =1-(1=2)z. The solution set is f(1-(1=2)z;(1=4)z;z;-1)jz2Rg. Parametrizing solution sets shows that systems with free variables have infinitely many solutions. For instance, abovez takes on all of infinitely many real number values, each associated with a different solution. We finish this subsection by developing a streamlined notation for linear systems and their solution sets. 2.6 Definition Anmn matrix is a rectangular array of numbers withm rows andn columns. Each number in the matrix is an entry. We usually denote a matrix with an upper case roman letters. For instance, 1 2:2 5 A= 3 4 -7 has2 rows and3 columns and so is a23 matrix. Read that aloud as “two-by- three”; the number of rows is always stated first. (The matrix has parentheses around it so that when two matrices are adjacent we can tell where one ends and the other begins.) We name matrix entries with the corresponding lower-case letter, so that the entry in the second row and first column of the above array isa =3. Note that the order of the subscripts matters: a =6 a since 2;1 1;2 2;1 a =2:2. We denote the set of allnm matrices by M . 1;2 nm We do Gauss’s Method using matrices in essentially the same way that we did it for systems of equations: a matrix row’s leading entry is its first nonzero entry (if it has one) and we perform row operations to arrive at matrix echelon form, where the leading entry in lower rows are to the right of those in the rows

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.