Solving Systems of Linear Equations PDF

I. Solving systems of linear equations What is it all about? It’s about formalising and generalizing problems that you’ve already solved in your life. Example Find the intersection point of the lines given by the following eq...

I. Solving systems of linear equations What is it all about? It’s about formalising and generalizing problems that you’ve already solved in your life. Example Find the intersection point of the lines given by the following equations: L1 : x2 = x1 − 2, L2 : x2 = − 12 x1 + 1. x2 L1 x1 L2 L1 and L2 are not parallel. What is the angle between L1 and L2 ? If I fix a point on L2 which is not on L1 , what is its distance from L1 ?... We will also see how to solve less abstract problems, but in a more systematic way than you are perhaps used to. Example (Balancing chemical equations) Consider a chemical equation CH4 + O2 → CO2 + H2 O. It tells us that methane and (diatomic) oxygen react to form carbon dioxide and water. This equation is not balanced. For example, there are 2 atoms of oxygen on the left and 3 on the right. Balancing the equation means finding positive integers x1 , x2 , x3 , x4 such that the following holds: If x1 molecules of methane react with x2 molecules of oxygen, then they form x3 molecules of carbon dioxide and x4 molecules of water. Systems of linear equations Definition 1 Let n be a positive integer and x1 ,... , xn variables. A linear equation in x1 ,... , xn is an equation of the form a1 x1 + · · · + an xn = b, (1) where a1 ,... , an , b are constants. 1  The constants will mostly be in R; occasionally in C. More generally, any equation that can be re-written as in (1) is a linear equation. E.g. 3x1 + 2 = 1 − x2 is a linear equation because 3x1 + 2 = 1 − x2 ⇔ 3x1 + x2 = −1. Question Is x2 = 1 is a linear equation in x? Definition 2 Let m ≥ 1 be an integer. A linear system of m equations in x1 ,... , xn is a set of m linear equations in variables x1 ,... , xn. We sometimes enclose a linear system by a curly bracket, to emphasise that we consider all its equations simultaneously. Example A linear system of two linear equations in x1 and x2 : ( x1 − x2 = 2 −13x1 + 13x2 = −26 Solving this linear system means finding all possible (α1 , α2 ) ∈ R2 satisfying both of these two equations. Solving a system of linear equations Solving a linear system means finding all possible (α1 , α2 ,... , αn ) ∈ Rn (or Cn ) such that the equations are all simultaneously satisfied if we substitute xi = αi for each i. Note: Here we are trying to find all ordered n-tuples (α1 , α2 ,... , αn ) ∈ Rn = R × R × · · · × R | {z } n times that satisfy the equations. The order of the αi is important. Example Compute the points in the intersection of the lines 1 L1 : x2 = x1 − 2, L2 : x2 = − x1 + 1. 2 (Answer: (x1 , x2 ) = (2, 0)) 2  Example Solve the system ( 3x1 + 3x2 = 5 −x1 = x2 Substituting the second equation into the first one: ( x1 = 53 − x2 5 5 ⇔ −x2 = − x2 ⇔ 0= x2 = −x1 3 3 So there are no solutions. Geometrically, the equations represent parallel lines. x2 x1 L2 : 3x1 + 3x2 = 5 L1 : −x1 = x2 Example Solve the system ( x1 − x2 = 2 −13x1 + 13x2 = −26 Multiplying the first equation by −13 we obtain the second one. Thus, the equations define the same line! And any point on the line is a solution. In particular, there are infinitely many solutions and these are all pairs (x1 , x2 ) with x1 , x2 ∈ R and x2 = x1 − 2. x2 x1 We have seen examples of a linear system with exactly one solution; a linear system with no solutions; a linear system with infinitely many solutions. Definition 3 We say that a linear system is consistent if it has at least one solution; inconsistent if it has no solutions. Since a non-trivial linear equation in two variables represents a line, we know from geometry that a linear system with 2 equations in 2 variables will have either 3  exactly one solution (if the lines are not parallel), no solutions (if the lines are parallel and distinct), or infinitely many solutions (if the lines coincide). As the number of variables and the number of equations grow, we want a more systematic way of studying linear systems. For example, how can we solve a linear system of the following general form: a11 x1 + · · · + a1n xn = b1 a21 x1 + · · · + a2n xn = b2... am1 x1 + · · · + amn xn = bm The constants determine the system completely, which suggests we should represent a system in a more concise form. Matrices and vectors Definition 4 A matrix is a rectangular array of numbers. If a matrix has m rows and n columns, it is said to have size m × n. 7 1 12 5/6   Example 0 2 0 9  is a 3 × 4 matrix. 0 11 8 1/2 Definition 5 An m × n matrix is called a row (resp. column) vector if m = 1 (resp. n = 1). An m × n matrix is called a square matrix of order n if m = n. A matrix A is completely determined by its size m × n and by its entries: if 1 ≤ i ≤ m and 1 ≤ j ≤ n we call the number appearing in the i-th row and j-th column the (i, j)-entry of A. Formally, a vector is an element of Rn (an n-tuple) and an m × n matrix is an n-tuple of m-tuples, i.e. an element of Rm×n. 3/4 1 13 7/2 is a row vector,   Example 2    0  is a column vector, 8/7 2 3 10    0 2 0  is a square matrix of order 3, 11 0 18 Matrices are often denoted by capital letters. We also write A = [aij ]m,n or A = (aij )m,n for the matrix of size m × n whose (i, j)-th entry is aij , or just A = [aij ] if the size is clear. 4  Vectors are denoted by boldface lower letters: b = [bi ] or (bi ) (clear from context if row or column, but usually column). Matrices attached to linear systems Definition 6 Consider the linear system: a11 x1 + · · · + a1n xn = b1 a21 x1 + · · · + a2n xn = b2... am1 x1 + · · · + amn xn = bm. The matrix   a11 · · · a1n  a21 · · · a2n  A=...    ...  am1 · · · amn is called the coefficient matrix. The matrix   b1  b2  b=.    ..  bm is called the right hand side vector. The matrix   a11 · · · a1n b1  a21 · · · a2n b2  à = [A | b] = .....   ....   am1 · · · amn bm is called the augmented matrix. We can also write the solutions more compactly: Definition 7 A solution vector for a linear system of equations in x1 ,... , xn is a vector   α1 ..  .  αn such that the equations of the system are all satisfied if we substitute xi = αi for every i. 5  The solution set is the set consisting of all solution vectors. Convention: (α1 ,... , αn ) denotes the column vector [αi ]. Example For the system arising from the line intersection example: ( x1 − x2 = 2 − 21 x1 − x2 = −1 we have 1 −1   the coefficient matrix A = − 21 −1 2   the right hand side vector b = −1 1 −1 2   the augmented matrix à = [A | b] = − 12 −1 −1 2   the solution set = {(2, 0)} 0 How does the augmented matrix help us solve the system? Elementary row operations There are three kinds of elementary row operations (EROs) on an m × n matrix. Let 1 ≤ i, j ≤ m and c be a non-zero constant. 1. Eij = Eji : switch the i-th and j-th row (interchange); 2. Ei (c): multiply the i-th row by c (scale); 3. Eij (c): add c times the i-th row to the j-th row (replace/combine). Definition 8 Two matrices are called row equivalent if there is a sequence of elementary row oper- ations that transforms one matrix into the other. Theorem 1 If the augmented matrices of two linear systems are row equivalent, then the two systems have the same solution set. Proof. 1. The order of equations does not matter. 2. X = Y is true if and only if cX = cY is true for all c ̸= 0. 3. X = Y is true if and only if X + Z = Y + Z is true for all Z. 1 −1 2   Example (Unique solution) Consider the augmented matrix of the linear system − 12 −1 −1 ( x1 − x2 = 2 − 12 x1 − x2 = −1 6  Apply EROs on the augmented matrix: We get: 1 −1 2 1 0 2     → ··· → − 12 −1 −1 0 1 0 By the previous theorem the following two systems have the same solution set: ( ( x1 − x2 = 2 x1 − 0 · x2 = 2 and − 2 x1 − x2 = −1 1 0 · x1 + x2 = 0 The solution set of the second system is obvious, namely {(2, 0)}, which agrees with our previous computations. Can the strategy of the previous example be applied more generally? And what would happen if the system had no solutions or infinitely many? Example (No solutions) ( 3x1 + 3x2 = 1 −x1 = x2 The augmented matrix is 3 3 1 E12 −1 −1 0 E1 (−1) 1 1 0       à := −−→ −−−−−→ −1 −1 0 3 3 1 3 3 1 1 1 0   E12 (−3) −−−−−→ =: B̃ 0 0 1 The second equation in the system attached to B̃ is 0 · x1 + 0 · x2 = 1 which has no solutions. Thus the solution set of our system is the empty set ∅. Now let us look at the remaining example. Example (Infinitely many solutions) ( x1 − x2 = 2 −13x1 + 13x2 = −26 7  We have 1 −1 2 1 −1 2 E12 (1) 1 −1 2       E2 (1/13) −−−−−−→ −−−−→ = B̃ −13 13 −26 −1 1 −2 0 0 0 The second equation of the system corresponding to B̃ is 0 · x1 + 0 · x2 = 0, which is satisfied by any x1 and x2 ; so it gives no information. It imposes no restrictions whatsoever on the solution set. The first equation is x1 − x2 = 2, so the solution set is {(α + 2, α) : α ∈ R} i.e., the set of all pairs (x, y) satisfying x − y = 2. Intersection of planes Above we studies the intersections of lines in order to identify any possible solutions. Now we will study intersection of planes in R3. Example (Infinitely many solutions (intersection is a line)) Compute the points in the intersection of the planes in R3 P1 : x + z = 0, P2 : y + 2z = 0. Solution: As we can see from the image the intersection is a line. Example (no solution (no intersection)) Compute the points in the intersection of the planes in R3 P1 : 3x + 6y + 3z = 6, P2 : 2x + 4y + 2z = −4. Solution: 8  As we can see from the image the intersection is empty (as the planes are parallel). Example (Infinitely many solutions (intersection is the plane)) Compute the points in the intersection of the planes in R3 P1 : x + y + z = 7, P2 : 2x + 2y + 2z = 14. Solution: As we can see from the image that the intersection of the planes is the plane itself. 9 Tutorial exercises I. Class discussion: Exercise 1. Decide if each statement is true or false (justify your answer). (a) A 3 × 4 matrix has 4 rows. (b) Suppose we apply an elementary row operation to a matrix A and obtain a ma- trix B. Then, A can be obtained by performing an elementary row operation on B. (c) Elementary row operations on an augmented matrix changes the solution set of the associated linear system. (d) Two matrices are row equivalent if they have the same number of rows. (e) A consistent system of linear equations has one or more solutions. Work in groups: Exercise 2. Determine whether each of the following systems of equations is linear. If so, put it in standard form and write augmented matrices corresponding to these systems. ( 2x1 x2 = x3 + 1 (a) −x3 + x2 − 3 = 0 ( 2x + y = z + t (b) y + 3t = 2x + 3  2x + 3y = −2z  (c) y + 3t − 1/2 = 2x p − t = −x + 3   Exercise 3. Find the elementary row operation that transforms the first matrix into the second, and then find the reverse row operation that transforms the second matrix into the first. 123 123     (a) 4 5 6, 7 8 9 789 456 123     −0.5 −1 −1.5 (b) 4 5 6,  4 5 6  789 7 8 9 123 1 2 3     (c) 4 5 6, 0 −3 −6 789 7 8 9 10 Exercise 4. Each of the following matrices were obtained by applying EROs to the augmented matrix associated with a linear system: 100 2 1 0 0 2     a)  0 0 1 −1  , b)  0 1 0 1  , 000 0 0 0 1 3 1 0 0 −2 1 0 0 1     c)  0 1 0 0  , d)  0 0 0 0 . 000 0 0 0 0 0 Determine the solution set of each system. Exercise 5. Construct three different augmented matrices for linear systems whose solution set is (x1 , x2 , x3 ) = (−1, 2, 3). Exercise 6. (PageRank) Google uses the PageRank algorithm to rank web pages in their search engine results. Here we will show, in simple terms, how this algorithm works. Suppose we have a web of four pages represented as in the figure: The vertices are the pages and the arrows are links from one page to another. For page i let Li be the set of all indices of pages linking to it. For page j let nj be its total number of outgoing links. We define the page score xi for the page i by X xj xi =. (2) nj j∈Li [Note that Google actually uses a more complicated formulation for page scoring.] (a) Write the system of linear equations resulting from the system of page ranking defined in Equation (2). (b) Suppose that x4 = 1. Compute the page scores of other vertices. Exercise 7. Consider the linear system given by 2x + 3y = 5 and x − 1 = 0. (a) What is its solution set? (Write it down in mathematical notation.) (b) Is this system consistent? (c) Formulate the problem and the solution geometrically. 11 Take-home problems Exercise 8. (The Discrete Heat Equation) Consider placing the following grid on a square plate as in the figure There are four points inside the plate to consider and the temperatures at these points are labelled x1 , x2 , x3 and x4. Discrete mean value property states that at each interior mesh point, the temperature is approximately the average of the temperatures at the neighbouring mesh points. (b) Write the system of linear equations modelling the temperatures of the interior mesh points. (c) Suppose that x2 = 15. Compute the temperatures of the other interior mesh points. Exercise 9. Construct a linear system that has x1 = 1, x2 = 1 as a solution and right-hand side terms b1 = 1, b2 = −2, b3 = 3. Answers 1 (a) F (b) T (c) F (d) F (e) T 2 (a) not a linear system ( 2x + y − z − t = 0 2 1 −1 −1 | 0   (b) , the augmented matrix is. y + 3t − 2x = 3 −2 1 0 3 | 3  2x + 3y + 2z = 0 2 3 2 0 0 | 0    (c) y + 3t − 2x = 1/2 , the augmented matrix is −2 1 0 0 3 | 1/2. p − t + x = −3 1 0 0 1 −1 | −3   3 (a) E23 and the reverse is E23 ; (b)E1 (−1/2) and the reverse is E1 (−2); (c) E12 (4) 4 (a) {(2, t, −1) : t ∈ R} 12  (b) {(2, 1, 3)} (c) {(−2, 0, t) : t ∈ R} (d) {(1, s, t) : s, t ∈ R} 1 0 0 | −1 110|1 1 0 0 | −1       5 0 1 0 | 2 , 0 1 0 | 2, 0 0 1 | 3 . (Try to construct different matrices than 001| 3 001|3 010| 2 these three examples.) 6 (a) The linear system is 1 x1 − x2 − x3 =0 3 1 1 − x1 + x2 − x3 =0 2 3 1 − x1 + x3 − x4 =0 2 1 − x3 + x4 = 0. 3 (b) x1 = 4, x2 = 3, x3 = 3. 7 (a) {(1, 1)} (b) the system is consistent (c) Two lines intersect at one point. 8 (a) The linear system is 4x1 − x2 − x3 = 40 −x1 + 4x2 − x4 = 30 −x1 + 4x3 − x4 = 30 −x2 − x3 + 4x4 = 20. (b) x1 = 35/2, x2 = x3 = 15, x4 = 25/2. 9  2x1 − x2 = 1  −x1 + x2 = −2 4x1 − x2 = 3   (Try to find a linear system different than this one.) 13