Linear Equations: Introduction, Gaussian Elimination, Curve Fitting

Chapter 1 Systems of Linear Equations 1.1 Introduction to Systems of Linear Equations 1.2 Gaussian Elimination and Gauss-Jordan Elimination 1.3 Applications of Systems of Linear Equations (Polynomial Curve Fitting) The linear algebra arises from solving systems of linear equations The last section of each chapter illustrates how to apply the knowledge you learn in that chapter to solving problems in different fields 1.1

1.1 Introduction to Systems of Linear Equations A linear equation ( ) in n variables: + + + + = 1 1 a x 2 2 a x 3 3 a x a x b n n ai: real-number coefficients xi: variables needed to be solved b : real-number constant term a1: leading coefficient ( ) x1: leading variable ( ) Notes: (1) Linear equations have no products or roots of variables and no variables involved in trigonometric, exponential, or logarithmic functions (2) Variables appear only to the first power 1.2

Ex 1: Linear or Nonlinear 1 2x + = Linear (b) 2 y z Linear + = (a) 3 2 7 x y Linear Linear = 2 (d) (sin ) 4 x x e + + = (c) 2 10 0 x x x x 1 2 1 2 3 4 is the exponent x = xe + = product of variables (f) 2 4 y Nonlinear Nonlinear (e) 2 xy z 1 x not the first power 1 y Nonlinear Nonlinear + = (g) sin 2 3 0 x x x + = (h) 4 1 2 3 trigonometric function 1.3

A solution () of a linear equation in n variables: + + + + = 1 1 a x a x 3 3 a x a x b 2 2 n n x = x = x = x = , , , s s s s , 1 1 2 2 3 3 n n + + + + = s.t. a s a s a s a s b 1 1 2 2 3 3 n n Solution set ( ): the set of all solutions of a linear equation In most cases, there are infinitely many ( ) solutions of a linear equation, so we need some methods to represent the solution set 1.4

Ex 2: Parametric representation () of a solution set = = , 2 1 x x + x = 2 4 with a solution (2, 1), i.e., x 1 2 1 2 If you solve for x1in terms of x2, you obtain 4 2 (in this form, the variable is free) x x = t x = 2 x 1 2 2 By letting (the variable t is called a parameter), you can represent the solution set as = = 4 2 , t x , is any real number t t x 1 2 The set representation for solutions: 4 ( 2 | ) , t t t R If you choose x1 to be the free variable, the parametric representation of the solution set is {(?,2 ? 2)|? ?} 1.5

A system of m linear equations in n variables: + + + + + + + + + + + + = = = 11 1 a x a x a x 12 2 a x a x a x 13 3 a x a x a x a x a x a x b b b 1 1 n n 21 1 22 2 23 3 2 2 n n 31 1 32 2 33 3 3 3 n n + + + + = 1 1 m a x a x a x mn n a x b 2 2 3 3 m m m A solution of a system of linear equations ( ) is a sequence of numbers s1, s2, , snthat can solve each linear equation in the system 1.6

Three possible cases for solutions of a system of linear equations: Every system of linear equations has either (1) exactly one solution (2) infinitely many solutions (3) no solution Consistent ( ( )): A system of linear equations has at least one solution (for cases (1) and (2)) Inconsistent ( ( )): A system of linear equations has no solution (for case (3)) 1.7

Ex 4: Solution of a system of linear equations in 2 variables + = 3 x y (1) = 1 x two intersecting lines y exactly one solution + = 3 x y (2) + = 2 two coincident lines 2 6 x y inifinitely many solution + = 3 x y (3) + = 1 lines x two y no solution parallel 1.8

Ex 5: Using back substitution ( system in row-echelon form ( x ) to solve a ) 5 (1) 2 (2) = = 2 y y The row-echelon form means that the system follows a stair-step pattern (The first variable x is the leading variable in Eq. (1), and the second variable y is the leading variable in Eq. (2)) and has leading coefficients of 1 for all equations (The formal definition of row-echelon form will be introduced on Slide 1.25) The back substitution means to solve a system in a reverse order. That is, you solve Eq. (2) for y first, and then substitute the solution of y into Eq. (1). Next, you can solve x directly in Eq. (1) since x is the only unknown variable Sol: By substituting into Eq. (1), you obtain = y 2 2( 2) = = 5 1 x x , 1 = = 2 x y The system has exactly one solution: 1.9

