ECE 317 Linear Algebra Chapter 2 PDF

ECE 317: Linear Algebra Chapter 2: Systems of Linear Equations feh The content of this lecture note is based mainly on Chapter 3: Systems of Linear Equations from the textbook ”Schaum’s Outl...

ECE 317: Linear Algebra Chapter 2: Systems of Linear Equations feh The content of this lecture note is based mainly on Chapter 3: Systems of Linear Equations from the textbook ”Schaum’s Outline of Linear Algebra” by by Lipschutz, Seymour, and Marc Lars Lipson. McGraw-Hill Education, 4th edition. It also includes additional examples from other resources. aq Contents 1 Basic Definitions, Solutions 3 aw 1.1 Linear Equation and Solutions.............................. 3 1.2 System of Linear Equations................................ 3 1.3 1.4 1.5 Sh Augmented and Coefficient Matrices of a System.................... Degenerate Linear Equations............................... Pivot: Leading Variable in a Nondegenerate Linear Equation............. 5 7 7 fa 2 Equivalent Systems, Elementary Operations 8 2.1 Equivalent Systems..................................... 9 ta 2.2 Elementary Operations................................... 10 3 Small Square Systems of Linear Equations 11 us 3.1 Geometrical Interpretation of a 2 × 2 Linear System.................. 11 3.2 Solving a 2 × 2 System Using the Elimination Algorithm................ 12.M 4 Systems in Triangular and Echelon Forms 14 4.1 Triangular Form...................................... 14 4.2 Echelon Form, Pivot and Free Variables......................... 15 Dr 5 Gaussian Elimination 16 5.1 Gaussian Elimination in Matrix Form.......................... 20  6 Echelon Matrices, Row Canonical Form, Row Equivalence 23 6.1 Echelon Matrices...................................... 23 feh 6.2 Row Canonical Form.................................... 24 6.3 Elementary Row Operations................................ 25 6.4 Rank of a Matrix...................................... 25 aq 6.5 Row Equivalence...................................... 26 7 Homogeneous Systems of Linear Equations 27 aw 7.1 Basis for the General Solution of a Homogeneous System................ 28 7.2 Nonhomogeneous and Associated Homogeneous Systems................ 30 8 Finding the Inverse of an n × n Matrix Sh 34 fa ta us.M Dr 2  1 Basic Definitions, Solutions 1.1 Linear Equation and Solutions feh Definition 1 (Linear Equation). A linear equation in unknowns x1 , x2 ,... , xn is an equation that can be put in the standard form a1 x1 + a2 x2 + · · · + an xn = b aq where a1 , a2 ,... , an , and b are constants. The constant ak is called the coefficient of xk , and b is called the constant term of the equation. aw Definition 2 (Solution of a Linear Equation). A solution of the linear equation is a list of values for the unknowns or, equivalently, a vector u in K n , say x1 = k1 , x2 = k2 ,..., Sh xn = kn or u = (k1 , k2 ,... , kn ) such that the following statement (obtained by substituting ki for xi in the equation) is true: a1 k1 + a2 k2 + · · · + an kn = b fa In such a case we say that u satisfies the equation. ta Example 1.1. Consider the following linear equation in three unknowns x, y, z : x + 2y − 3z = 6 us We note that x = 5, y = 2, z = 1, or, equivalently, the vector u = (5, 2, 1) is a solution of the equation. That is,.M 5 + 2(2) − 3(1) = 6 or 5+4−3=6 or 6=6 On the other hand, w = (1, 2, 3) is not a solution, because on substitution, we do not get a true statement: 1 + 2(2) − 3(3) = 6 or 1 + 4 − 9 = 6 or −4=6 Dr 1.2 System of Linear Equations 3  Definition 3 (System of Linear Equations). A system of linear equations is a list of linear equa- tions with the same unknowns. In particular, a system of m linear equations L1 , L2 ,... , Lm in n unknowns x1 , x2 ,... , xn can be put in the standard form feh Equation 1 (L1 ) : a11 x1 + a12 x2 + · · · + a1n xn = b1 Equation 2 (L2 ) : a21 x1 + a22 x2 + · · · + a2n xn = b2.. (1). aq Equation m (Lm ) : am1 x1 + am2 x2 + · · · + amn xn = bm where the aij and bi are constants. The number aij is the coefficient of the unknown xj in the equation Li , and the number bi is the constant of the equation Li. aw Definition 4 (Square Linear System). The system of linear equations is called an m × n (read: m Sh by n ) system. It is called a square system if m = n-that is, if the number m of equations is equal to the number n of unknowns. Definition 5 (Homogeneous System). The system is said to be homogeneous if all the constant fa terms are zero-that is, if b1 = 0, b2 = 0,... , bm = 0. ta Definition 6 (Nonhomogeneous System). The system is said to be nonhomogeneous if any of the constant terms is non-zero. us Definition 7 (Solution of a Linear System). A solution (or a particular solution) of a system is a.M list of values for the unknowns or, equivalently, a vector u in K n , which is a solution of each of the equations in the system. Definition 8 (Solution Set). The set of all solutions of the system is called the solution set or the Dr general solution of the system. 4  Example 1.2. Consider the following system of linear equations: x1 + x2 + 4x3 + 3x4 = 5 feh 2x1 + 3x2 + x3 − 2x4 = 1 x1 + 2x2 − 5x3 + 4x4 = 3 It is a 3 × 4 system because it has three equations in four unknowns. Determine whether (a) u = (−8, 6, 1, 1) and (b) v = (−10, 5, 1, 2) are solutions of the system. Solution: aq a) Substitute the values of u in each equation, obtaining −8 + 6 + 4(1) + 3(1) = 5 or −8 + 6 + 4 + 3 = 5 or 5=5 aw 2(−8) + 3(6) + 1 − 2(1) = 1 or −16 + 18 + 1 − 2 = 1 or 1=1 −8 + 2(6) − 5(1) + 4(1) = 3 or −8 + 12 − 5 + 4 = 3 or 3=3 Yes, u is a solution of the system because it is a solution of each equation. 2(−10) + 3(5) + 1 − 2(2) = 1 Sh b) Substitute the values of v into each successive equation, obtaining −10 + 5 + 4(1) + 3(2) = 5 or or −10 + 5 + 4 + 6 = 5 −20 + 15 + 1 − 4 = 1 or or 5=5 −8 = 1 No, v is not a solution of the system, because it is not a solution of the second equation. (We do not need to substitute v into the third equation.) fa ta Definition 9 (Consistent and Inconsistent Systems). Liner system can be classified into: ˆ Consistent systems: if it has one (i.e., unique solution) or more solutions (i.e., infinite). us ˆ Inconsistent systems: if it has no solution..M Remark 1.1. If the system is consistent, either it has a unique solution (only one solution) or it has infinite number of solutions. The system cannot have finite number of solution other than one (eg., 3 solutions). Dr 1.3 Augmented and Coefficient Matrices of a System Definition 10. Consider again the general system (1) of m equations in n unknowns. Such a 5  feh aq aw Figure 1: Classification of linear systems based on their solution. system has associated with it the following two matrices: M=.  . a11 a12... a1n b1  a21 a22... a2n b2  . am1 am2... amn bn Sh  .  ..  and A = ..  a11 a12... a1n  a21 a22... a2n .... am1 am2... amn      The first matrix M is called the augmented matrix of the system, and the second matrix A is fa called the coefficient matrix. ta Note 1. The coefficient matrix A is simply the matrix of coefficients, which is the augmented matrix M without the last column of constants. us Example 1.3. Consider the following system of linear equations:.M x1 + x2 + 4x3 + 3x4 = 5 2x1 + 3x2 + x3 − 2x4 = 1 x1 + 2x2 − 5x3 + 4x4 = 3 The augmented matrix M and the coefficient matrix A of the system in Example 3.2 are as follows: Dr     1 1 4 3 5 1 1 4 3 M= 2 3 1 −2 1  and A =  2 3 1 −2  1 2 −5 4 3 1 2 −5 4 As expected, A consists of all the columns of M except the last, which is the column of constants. 6  Note 2. Relation between a system of linear equations and its associated augmented matrix feh ˆ Clearly, a system of linear equations is completely determined by its augmented matrix M , and vice versa. ˆ Each row of M corresponds to an equation of the system, ˆ Each column of M corresponds to the coefficients of an unknown, except for the last column, aq which corresponds to the constants of the system. aw 1.4 Degenerate Linear Equations Definition 11. A linear equation is said to be degenerate if all the coefficients are zero—that is, if it has the form Sh 0x1 + 0x2 +... + 0xn = b Remark 1.2. The solution of such an equation depends only on the value of the constant b. Specifically, fa ˆ If b ̸= 0, then the equation has no solution. ˆ If b = 0, then every vector u = (k1 , k2 ,... , kn ) in K n is a solution. ta Theorem 1.1. Let L be a system of linear equations that contains a degenerate equation L, say us with constant b. (i) If b ̸= 0, then the system L has no solution..M (ii) If b = 0, then L may be deleted from the system without changing the solution set of the system. 1.5 Pivot: Leading Variable in a Nondegenerate Linear Equation Dr Definition 12 (Pivot). Now let L be a nondegenerate linear equation (i.e., one or more of the coefficients of L are not zero). By the leading unknown of L, we mean the first unknown in L with a nonzero coefficient. 7  feh aq aw Sh Figure 2: Why do we need equivalent systems and elementary operations? Example 1.4. For example, x3 and y are the leading unknowns, respectively, in the equations fa 0x1 + 0x2 + 5x3 + 6x4 + 0x5 + 8x6 = 7 and 0x + 2y − 4z = 5 We frequently omit terms with zero coefficients, so the above equations would be written as ta 5x3 + 6x4 + 8x6 = 7 and 2y − 4z = 5 In such a case, the leading unknown appears first. us 2 Equivalent Systems, Elementary Operations.M ˆ These two section are related to each other as it first define the concept oof equivalent systems and the ”elementary operations” is one way to obtain equivalent systems of linear equations. ˆ Why do we need equivalent systems and elementary operations? Consider a system L of linear equations. Then, Gaussian elimination, our main method for finding the solution of a given system of linear equations, consists of using the elementary Dr operations to transform the given system L into an equivalent system M (i.e., has the same solution) whose solution can be easily obtained (i.e., obtaining the solution from the system M is much simpler than the original system L ). 8  2.1 Equivalent Systems Definition 13 (Linear Combination of Equations). Consider the following system of m linear feh equations in n unknowns. Equation 1 (L1 ) : a11 x1 + a12 x2 + · · · + a1n xn = b1 Equation 2 (L2 ) : a21 x1 + a22 x2 + · · · + a2n xn = b2.. (2). aq Equation m (Lm ) : am1 x1 + am2 x2 + · · · + amn xn = bm Let L be the linear equation obtained by multiplying the m equations by constants c1 , c2 ,... , cm , respectively, and then adding the resulting equations. Specifically, let L be the following linear aw equation: (c1 × L1 ) : c1 a11 x1 + c1 a12 x2 + ··· + c1 a1n xn = c1 b1 (c2 × L2 ) : c2 a21 x1 + c2 a22 x2 + ··· + c2 a2n xn = c2 b2.. (cm × Lm ) : (Sum) L :. cm am1 x1 + cm am2 x2 + Sh ··· + cm amn xn (c1 a11 + · · · + cm am1 ) x1 + · · · + (c1 a1n + · · · + cm amn ) xn = cm bm = c1 b1 + · · · + cm bm Then L is called a linear combination of the equations in the system. fa ta Remark 2.1. Any solution of the system (2) is also a solution of the linear combination L. us Example 2.1. Let L1 , L2 , L3 denote, respectively, the following three equations: x1 + x2 + 4x3 + 3x4 = 5 2x1 + 3x2 + x3 − 2x4 = 1.M x1 + 2x2 − 5x3 + 4x4 = 3 Let L be the equation obtained by multiplying L1 , L2 , L3 by 3, −2, 4, respectively, and then adding. 3L1 : 3x1 + 3x2 + 12x3 + 9x4 = 15 −2L2 : −4x1 − 6x2 − 2x3 + 4x4 = −2 4L1 : 4x1 + 8x2 − 20x3 + 16x4 = 12 (Sum) L : 3x1 + 5x2 − 10x3 + 29x4 = 25 Dr Let the solution u = (−8, 6, 1, 1) of the system. Then, u = (−8, 6, 1, 1) is also a solution of L. That is, substituting u in L, we obtain a true statement: 3(−8) + 5(6) − 10(1) + 29(1) = 25 or − 24 + 30 − 10 + 29 = 25 or 9=9 9  Definition 14 (Equivalent Systems). Two systems of linear equations are said to be equivalent if they have the same solutions. feh Theorem 2.1 (Equivalent Systems). Two systems of linear equations have the same solutions if and only if each equation in each system is a linear combination of the equations in the other aq system. aw 2.2 Elementary Operations Definition 15. The following operations on a system of linear equations L1 , L2 ,... , Lm are called elementary operations. interchanged by writing: Sh ˆ [E1 ] Interchange two of the equations. We indicate that the equations Li and Lj are Interchange Li and Lj ”, or ” Li ←→ Lj ” ˆ [E2 ] Replace an equation by a nonzero multiple of itself. We indicate that equation Li is fa replaced by kLi (where k ̸= 0 ) by writing: ”Replace Li by kLi ′ or ” kLi → Li ” ta ˆ [E3 ] Replace an equation by the sum of a multiple of another equation and itself. We indicate that equation Lj is replaced by the sum of kLi and Lj by writing: ”Replace Lj by kLi + Lj ” or ” kLi + Lj → Lj ” us Note: The arrow → in [E2 ] and [E3 ] may be read as ”replaces.”.M Remark 2.2. Sometimes (say to avoid fractions when all the given scalars are integers) we may apply [E2 ] and [E3 ] in one step; that is, we may apply the following operation: [E] Replace equation Lj by the sum of kLi and k ′ Lj (where k ′ ̸= 0 ), written ”Replace Lj by kLi + k ′ Lj ” or ” kLi + k ′ Lj → Lj ” Dr The main property of the above elementary operations is contained in the following theorem (proved in Problem 3.45). 10  Theorem 2.2. Suppose a system of M of linear equations is obtained from a system L of linear equations by a finite sequence of elementary operations. Then M and L have the same solutions. feh 3 Small Square Systems of Linear Equations aq 3.1 Geometrical Interpretation of a 2 × 2 Linear System ˆ Consider a system of two nondegenerate linear equations in two unknowns x and y, which aw can be put in the standard form A1 x + B1 y = C1 (3) A2 x + B2 y = C2 not both zero. Sh ˆ Because the equations are nondegenerate, A1 and B1 are not both zero, and A2 and B2 are ˆ If the coefficients A1 , A2 , B1 , B2 , C1 , and C2 are real numbers, then the graph of each equation is a line in the plane ℜ2. ˆ The general solution of the system (3) belongs to one of three types: (i) unique solution, (ii) fa no solution, and (iii) infinite solutions: – The system has exactly one solution. Here the two lines intersect in one point [3.1(a)]. This occurs when the lines have distinct ta slopes or, equivalently, when the coefficients of x and y are not proportional: A1 B1 ̸= or, equivalently, A1 B2 − A2 B1 ̸= 0 A2 B2 us For example, in Fig. 3.1(a), 1/3 ̸= −1/2. – The system has no solution. Here the two lines are parallel [Fig. 3.1(b)]. This occurs when the lines have the same.M slopes but different y intercepts, or when A1 B1 C1 = ̸= A2 B2 C2 For example, in Fig. 3.1(b), 1/2 = 3/6 ̸= −3/8. – The system has an infinite number of solutions. Dr Here the two lines coincide [Fig. 3.1(c)]. This occurs when the lines have the same slopes and same y intercepts, or when the coefficients and constants are proportional, A1 B1 C1 A2 = B2 = C2 For example, in Fig. 3.1(c), 1/2 = 2/4 = 4/8. 11  feh aq aw A2 B2 Sh Remark 3.1. The following expression and its value is called a determinant of order two: A1 B1 = A1 B2 − A2 B1 Determinants will be studied Later. Thus, the system (3) has a unique solution if and only if the fa determinant of its coefficients is not zero. (We show later that this statement is true for any square system of linear equations.) ta 3.2 Solving a 2 × 2 System Using the Elimination Algorithm us Algorithm 1 (Elimination Algorithm for 2 × 2 system:). The input consists of two nondegenerate linear equations L1 and L2 in two unknowns with a unique solution..M ˆ Part A. (Forward Elimination) Multiply each equation by a constant so that the resulting coefficients of one unknown are negatives of each other, and then add the two equations to obtain a new equation L that has only one unknown. ˆ Part B. (Back-Substitution) Solve for the unknown in the new equation L (which contains Dr only one unknown), substitute this value of the unknown into one of the original equations, and then solve to obtain the value of the other unknown. 12  Remark 3.2. Part A of Algorithm 3.1 can be applied to any system even if the system does not have a unique solution. In such a case, the new equation L will be degenerate and Part B will not feh apply. Example 3.1 (Unique Case). Solve the system aq L1 : 2x − 3y = −8 L2 : 3x + 4y = 5 Solution: aw Part A: Forward Elimination: The unknown x is eliminated from the equations by forming the new equation L = −3L1 + 2L2. That is, we multiply L1 by −3 and L2 by 2 and add the resulting equations as follows: −3L1 : −6x + 9y = 24 2L2 : 6x + 8y = 10 Addition : Sh 17y = 34 Part B: Back-Substitution: We now solve the new equation for y, from 17y = 34, we obtain y = 2. We substitute y = 2 into one of the original equations, say L1 , and solve for the other unknown x, obtaining fa 2x − 3(2) = −8 → 2x − 6 = 8 → 2x = −2 → x = −1 ta Thus, x = −1, y = 2, or the pair u = (−1, 2) is the unique solution of the system. The unique solution is expected, because 2/3 ̸= −3/4. [Geometrically, the lines corresponding to us the equations intersect at the point (−1, 2).].M Example 3.2 (No Solution). Solve the system L1 : x − 3y = 4 L2 : −2x + 6y = 5 Solution: We eliminated x from the equations by multiplying L1 by 2 and adding it to L2 - that is, by forming the new equation L = 2L1 + L2 as follows: Dr 2L1 : 2x − 6y = 8 L2 : −2x + 6y = 5 Addition : 0x + 0y = 13 13  The result is a degenerate equation 0x + 0y = 13, which has a nonzero constant b = 13. Thus, this equation and the system have no solution. feh This is expected, because 1/(−2) = −3/6 ̸= 4/5. (Geometrically, the lines corresponding to the equations are parallel.) aq Example 3.3 (Infinite Solutions:). Solve the system L1 : x − 3y = 4 L2 : −2x + 6y = −8 aw We eliminated x from the equations by multiplying L1 by 2 and adding it to L2 - that is, by forming the new equation L = 2L1 + L2 as follows: 2L1 : 2x − 6y = 8 L2 : −2x + 6y = −8 Addition : Sh0x + 0y = 0 he result is the degenerate equation 0x + 0y = 0, where the constant term is also zero. Thus, the system has an infinite number of solutions, which correspond to the solutions of either equation. fa This is expected, because 1/(−2) = −3/6 = 4/(−8). (Geometrically, the lines corresponding to the equations coincide.) To find the general solution, let y = a, and substitute into L1 to obtain x−3a = 4 or x = 3a+4 ta Thus, the general solution of the system is x = 3a + 4, y = a or u = (3a + 4, a) us where a (called a parameter) is any scalar..M 4 Systems in Triangular and Echelon Forms 4.1 Triangular Form Example 4.1. Find the solution for the following system of linear equations, which is in triangular Dr form: 2x1 −3x2 +5x3 −2x4 = 9 5x2 −x3 +3x4 = 1 7x3 −x4 = 3 2x4 = 8 14  Solution: Such a triangular system always has a unique solution, which may be obtained by back-substitution. That is, feh (1) First solve the last equation for the last unknown to get x4 = 4. (2) Then substitute this value x4 = 4 in the next-to-last equation, and solve for the next-to-last unknown x3 as follows: 7x3 − 4 = 3 or 7x3 = 7 or x3 = 1 aq (3) Now substitute x3 = 1 and x4 = 4 in the second equation, and solve for the second unknown x2 as follows: 5x2 − 1 + 12 = 1 or 5x2 + 11 = 1 or 5x2 = −10 or x2 = −2 (4) Finally, substitute x2 = −2, x3 = 1, x4 = 4 in the first equation, and solve for the first aw unknown x1 as follows: 2x1 + 6 + 5 − 8 = 9 or 2x1 + 3 = 9 or 2x1 = 6 or x1 = 3 Thus, x1 = 3, x2 = −2, x3 = 1, x4 = 4, or, equivalently, the vector u = (3, −2, 1, 4) is the unique solution of the system. 4.2 Echelon Form, Pivot and Free Variables Sh fa Definition 16 (Echelon Form). A system of linear equations is said to be in echelon form if ˆ Does not contain any degenerate equation ta ˆ The leading unknown in each equation, other than the first equation, is to the right of the leading unknown in the preceding equation. us Definition 17 (Pivot and Free Variables). Consider a linear system of equation in its echelon.M from, then the leading variables (i.e., the first variable with non-zero coefficient in each equation) are called pivots. The other variables are called free-variables. Example 4.2. Determine the pivot and free variables in each of the following systems: Dr 2x1 −3x2 −6x3 −5x4 +2x5 = 7 2x −6y +7z = 1 x +2y −3z = 2 +x3 +3x4 −7x5 = 6 +4y +3z = 8 2x +3y +z = 4 +3x4 −2x5 = 1 +2z = 4 3x +4y +5z = 8 (a) (b) (c) 15  (a) In echelon form, the leading unknowns are the pivot variables, and the others are the free variables. Here x1 , x3 , x4 are the pivot variables, and x2 and x5 are the free variables. feh (b) The leading unknowns are x; y; z, so they are the pivot variables. There are no free variables (as in any triangular system). (c) The notion of pivot and free variables applies only to a system in echelon form. aq Example 4.3. Find the solution for the following system of linear equations: 2x1 −3x2 −6x3 −5x4 +2x5 = 7 aw +x3 +3x4 −7x5 = 6 +3x4 −2x5 = 1 Solution: Sh This is a system in an echelon form, which can be solved by back-substitution. The leading unknowns are the pivot variables, and the others are the free variables. Here x1 , x3 , x4 are the pivot variables, and x2 and x5 are the free variables. To solve this problem, set x2 = α and x5 = β, where α, β ∈ ℜ. fa (1) Start with the equation 3: 3x4 = 1 + 2x5 −→ x4 = 1+2β 3. ta (2) From equation 2: x3 + 3 1+2β 1+2β 3 − 7β = 6 −→ x3 = 6 − 3 3 + 7β = 5 + 5β. (3) From equation 1: us 2x1 − 3α − 6x3 − 5 1+2β 1+2β 3 + 2β = 7 −→ x1 = 7 + 3α + 6(5 + 5β) + 5 3 − 2β = 38.6667 + 3α + 31.3333β...M   1+2β Thus, the vector u = 38.6667 + 3α + 31.3333β , α , 5 + 5β , 3 , β is the general for the solution of the system. Dr 5 Gaussian Elimination Algorithm 2 (Gaussian Elimination:). 16  ˆ Part A. (Forward Elimination) Step-by-step reduction of the system yielding either a degenerate equation with no solution (which indicates the system has no solution) or an equivalent simpler system in triangular or echelon form. feh ˆ Part B. (Back-Substitution) Step-by-step back-substitution to find the solution of the simpler system. aq Algorithm 3 (Part A: Forward Elimination:). ˆ Step 1: Arrange so that a11 a11 = ̸ 0. That is, if necessary, interchange equations so that the aw first unknown x1 appears with a nonzero coefficient in the first equation. ˆ Step 2: Use a11 as a pivot to eliminate x1 from all equations except the first equation. This is achieved by: a i,1 – Set m = − a1,1. ˆ Step 3: Examine each new equation Li + mL1 Sh – Replace Li by Li + mL1 (i.e., Li ←− Li + mL1 ) – If Li + mL1 is non-degenerate equation: Proceed to Step 4. fa – If Li + mL1 is degenerate equation: * If Li + mL1 has the form 0x1 + 0x2 +... + 0xn = 0, then delete this equation from ta te system and proceed to Step 4. * If Li + mL1 has the form 0x1 + 0x2 +... + 0xn = b; b ̸= 0, then STOP and declare that the system is inconsistent and has no solution. us ˆ Step 4: Repeat the Steps 1-3 with each new ”smaller” subsystem formed by all the equations excluding the first equation..M Note 3. The ”Forward Elimination” step is of recursive nature in the sense that each pivot is used to create zeros below it through repeating Steps 1-3 for each pivot. Note 4. The output of the ”Forward Elimination” step is one of three options: Dr ˆ Triangular form (the number of pivots equals to the number of unknowns): In this case, the system has a unique solution. ˆ Echelon form (the number of pivots less than to the number of unknowns): In this case, the system has infinite solutions. 17  ˆ A degenerate equation with no solution (i.e., 0x1 + 0x2 +... + 0xn = b; b ̸= 0): In this case, the system has no solution (i.e., inconsistent system). feh Example 5.1. Solve the following system using Gaussian Elimination algorithm. x1 +3x2 −2x3 +5x4 = 4 aq 2x1 +8x2 −x3 +9x4 = 9 3x1 +5x2 −12x3 +17x4 = 7 Solution: aw Part A: Forward Elimination ˆ Pivot 1: Starts with the first equation (i.e., L1 ), the pivot variable is x1. Now, we need to cancel x1 from all equations below L1 (i.e., Li ; i > 1): a 2,1 – To remove x1 from L2 , set m = − a1,1 Sh = −2 then replace L2 by L2 − 2L1. That is, L2 ←− L2 − 2L1 = 2x2 + 3x3 − x4 = 1 a – To remove x1 from L3 , set m = − a3,1 1,1 = −3 then replace L3 by L3 − 3L1. That is, L3 ←− L3 − 3L1 = −4x2 − 6x3 + 2x4 = −5 fa The new system after removing x1 becomes: ta x1 +3x2 −2x3 +5x4 = 4 M1 : 2x2 +3x3 −x4 = 1 −4x2 −6x3 +2x4 = −5 us ˆ Pivot 2: Consider the new system M while ignoring the first equation. Pick the second equation (i.e., L2 ), the pivot variable is x2. Now, we need to cancel x2 from all equations below L2 (i.e., Li ; i > 2):.M a 3,2 – To remove x2 from L3 , set m = − a2,2 = 2 then replace L3 by L3 + 2L2. That is, L3 ←− L3 + 2L2 = 0x2 + 0x3 + 0x4 = −3 Since we end up with a degenerate equation with non-zero constant. Then, the system has no solution. DO NOT CONTINUE Dr 18  Example 5.2. Solve the following system using Gaussian Elimination algorithm. x1 +x2 −2x3 +4x4 = 5 feh 2x1 +2x2 −3x3 +x4 = 3 3x1 +3x2 −4x3 −2x4 = 1 Solution: Part A: Forward Elimination aq ˆ Pivot 1: Starts with the first equation (i.e., L1 ), the pivot variable is x1. Now, we need to cancel x1 from all equations below L1 (i.e., Li ; i > 1): a 2,1 – To remove x1 from L2 , set m = − a1,1 = −2 then replace L2 by L2 − 2L1. That is, aw L2 ←− L2 − 2L1 = x3 − 7x4 = −7 a – To remove x1 from L3 , set m = − a3,1 1,1 = −3 then replace L3 by L3 − 3L1. That is, M1 : Sh L3 ←− L3 − 3L1 = 2x3 − 14x4 = −14 The new system after removing x1 becomes: x1 +x2 −2x3 +4x4 = 5 x3 −7x4 = −7 fa 2x3 −14x4 = −14 ˆ Pivot 2: Consider the new system M while ignoring the first equation. Pick the second equation (i.e., L2 ), the pivot variable is x3 (Note: the pivot is not x2 ). Now, we need to ta cancel x3 from all equations below L2 (i.e., Li ; i > 2): a 3,3 – To remove x3 from L3 , set m = − a2,3 = −2 then replace L3 by L3 − 2L2. That is, us L3 ←− L3 − 2L2 = +0x3 + 0x4 = 0 Since we end up with a degenerate equation with zero constant. Then, equation 3 is removed from the system..M The new system after removing x3 becomes: x1 +x2 −2x3 +4x4 = 5 M2 : x3 −7x4 = −7 Now, the new system is in its row-echlon from. Therefore, the system has infinite solutions. The Dr general expression for the solution can be easily determined using Back-Substitution as follows. Part B: Back-Substitution The first step is to determine the free variables and assign them arbitrary values. That is. The free variables are x2 and x4. Set them to arbitrary values x2 = a, x4 = b. Then, we employ a back-substitution procedure to find the values of the pivot variables as follows: 19  ˆ From L2 : x3 − 7x4 = −7 −→ x3 − 7b = 7 −→ x3 = 7b − 7 = 7(b − 1) feh ˆ From L1 : x1 + x2 − 2x3 + 4x4 = 5 −→ x1 + a − 2(7b − 7) + 4b = 5 −→ x1 = 10b − a − 9 Therefore, the general solution x∗ takes the form: aq   10b − a − 9 a x∗ =      7b − 7  b aw 5.1 Gaussian Elimination in Matrix Form Sh This section illustrate how to apply the Gaussian Elimination algorithm in Matrix for rather than equations form. Both forms (equation from or matrix form) are the same and lead to the same result. However, the matrix form is more compact. Besides, it is more suitable to implement the algorithm on computers. fa To illustrate how the matrix form of Gaussian Elimination algorithm works, we will repeat the above two examples (i.e., Example 5.1 and Example 5.2) using the matrix form rather than the standard equation form. ta Example 5.3. Repeat solving the system in Example 5.1 using the Matrix form of Gaussian us Elimination algorithm. Solution: Part A: Forward Elimination.M     1 2 −2 5 4 R2 ←R2 −2R1 1 2 −2 5 4 R3 ←R3 −3R1  2 8 −1 9 9  → ∼  0 2 3 −1 1  3 5 −12 17 7 0 −4 −6 2 −5   1 2 −2 5 4 R3 ←R3 +2R2 → ∼  0 2 3 −1 1  0 0 0 0 −3 Dr Since we end up with a degenerate equation with non-zero constant. Don’t continue. The system has no solution. 20  Example 5.4. Repeat solving the system in Example 5.2 using the Matrix form of Gaussian Elimination algorithm. feh Solution: Part A: Forward Elimination     1 1 −2 4 5 R2 ←R2 −2R1 1 1 −2 4 5 R3 ←R3 −3R1  2 2 −3 1 3  → ∼  0 0 1 −7 −7  aq 3 3 −4 −2 1 0 0 2 −14 −14   1 1 −2 4 5 R3 ←R3 −22R2 → ∼  0 0 1 −7 −7  aw 0 0 0 0 0 Remove the   degenerate equation 1 1 −2 4 5 → ∼ 0 0 1 −7 −7 Now, the new system is in its row-echlon from. Therefore, the system has infinite solutions. The Sh general expression for the solution can be easily determined using Back-Substitution as follows. Part B: Back-Substitution The first step is to determine the free variables and assign them arbitrary values. That is. The free variables are x2 and x4. Set them to arbitrary values x2 = a, x4 = b. Then, we employ a back-substitution procedure to find the values of the pivot variables as follows: fa ˆ The corresponding equation to R2 : x3 − 7x4 = −7 −→ x3 − 7b = 7 −→ x3 = 7b − 7 = 7(b − 1) ta ˆ The corresponding equation to R1 : x1 + x2 − 2x3 + 4x4 = 5 −→ x1 + a − 2(7b − 7) + 4b = 5 −→ x1 = 10b − a − 9 us Therefore, the general solution x∗ takes the form:  .M 10b − a − 9 a x∗ =      7b − 7  b Dr 21  Example 5.5. Solve the following system using Gaussian Elimination algorithm. x1 −3x2 −2x3 = 6 feh 2x1 −4x2 −3x3 = 8 −3x1 +6x2 +8x3 = −5 Solution: This example will be solved in both forms of the Gaussian Elimination algorithm (i.e., aq equation from and matrix form). This example demonstrates that the matrix from is simpler and faster than the equation from. Equation Form Matrix Form Part A: Forward Elimination Part A: Forward Elimination aw Pivot 1: x1   1 −3 −2 6 ˆ To remove x1 from L2 , replace L2 by L2 −  2 −4 −3 8  2L1. That is, −3 6 8 −5   R2 ←R2 −2R1 1 −3 −2 6 L2 ←− L2 − 2L1 → L2 : 2x2 + x3 = −4 3L1. That is, L3 ←− L3 + 3L1 → L3 : −3x2 + 2x3 = 13 Sh ˆ To remove x1 from L3 , replace L3 by L3 − R3 ←R3 +3R1 ∼ R3 ←2R3 +3R2 ∼  0 2  1 −4  0 −3 2 13 1 −3 −2 6  0 2 0 0 7 14  1 −4  fa The new system after removing x1 from L2 and L3 becomes: ta x1 −3x2 −2x3 = 6 2x2 +x3 = −4 −3x2 +2x3 = 13 us Pivot 2: x2 ˆ To remove x3 from L3 , replace L3 by 2L3 + 2L2 (or by L3 + 23 L2 ). That is,.M L3 ←− 3L2 + 2L3 → L3 : 7x3 = 14 The new system after removing x3 from L3 be- comes: x1 −3x2 −2x3 = 6 Dr 2x2 +x3 = −4 7x3 = 14 Part B: Back Substitution 22  Note: The Back Substitution phase is the same for both forms of the Gaussian Elimination Algorithm. The pivots are x1 , x2 , and x3. There are no free variables, and hence, the system admits a unique feh solution as ˆ From L3 : 7x3 = 14 −→ x3 = 2 aq ˆ From L2 : 2x2 + x3 = −4 −→ 2x2 + 2 = −4 −→ x2 = −3 ˆ From L1 : aw x1 − 3x2 − 2x3 = 6 −→ x1 + 9 − 4 = 6 −→ x1 = 1 6 Echelon Matrices, Row Canonical Form, Row Equivalence 6.1 Echelon Matrices Sh Definition 18 (Echelon Matrix). A matrix A is called an echelon matrix, or is said to be in echelon fa form, if the following two conditions hold (where a leading nonzero element of a row of A is the first nonzero element in the row): Property (1) All zero rows, if any, are at the bottom of the matrix. ta Property (2) Each leading nonzero entry in a row is to the right of the leading nonzero entry in the preceding row. us Definition 19 (Pivots of the echelon matrix). The leading nonzero elements in their respective rows, are called the pivots of the echelon matrix..M Example 6.1. The following is an echelon matrix whose pivots have been circled:   0 (2) 3 4 5 9 0 7  0 0 0 (3) 4 1 2 5  Dr   A=  0 0 0 0 0 (5) 7 2    0 0 0 0 0 0 (8) 6  0 0 0 0 0 0 0 0 Observe that the pivots are in columns C2 , C4 , C6 , C7 , and each is to the right of the one above. 23  Using the above notation, the pivots are a12 = 2, a24 = 3, a36 = 5, a47 = 8 feh 6.2 Row Canonical Form aq Definition 20 (Row Canonical Form). A matrix A is called an row canonical form (or row-reduced echelon form), if it is an echelon matrix, and if it satisfies the following additional two properties: Property (3) Each pivot (leading nonzero entry) is equal to 1. aw Property (4) Each pivot is the only nonzero entry in its column. Note 5. The major difference between an echelon matrix and a matrix in row canonical form is Sh that in an echelon matrix there must be zeros below the pivots [Properties (1) and (2)], but in a matrix in row canonical form, each pivot must also equal 1 [Property (3)] and there must also be zeros above the pivots [Property (4)]. fa Example 6.2. The following are echelon matrices whose pivots have been circled. Determine whether they are in row-canonical form or not? ta   (2) 3 2 0 4 5 −6      0 0 0 (1) −3 (1) 2 3 0 (1) 3 0 0 4 2 0    0 0 0  ,  0 0 (1)  ,  0 0 0 (1) 0 −3  0 0 (6) 2  0 0 0 0 0 0 0 (1) 2 us 0 0 0 0 0 0 0 Solution:.M ˆ The first matrix is not in row canonical form, because it satisfies neither property (3) nor property (4); that is, some pivots are not equal to 1 and there are nonzero entries above the pivots. ˆ The second matrix is not in row canonical form, because it does not satisfy property (4); that is, there is a nonzero entry above the second pivot in the third column. ˆ The third matrix is also an example of a matrix in row canonical form. Dr 24  6.3 Elementary Row Operations Suppose A is a matrix with rows R1 , R2 ,... , Rm. The following operations on A are called ele- feh mentary row operations. ˆ [E1 ] (Row Interchange): Interchange rows Ri and Rj. This may be written as ”Interchange Ri and Rj ” or ”Ri ←→ Rj ” ˆ [E2 ] (Row Scaling): Replace row Ri by a nonzero multiple kRi of itself. This may be written aq as ”Replace Ri by kRi (k ̸= 0) ” or ”kRi → Ri ” ˆ [E3 ] (Row Addition): Replace row Rj by the sum of a multiple kRi of a row Ri and itself. aw This may be written as ”Replace Rj by kRi + Rj ” or \kRi + Rj → Rj ” The arrow → in E2 and E3 may be read as ”replaces.” Sometimes (say to avoid fractions when all the given scalars are integers) we may apply [E2 ] and [E3 ] in one step; that is, we may apply the following operation [E] : This may be written as ”Replace Rj by kRi + k ′ Rj (k ′ ̸= 0) ” Sh ˆ [E] Replace Rj by the sum of a multiple kRi of a row Ri and a nonzero multiple k ′ Rj of itself. or ”kRi + k ′ Rj → Rj ” 6.4 Rank of a Matrix fa Definition 21 (Rank of a Matrix). The rank of a matrix A, written rankA, is equal to the number ta of pivots in an echelon form of A. us Note 6. The rank is a very important property of a matrix and, depending on the context in which the matrix is used, it will be defined in many different ways. Of course, all the definitions lead to the same number..M Example 6.3. What is the rank of the following matrices?   (2) 3 2 0 4 5 −6     (1) 2 3 0 (1) 3 0 0 4  0 0 0 (1) −3 2 0  Dr    0 0 ,  0 0 (1)  ,  0 0 0 (1) 0 −3  0 0 0 (6) 2  0 0 0 0 0 0 0 (1) 2 0 0 0 0 0 0 0 Solution: The rank equals to the number of pivots of the matrix, when it is written in its row- echelon from. All matrices are in their row-echelon from. Therefore, 25  ˆ The rank of the first matrix is 3. ˆ The rank of the second matrix is 2. feh ˆ The rank of the third matrix is 3. 6.5 Row Equivalence aq Definition 22 (Row Equivalence). A matrix A is said to be row equivalent to a matrix B, written A ∼ B if B can be obtained from A by a sequence of elementary row operations. In the case that aw B is also an echelon matrix, B is called an echelon form of A. Example 6.4. Convert the following system of linear equations into its row-canonical form and solve it: Sh +3z = 9 x + 5y − 2z = 2 1 3 x + 2y = 3 fa Solution: 1       0 0 3 9 2 0 3 1 6 0 9 ta R1 ↔R3 3 3R1  1 5 −2 2  → ∼  1 5 −2 2  → ∼  1 5 −2 2  1 3 2 0 3 0 0 3 9 0 0 3 9     1 6 0 9 1 6 0 9 us R2 =R2 −R1 −R2 → ∼  0 −1 −2 −7  → ∼  0 1 2 7  0 0 3 9 0 0 3 9     1 0 −12 −33 1 R3 1 0 −12 −33 R1 =R1 −6R2 → ∼  0 1 2 7  → 3∼  0 1 2 7.M  0 0 3 9 0 0 1 3     1 0 0 3 1 0 0 3 R1 =R1 +12R3 R2 =R2 −2R3 → ∼  0 1 2 7  → ∼  0 1 0 1  0 0 1 3 0 0 1 3 Note: In the above solution, all the matrices are row equivalent to each other since we can convert any one of them into the other one by a sequence of elementary r0w operations. Dr From the row-canonical form of the system of liner equations, the solution for the linear system is given by: x = 3, y = 1, z = 3 26  Theorem 6.1. Every matrix A is row equivalent to a unique matrix in row canonical form. feh 7 Homogeneous Systems of Linear Equations aq Definition 23. A system of linear equations is said to be homogeneous if all the constant terms are zeros: Equation 1 (L1 ) : a11 x1 + a12 x2 + · · · + a1n xn =0 Equation 2 (L2 ) : a21 x1 + a22 x2 + · · · + a2n xn =0 (4) aw... Equation m (Lm ) : am1 x1 + am2 x2 + · · · + amn xn = 0 This homogeneous system can be written in a compact matrix form as: , where A is the coefficient matrix given by: A=.  a11  a21  Sh Ax = 0 a12 a22...... a1n a2n   .. ..  fa.  am1 am2... amn ta Solution of Homogeneous systems: us ˆ Zero solution: Homogeneous system always has the zero vector as a solution, called the zero or trivial solution. ˆ Nonzero solutions: Let r denotes the number of equations in echelon form and n denotes the number of unknowns. Nonzero solutions reduces to the following two cases:.M 1. r = n: The system has only the zero solution. 2. r < n: The system has nonzero solutions. Example 7.1. Determine whether or not each of the following homogeneous systems has a nonzero solution: Dr x+y−z =0 x+y−z =0 x1 + 2x2 − 3x3 + 4x4 = 0 2x − 3y + z = 0 2x + 4y − z = 0 2x1 − 3x2 + 5x3 − 7x4 = 0 x − 4y + 2z = 0 3x + 2y + 2z = 0 5x1 + 6x2 − 9x3 + 8x4 = 0 (a) (b) (c) 27  Solution: (a) Reduce the system to echelon form as follows: feh x+y−z =0 x+y−z =0 −5y + 3z = 0 and then −5y + 3z = 0 −5y + 3z = 0 There are two pivots and three unknowns (i.e., there is one free variables). Thus, the system has non-zero solutions. aq (b) Reduce the system to echelon form as follows: x+y−z =0 x+y−z =0 aw 2y + z = 0 and then 2y + z = 0 −y + 5z = 0 11z = 0 There are three pivots and three unknowns (no free variables). Thus, the system has only the zero solution. Sh (c) The system must have a nonzero solution, because there are four unknowns but only three equations. (Here we do not need to reduce the system to echelon form.) 7.1 Basis for the General Solution of a Homogeneous System fa Definition 24 (Basis for the solution of homogeneous system). Let W denote the general solution ta of a homogeneous system Ax = 0. A list of nonzero solution vectors u1 , u2 ,... , us of the system is said to be a basis for W if each solution vector w ∈ W can be expressed uniquely as a linear combination of the vectors u1 , u2 ,... , us ; that is, there exist unique scalars a1 , a2 ,... , as such that us w = a1 u1 + a2 u2 + · · · + as us.M Definition 25 (Dimension of W ). Let W denote the general solution of a homogeneous system Ax = 0. Assume that there are s basis vectors fro W. This number s is called the dimension of W , written as dim W = s, and it is equal to the number of free variables. When W = {0} - that is, the system has only the zero solution we define dim W = 0. The following Dr theorem, proved in Chapter 5, page 171, tells us how to find such a basis. Theorem 7.1 (Finding basis for Ax = 0). Let W be the general solution of a homogeneous system Ax = 0, and suppose that the echelon form of the homogeneous system has s free variables. Let 28  u1 , u2 ,... , us be the solutions obtained by setting one of the free variables equal to 1 (or any nonzero constant) and the remaining free variables equal to 0 Ṫhen the vectors u1 , u2 ,... , us form a basis of W , and dim W = s feh Remark 7.1. We emphasize that the general solution W may have many bases, and that Theorem 7.1 only gives us one such basis. aq aw Example 7.2. Find the dimension and a basis for the general solution W of the homogeneous system x1 + 2x2 − 3x3 + 2x4 − 4x5 = 0 2x1 + 4x2 − 5x3 + x4 − 6x5 = 0 5x1 + 10x2 − 13x3 + 4x4 − 16x5 = 0 Solution: Sh ”Replace L2 by −2L1 + L2 ” and ”Replace L3 by −5L1 + L3 ” and then ”Replace L3 by −2L2 + L3 ” These operations yield x1 + 2x2 − 3x3 + 2x4 − 4x5 = 0 x1 + 2x2 − 3x3 + 2x4 − 4x5 = 0 fa x3 − 3x4 + 2x5 = 0 and x3 − 3x4 + 2x5 = 0 2x3 − 6x4 + 4x5 = 0 The system in echelon form has three free variables, x2 , x4 , x5 ; hence, dim W = 3. Three solution ta vectors that form a basis for W are obtained as follows: (1) Set x2 = 1, x4 = 0, x5 = 0. Back-substitution yields the solution u1 = (−2, 1, 0, 0, 0). us (2) Set x2 = 0, x4 = 1, x5 = 0. Back-substitution yields the solution u2 = (7, 0, 3, 1, 0). (3) Set x2 = 0, x4 = 0, x5 = 1. Back-substitution yields the solution u3 = (−2, 0, −2, 0, 1)..M The vectors u1 = (−2, 1, 0, 0, 0), u2 = (7, 0, 3, 1, 0), u3 = (−2, 0, −2, 0, 1) form a basis for W. Note: Any solution of the system in this Example can be written in the form au1 + bu2 + cu3 = a(−2, 1, 0, 0, 0) + b(7, 0, 3, 1, 0) + c(−2, 0, −2, 0, 1) = (−2a + 7b − 2c, a, 3b − 2c, b, c) Dr 29  7.2 Nonhomogeneous and Associated Homogeneous Systems Definition 26 (Associated homogeneous system). Let Ax = b be a nonhomogeneous system of feh linear equations. Then Ax = 0 is called the associated homogeneous system. Example 7.3. Find the associated homogeneous system of the following nonhomogeneous system: aq x + 2y − 4z = 7 3x − 5y + 6z = 8 aw Solution: The associated homogeneous system is given by: x + 2y − 4z = 0 3x − 5y + 6z = 0 Example 7.4. Let A, b are given by: Sh fa     1 2 4 −2 A =  3 −7 −1  , b= 7  −1 4 2 −4 ta Find the solution of (a) the system Ax = b, and (b) its associated homogeneous system Ax = 0. Solution: us (a) Apply the Gaussain elimination algorithm to the system Ax = b     1 2 4 −2 R2 ←R2 −3R1 1 2 4 −2 R3 ←R3 +R1  3 −7 −1 7  ∼  0 −13 −13 13 .M −1 4 2 −4 0 6 6 −6   1 2 4 −2   R3 ←13R3 +6R2 R2 ←R2 /−13 1 2 4 −2 ∼  0 −13 −13 13  ∼ 0 1 1 −1 0 0 0 0 The pivots are x1 and x2 , and the free variable is x3. Let x3 = t ∈ ℜ. Then, Dr ˆ From L2 : x2 + x3 = −1 −→ x2 = −1 − t ˆ From L1 : x1 + 2x2 + 4x3 = −2 −→ x1 − 2 − 2t + 4t = −2 −→ x1 = −2t 30  Then, the general solution x∗ of Ax = b is given by:   −2t feh x∗ =  −1 − t  t (b) Apply the Gaussain elimination algorithm to the system Ax = 0 aq     1 2 4 0 R2 ←R2 −3R1 1 2 4 R3 ←R3 +R1  3 −7 −1 0  ∼  0 −13 −13  −1 4 2 0 0 6 6   1 2 4   1 2 4 aw R3 ←13R3 +6R2 R2 ←R2 /−13 ∼  0 −13 −13  ∼ 0 1 1 0 0 0 The pivots are x1 and x2 , and the free variable is x3. Let x3 = t ∈ ℜ. Then, ˆ From L2 : ˆ From L1 : Sh x2 + x3 = 0 −→ x2 = −t x1 + 2x2 + 4x3 = 0 −→ x1 − 2t + 4t = 0 −→ x1 = −2t fa Then, the general solution xh of Ax = 0 is given by:     −2t −2 ta xh =  −t  =  −1  t t 1 us Now, let us dig deeply into the solution of the above example. First, let us find particular solutions of the system Ax = b (by picking specific values of t). For instant:.M   0 ˆ Let x∗0 be the solution of Ax = b when t = 0. That is, x∗0 =  −1  0   −2 ˆ Let x∗1 be the solution of Ax = b when t = 1. That is, x∗1 =  −2  Dr 1   −4 ˆ Let x∗2 be the solution of Ax = b when t = 2. That is, x∗2 =  −3  2 31  Note that each solution of the system Ax = b can be decomposed into two components. The first component is a particular solution (i.e., xp ) and the second component is scaled version of the solution of the associated homogeneous system (i.e., tx∗h ). That is: feh   −2 x∗ = xp + xh = xp +  −1  t (5) 1 To illustrate: aq   0 ˆ Let xp = x∗0 =  −1 . Then, 0 aw           −2 0 −2 −2 x∗1 = xp +  −1  t =  −1  +  −1  =  −1  1 t=1 0 1 1           −2 0 −4 −4 x∗2 = xp +  −1  t =  −1  +  −2  =  −3   −2  ˆ Let xp = x∗1 =  −2 . Then, 1 1 t=2 Sh 0 2 2 fa           −2 −2 2 0 x∗0 = xp +  −1  t =  −2  +  1  =  −1  1 t=−1 1 −1 0 ta           −2 −2 −2 −4 x∗2 = xp +  −1  t =  −2  +  −1  =  −3  1 t=1 1 1 2 us   −4 ˆ Let xp = x∗2 =  −3 . Then, 2.M           −2 −4 4 0 x∗0 = xp +  −1  t =  −3  +  2  =  −1  1 t=−2 2 −2 0           −2 −4 2 −2 x∗1 = xp +  −1  t =  −3  +  1  =  −2  1 2 −1 1 Dr t=−1 In summary, we can observe that the general solution of the equation Ax = b admits the following form: x∗ = (Any Particular Solution of Ax = b) + (General Solution of Ax = 0) This result is stated formally in the following Theorem 7.2 32  Theorem 7.2. Let xp be a particular solution of Ax = b, let xh be the general solution of the associated homogeneous system Ax = 0, and x∗ be the general solution of Ax = b. Then, feh x∗ = xp + x h ˆ Theorem 7.2 governs the relationship between the solution of a nonhomogeneous system aq Ax = b and the solution of its associated homogeneous system Ax = 0. ˆ It states that any solution of Ax = b can be decomposed into two components: (i) particular (or specific) solution of Ax = b and the general solution of the associated homogeneous aw system Ax = 0. That is: x∗ = (Any Particular Solution of Ax = b) + (General Solution of Ax = 0) Example 7.5. Let A, b are given by:  3 1 1  Sh A =  1 1 −1  , 4 2 0  4  b =  −2  2 Express the solution of the system Ax = b as the sum of a particular solution and the general solution of the associated homogeneous system (i.e., x∗ = xp + xh ). fa Solution: ta     3 1 1 4 R2 ←3R2 −R1 3 1 1 4 R3 ←3R3 −4R1  1 1 −1 −2  ∼  0 2 −4 −10  4 2 0 2 0 2 −4 −10   3 1 1 4 us   R3 ←R3 −R2  0 2 −4 −10  R2 ←R2 /2 3 1 1 4 ∼ ∼ 0 1 −2 −5 0 0 0 0 The pivots are x1 and x2 , and the free variable is x3. Let x3 = t ∈ ℜ. Then,.M ˆ From L2 : x2 − 2x3 = −5 −→ x2 = 2t − 5 ˆ From L1 : 3x1 + x2 + x3 = 4 −→ 3x1 + 2t − 5 + t = 4 −→ x1 = 3 − t Dr Then, the general solution x∗ of Ax = b is given by:   3−t x∗ =  2t − 5  t 33  There are infinite options to decompose x∗ into xp + xh. The simplest one can be obtained when having the particular solution at t = 0. That is: feh   3 x∗ =  −5  0 and the associated xh is obtained by aq     −t −1 xh = x∗ − xp =  2t  =  2  t t 1. aw 8 Finding the Inverse of an n × n Matrix Sh The following algorithm finds the inverse of a matrix. Algorithm 4. The input is a square matrix A. The output is the inverse of A or that the inverse does not exist. fa ˆ Step 1. Form the n × 2n (block) matrix M = [A, I], where A is the left half of M and the identity matrix I is the right half of M. ta ˆ Step 2. Row reduce M to echelon form. If the process generates a zero row in the A half of M , then STOP A has no inverse. (Otherwise A is in triangular form.) ˆ Step 3. Further row reduce M to its row canonical form us M ∼ [I, B] where the identity matrix I has replaced A in the left half of M..M ˆ Step 4. Set A−1 = B, the matrix that is now in the right half of M. Example 8.1. Find the inverse of the matrix Dr   1 0 2 A =  2 −1 3  4 1 8 Solution: 34  First form the (block) matrix M = [A, I] and row reduce M to an echelon form:       1 0 2 1 0 0 1 0 2 1 0 0 1 0 2 1 0 0 feh M =  2 −1 3 0 1 0  ∼  0 −1 −1 −2 1 0  ∼  0 −1 −1 −2 1 0  4 1 8 0 0 1 0 1 0 −4 0 1 0 0 −1 −6 1 1 In echelon form, the left half of M is in triangular form; hence, A has an inverse. Next we further row reduce M to its row canonical form: aq     1 0 0 −11 2 2 1 0 0 −11 2 2 M ∼  0 −1 0 4 0 −1  ∼  0 1 0 −4 0 1  0 0 1 6 −1 −1 0 0 1 6 −1 −1 The identity matrix is now in the left half of the final matrix; hence, the right half is A−1. In other aw words,   −11 2 2 A−1 =  −4 0 1  6 −1 −1 Sh fa ta us.M Dr 35