Ex 6: Using back substitution to solve a system in row- echelon form 2 x y y + + = = = 3 3 9 5 (2) 2 (3) (1) z z z Sol: Substitute into (2), y can be solved as follows 2 = z ) 2 ( 3 + y and substitute and into (1) 1 = y = 5 y 1 2 = = z ) 1 + = ( 2 ) 2 ( 3 9 x = 1 x The system has exactly one solution: = x = , 1 = , 1 2 y z 1.10

Equivalent (): Two systems of linear equations are called equivalent if they have precisely the same solution set Notes: Each of the following operations ( ) on a system of linear equations produces an equivalent system O1: Interchange two equations O2: Multiply an equation by a nonzero constant O3: Add a multiple of an equation to another equation Gaussian elimination: A procedure to rewrite a system of linear equations to be in row-echelon form by using the above three operations 1.11

Ex 7: Solve a system of linear equations (consistent system) 2 3 2 5 x y + Sol: First, eliminate the x-terms in Eqs. (2) and (3) based on Eq. (1) (1) (2) (2) (by O3) 2 3 3 2 5 5 x y z + = + + = = = 3 9 4 (2) 17 (1) x x y y z 5 (3) z + + + = = 9 5 (4) 17 x y y z z + (1) ( 2) x (3) (3) (by O3) 3 3 z z = + + = = 2 9 5 1 y y y z (5) 1.12

Second, eliminate the (-y)-term in Eq. (5) based on Eq. (4) + (4) x (5) (5) (by O3) + + = = = 2 3 3 2 9 5 4 y y z z z (6) (6) x (6) (by O2) 2 y y + 1 2 + = = = 3 3 9 5 2 z z z Since the system of linear equations is expressed in its row- echelon form, the solution can be derived by the back substitution: (only one solution) , 1 , 1 = = = z y x 2 1.13

Ex 8: Solve a system of linear equations (inconsistent system) + x x x = 3 1 x x x (1) 1 2 3 = 2 2 2 1 (2) 1 2 3 + = (3) 2 3 x x x 1 2 3 Sol: + + + (1) ( (1) ( 1) x 2) (2) (3) (2) (by O3) (3) (by O3) x x x = = = 3 5 5 1 0 (4) 2 x x x 1 2 3 4 4 2 3 (5) 2 3 1.14

+ + (4) ( 1) x (5) (5) (by O3) x x = = = 3 5 1 0 2 x x 1 2 3 4 2 3 0 (a false statement) So, the system has no solution (an inconsistent system) 1.15

Ex 9: Solve a system of linear equations (infinitely many solutions) x x x x x x + = = = 0 1 (2) 1 (1) 2 3 3 1 3 3 (3) 1 2 Sol: (1) (2) (by O1) = = = 3 1 0 (2) 1 (1) x x x 1 3 x x 2 3 + 3 (3) x 1 2 + (1) (3) (3) (by O3) = = = 3 1 0 0 x x x x 1 3 x x 2 3 3 3 (4) 2 3 1.16

Since Equation (4) is the same as Equation (2), it is not necessary and can be omitted 1 = = 3 1 0 x x x 1 3 x 2 x 3 x = = + , x 3 x 2 3 1 3 Let , then x = 3 = = = t 3 t t 1 x x x t 1 t R 2 3 This system has infinitely many solutions. 1.17

Keywords in Section 1.1: linear equation: system of linear equations: leading coefficient: leading variable: solution: solution set: free variable: parametric representation: consistent: ( ) inconsistent: ( ) row-echelon form: equivalent: 1.18

1.2 Gaussian Elimination and Gauss-Jordan Elimination m n matrix ( ): a 21 a a a a 11 12 13 1 n a a a 22 23 2 n a a a a rows ( ) m 31 32 33 3 n a a a a 1 2 3 m m columns ( m mn ) n Notes: (1) Every entry ( ) aij in the matrix is a real number (2) A matrix with m rows and n columns is said to be with size m n (3) If , then the matrix is called square matrix ( ) of order n n m= (4) For a square matrix, the entries a11, a22, , annare called the main (or principal) diagonal ( ) entries 1.19

Ex 1: Matrix Size 1 A scalar (any real number) can be treated as a 1 1 matrix. 1 ] 2 [ 0 0 2 2 0 0 1 1 1 3 0 4 2 e 3 2 2 2 7 4 Note: One very common use of matrices is to represent a system of linear equations (see the next slide) 1.20

A system of m equations in n variables: a x a x a x a x a x a x + + + + + + + + + + + + = = = 13 3 a x a x a x a x a x a x b b b 11 1 12 2 1 1 n n 21 1 22 2 23 3 2 2 n n 31 1 32 2 33 3 3 3 n n + + + + = 1 1 m a x a x a x a x b 2 2 3 3 m m mn n m Matrix form: ?? = ? a a a a x x b b 11 12 13 1 n 1 1 a a a a 21 22 23 2 n 2 2 = = x b = A a a a a 31 32 33 3 n x b a a a a n m 1 2 3 m m m mn 1.21

Coefficient matrix (): = a a a a a a a a a a a a 11 12 13 1 n 21 22 23 2 n A 31 32 33 3 n a a a a 1 2 3 m m m mn Augmented matrix ( ): formed by appending the constant-term vector to the right of the coefficient matrix of a system of linear equations a a a a a a a a a = a a a b b b 11 12 13 1 1 n 21 22 23 2 2 n b [ ] A 31 32 33 3 3 n a a a a b 1 2 3 m m m mn m 1.22

Before introducing the Gaussian elimination and the Gauss- Jordan elimination, we need some background knowledge, including the elementary row operations ( ) and the criteria to identify the row-echelon or reduced row- echelon forms ( ) for matrices Elementary row operations ( ): (1) Interchange two rows: , i j I R R i j (2) Multiply a row by a nonzero constant: ( ) k i A ( ) k R M R i i (3) Add a multiple of a row to another row: + ( ) , i j k ( ) k R R R i j j Row equivalent ( ): Two matrices are said to be row equivalent if one can be obtained from the other by a finite sequence of above elementary row operations 1.23

Ex 2: Elementary row operations 0 1 3 4 1 2 0 3 I 1,2 1 2 0 3 0 1 3 4 2 3 4 1 2 3 4 1 1 2 2 4 6 2 1 2 3 1 ( ) M 1 3 3 0 1 3 3 0 1 5 2 1 2 5 2 1 2 1 2 4 3 1 2 4 3 ( 2) 1,3 A 13 0 3 2 1 0 3 2 1 2 1 5 2 0 3 8 1.24

Row-echelon form (): (1), (2), and (3) Reduced row-echelon form ( ): (1), (2), (3), and (4) (1) All rows consisting entirely of zeros occur at the bottom of the matrix ( 0 row matrix ) (2) For each row that does not consist entirely of zeros, the first nonzero entry from the left side is 1, which is called as leading 1 ( 0 row 0 entry 1 entry leading 1) (3) For two successive nonzero rows, the leading 1 in the higher row is further to the left than the leading 1 in the lower row ( 0 row row leading 1 ) (4) Every column that contains a leading 1 has zeros everywhere else ( leading 1 column entry 0) 1.25

Ex 4: Row-echelon form or reduced row-echelon form 3 0 1 0 1 2 1 4 0 1 0 5 (reduced row- echelon form) (row-echelon form) 0 0 1 3 0 0 1 2 0 0 0 0 1 0 0 1 1 5 2 1 3 (reduced row- echelon form) 0 1 0 2 (row-echelon form) 0 0 1 3 2 0 0 1 3 0 0 0 1 4 0 0 0 0 0 0 0 0 1 1 2 3 4 1 2 1 2 0 2 1 1 0 0 0 0 0 0 1 3 0 1 2 4 Violate the first criterion Violate the second criterion 1.26

Gaussian elimination: The procedure for reducing a matrix to a row-echelon form by performing the three elementary row operations Gauss-Jordan elimination: The procedure for reducing a matrix to its reduced row-echelon form by performing the three elementary row operations Notes: (1) Every matrix has an unique reduced row-echelon form (2) A row-echelon form of a given matrix is not unique (Different sequences of elementary row operations can produce different row-echelon forms) The above two statements will be verified numerically in Ex. 8 1.27

Ex: Procedure of the Gaussian elimination and Gauss-Jordan elimination Produce a leading 1 2 0 10 0 0 2 0 7 12 2 4 10 6 12 28 I 1,2 2 4 6 12 28 0 0 7 12 2 4 5 6 5 1 2 4 5 6 5 1 The first nonzero column Leading 1 0 Produce a leading 1 6 3 1 2 1 2 5 3 6 14 ( ) 1 1 2 5 14 ( 2) 1,3 A M 0 2 0 7 12 0 0 2 0 7 12 2 4 5 6 5 1 0 0 5 0 17 29 Eliminate nonzero entries below the leading 1 Submatrix The first nonzero column 1.28

The first nonzero column Leading 1 1 2 0 0 5 1 0 0 3 6 14 6 1 2 0 0 5 1 0 5 0 3 6 14 6 29 1 2 ( 2 ) ( 5) 2,3 A M 0 0 7 2 1 2 0 0 7 2 17 0 1 Eliminate nonzero entries below the leading 1 Submatrix Produce a leading 1 Nonzero entries 1 2 0 3 0 7 1 2 0 0 5 1 0 0 3 6 14 6 2 7 2 (2) 3 ( ) 3,2 M ( 6) 3,1 A (5) 2,1 A A 0 0 1 0 0 1 7 2 0 0 0 0 0 0 1 2 0 1 Leading 1 s (reduced row- echelon form) (row-echelon form) 1.29

Ex 7: Solve a system by the Gauss-Jordan elimination method (only one solution) 2 + y x Sol: Form the augmented matrix by concatenating and + = 3 9 x y z = 3 4 x y + = 2 5 5 17 z b A 1 1 2 (row-echelon form) 1 1 2 2 3 0 5 3 9 4 1 0 0 2 1 1 3 3 1 9 5 1 1 0 0 2 3 9 1 3 0 1 2 ( 2) 1,3 A (1) 1,2 (1) 2,3 (1/2) 3 A A M 5 5 17 1 0 0 0 0 = ( 3) 3,2 A ( 3) 3,1 A (2) 2,1 A 1 x 1 0 0 = 1 y = 1 2 z (reduced row-echelon form) 1.30

Ex 8Solve a system by the Gauss-Jordan elimination method (infinitely many solutions) + + = = 2 3 4 5 2 0 1 x x x x x 1 2 3 1 2 Sol: For the augmented matrix, 2 3 4 5 2 0 0 1 1 2 3 1 0 0 1 0 2 1 1 0 3 1 2 ( ) 1 ( 3) 1,2 A M 5 1 1 1 2 0 1 3 0 1 1 0 0 5 3 2 1 ( 2) 2,1 A ( 1) 2 M 1 1 (reduced row-echelon form) (row-echelon form) 1.31

Then the system of linear equations becomes 3 x + = = 5 2 x x x 1 3 1 2 3 It can be further reduced to = 2 5 x x 1 3 = + 1 3 x x 2 3 Let , then x = 3 = 2 5 + , t x t 1 = 1 3 , x t t R 2 = , x t 3 So, this system has infinitely many solutions 1.32

In order to show that the reduced row-echelon form is unique, an experiment is conducted by performing a redundant elementary row operation of interchanging the first and second rows in advance 2 3 4 5 2 0 0 1 3 2 5 4 0 2 1 0 1 5/3 2 0 1/3 2 (1/3) 1 1,2 I M 4 0 1 5/3 0 2/3 0 2 1/3 2/3 1 5/3 0 (row-echelon form) 0 1/3 3 ( 2) 1,2 A (3/ 2) 2 M 1 1 1 0 0 5 3 2 1 ( 5/3) 2,1 A 1 (reduced row-echelon form) Comparing with the results on Slide 1.31, we can infer that it is possible to derive different row-echelon forms, but there is a unique reduced row-echelon form for each matrix 1.33

Homogeneous systems of linear equations () : A system of linear equations is said to be homogeneous if all the constant terms are zero + + + + = 0 a x a x a x a x 11 1 12 2 13 3 1 n n + + + + = 0 a x a x a x a x 21 1 22 2 23 3 2 n n + + + + = 0 a x a x a x a x 31 1 32 2 33 3 3 n n + + + + = 0 a x a x a x a x 1 1 2 2 3 3 m m m mn n 1.34

Trivial (obvious) solution (): = = x x x = = = 0 nx 1 2 3 Nontrivial solution ( ): other solutions Theorem 1.1 (1) Every homogeneous system of linear equations is consistent. Furthermore, for a homogeneous system, exactly one of the following is true: (a) The system has only the trivial solution (b) The system has infinitely many nontrivial solutions in addition to the trivial solution (In other words, if a system has any nontrivial solution, this system must have infinitely many nontrivial solutions) (2) If the homogenous system has fewer equations than variables, then it must have an infinite number of solutions 1.35

Ex 9: Solve the following homogeneous system (also verify the two statements in Theorem 1.1 numerically) + + + = = 3 3 0 0 x x x x x x 1 2 3 2 1 2 3 For the augmented matrix, Sol: 1 3 ( ) 2 ( 2) 1,2 A (1) 2,1 M A 1 0 2 0 1 1 3 0 (reduced row- echelon form) 2 1 3 0 0 1 1 0 + = = 2 0 0 x x x 1 3 x 2 3 = = = Let , then x = 3 2 , , , x t x t x t t R t 1 2 3 = = = = When When 0, 0, there are infinitely many nontrivial solutions 0 (trivial solution) t t x x x 1 2 3 1.36

Keywords in Section 1.2: matrix: row: column: entry: size: square matrix: order: main diagonal: coefficient matrix: augmented matrix: 1.37

elementary row operation: row equivalent: row-echelon form: reduced row-echelon form: leading 1: 1 Gaussian elimination: Gauss-Jordan elimination: - homogeneous system: trivial solution: nontrivial solution: 1.38

1.3 Applications of Systems of Linear Equations Polynomial Curve Fitting in Examples 1, 2, and 4 See the text book or Applications in Ch1.pdf downloaded from my website The polynomial curve fitting problem is that given n points (x1, y1), (x2, y2), , (xn, yn) on the xy-plane, find a polynomial function of degree n 1 passing through these n points Once equipped with this polynomial function, we can predict the value of y for some missing values of x A typical application of the curve fitting problem in the field of finance is to derive the interest rate (y) for different time to maturity (x) 1.39