Systems of Linear Equations - Hong Kong University of ...

1 Systems of Linear EquationsBeifang Chen1 Systems of Linear equationsLinear systemsAlinear equationin variablesx1, x2, .. , xnis an equation of the forma1x1+a2x2+ +anxn=b,wherea1, a2, .. , anandbare constant real or complex numbers. The constantaiis called thecoefficientofxi; andbis called theconstant termof the of Linear Equations (orlinear system ) is a finite collection of Linear Equations in samevariables. For instance, a Linear system ofmequations innvariablesx1, x2, .. , xncan be written as a11x1+a12x2+ +a1nxn=b1a21x1+a22x2+ +a2nxn= +am2x2+ +amnxn=bm( )Asolutionof a Linear system ( ) is a tuple (s1, s2, .. , sn) of numbers that makes each equation a truestatement when the valuess1, s2, .. , snare substituted forx1, x2.

2 , xn, respectively. The set of all solutionsof a Linear system is called thesolution setof the system of Linear Equations has one of the following exclusive conclusions.(a)No solution.(b)Unique solution.(c)Infinitely many Linear system is said to beconsistentif it has at least one solution; and is said to beinconsistentifit has no interpretationThe following three Linear Systems (a) 2x1+x2= 32x1 x2= 0x1 2x2= 4(b) 2x1+x2= 32x1 x2= 5x1 2x2= 4(c) 2x1+x2= 34x1+2x2= 66x1+3x2= 9have no solution, a unique solution, and infinitely many solutions, respectively. See Figure : A Linear equation of two variables represents a straight line inR2. A Linear equation of three vari-ables represents a plane general, a Linear equation ofnvariables represents a hyperplane in then-dimensional Euclidean of a Linear system1ox1x2ox1x2ox1x2 Figure 1: No solution, unique solution, and infinitely many matrixof the general Linear system ( ) is the table a11a12.

3 A1nb1a21a22.. amnbm ( )and thecoefficient matrixof ( ) is a11a12.. a1na21a22.. amn ( )2 Systems of Linear Equations can be represented by matrices. Operations on Equations (for eliminatingvariables) can be represented by appropriate row operations on the corresponding matrices. For example, x1+x2 2x3= 12x1 3x2+x3= 83x1+x2+4x3= 7 1 1 212 3 1 83 1 47 [Eq 2] 2[Eq 1][Eq 3] 3[Eq 1]R2 2R1R3 3R1 x1+x2 2x3=1 5x2+5x3= 10 2x2+10x3=4 1 1 210 5 5 100 2 104 ( 1/5)[Eq 2]( 1/2)[Eq 3]( 1/5)R2( 1/2)R3 x1+x2 2x3= 1x2 x3= 2x2 5x3= 2 1 1 210 1 120 1 5 2 [Eq 3] [Eq 2]R3 R2 x1+x2 2x3= 1x2 x3= 2 4x3= 4 1 1 210 1 120 0 4 4 ( 1/4)[Eq 3]( 1/4)R3 x1+x2 2x3= 1x2 x3= 2x3= 1 1 1 210 1 120 0 11 [Eq 1] + 2[Eq 3][Eq 2] + [Eq 3]R1+ 2R3R2+R3 x1+x2= 3x2= 3x3= 1 1 1 030 1 030 0 11 [Eq 1] [Eq 2]R1 R2 x1= 0x2= 3x3= 1 1 0 000 1 030 0 11 Elementary row operationsDefinition are three kinds of elementary row operations on matrices.

4 (a)Adding a multiple of one row to another row;(b) Multiplying all entries of one row by a nonzero constant;(c)Interchanging two Linear Systems in same variables are said to beequivalentif their solution sets arethe same. A matrixAis said to berow equivalentto a matrixB, writtenA B,if there is a sequence of elementary row operations that the augmented matrices of two Linear Systems are row equivalent, then the two systemshave the same solution set. In other words, elementary row operations do not change solution is trivial for the row operations (b) and (c) in Definition Consider the row operation (a) inDefinition Without loss of generality, we may assume that a multiple of the first row is added to thesecond row.

5 Let us only exhibit the first two rows as follows a11a12.. a1nb1a21a22.. amnbm ( )Do the row operation (Row 2) +c(Row 1). We obtain a11a12..a1nb1a21+ca11a22+ca22.. a2n+ca2nb2+cb1a31a32..amnbm ( )Let (s1, s2, .. , sn) be a solution of ( ), that is,ai1s1+ai2s2+ +ainsn=bi,1 i m.( )In particular,a11s1+a12x2+ +a1nsn=b1,( )a21s1+a21x2+ +a2nsn=b2.( )Multiplyingcto both sides of ( ), we haveca11s1+ca12+ +ca1nsn=cb1.( )Adding both sides of ( ) and ( ), we obtain(a21+ca11)s1+ (a22+ca12)s2+ + (a2n+ca1n)sn=b2+cb1.( )This means that (s1, s2, .. , sn) is a solution of ( ).Conversely, let (s1, s2, .. , sn) be a solution of ( ), , ( ) is satisfied and the Equations of ( ) aresatisfied except fori= 2. Sincea11s1+a12x2+ +a1nsn=b1,multiplyingcto both sides we havec(a11s1+a12+ +a1nsn) =cb1.

6 ( )Note that ( ) can be written as(a21s1+a22s2+ +a2nsn) +c(a11s1+a12s2+ +a1nsn) =b2+cb1.( )Subtracting ( ) from ( ), we havea21s1+a22s2+ +a2nsn= means that (s1, s2, .. , sn) is a solution of ( ).42 Row echelon formsDefinition matrix is said to be inrow echelon formif it satisfies the following two conditions:(a)All zero rows are gathered near the bottom.(b)The first nonzero entry of a row, called theleading entryof that row, is ahead of the first nonzeroentry of the next matrix in row echelon form is said to be inreduced row echelon formif it satisfies two more conditions:(c)The leading entry of every nonzero row is 1.(d)Each leading entry 1 is the only nonzero entry in its matrix in (reduced) row echelon form is called a(reduced) row echelon we call row echelon forms just as echelon forms and row echelon matrices as echelonmatrices without mentioning the word row.

7 Row echelon form patternThe following are two typical row echelon matrices. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 , 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 where the circled stars represent arbitrary nonzero numbers, and the stars represent arbitrary numbers,including zero. The following are two typical reduced row echelon matrices. 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 , 0 1 0 0 0 00 0 0 0 1 0 0 00 0 0 0 0 0 1 0 00 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 Definition a matrixAis row equivalent to a row echelon matrixB, we say thatAhas therowechelon formB; ifBis further a reduced row echelon matrix, then we say thatAhas thereduced rowechelon reduction algorithmDefinition positionof a matrixAis a location of entries ofAthat corresponds to a leadingentry in a row echelon form ofA.

8 Apivot column(pivot row) is a column (row) ofAthat contains apivot (Row Reduction Algorithm).(1)Begin with the leftmost nonzero column, which isapivot column; the top entry is apivot position.(2)If the entry of the pivot position is zero, select a nonzero entry in the pivot column, interchange thepivot row and the row containing this nonzero entry.(3)If the pivot position is nonzero, use elementary row operations to reduce all entries below the pivotposition to zero, (and the pivot position to 1 and entries above the pivot position to zero for reducedrow echelon form).(4)Cover thepivot rowand the rows above it; repeat (1)-(3) to the remaining matrix is row equivalent to one and only one reduced row echelon matrix.

9 In otherwords, every matrix has a unique reduced row echelon Row Reduction Algorithm show the existence of reduced row echelon matrix for any only need to show the uniqueness. SupposeAandBare two reduced row echelon forms for a matrixM. Then the systemsAx=0andBx=0have the same solution set. WriteA= [aij] andB= [bij].We first show thatAandBhave the same pivot columns. Leti1, .. , ikbe the pivot columns ofA, andletj1, .. , jlbe the pivot columns ofB. Supposei1=j1, .. , ir 1=jr 1, butir6=jr. Assumeir< theirth row ofAis[0, .. ,0,1, ar,ir+1, .. , ar,jr, ar,jr+1, .. , ar,n].While thejrth row ofBis[0, .. ,0,1, br,jr+1, .. , br,n].Sinceir 1=jr 1andir< jr, we havejr 1< ir< jr. Soxiris a free variable forBx=0. Letui1= b1,ir.

10 , uir 1= br 1,ir, uir= 1,andui= 0 fori > a solution ofBx=0, but is not a solution ofAx=0. This is a contradiction. Of course,k= we show that for 1 r k=l, we havearj=brj, jr+ 1 j jr+1 , we havear0j06=br0j0such thatr0is smallest and thenj0is smallest. Setuj0= 1, ui1= a1,j0, .. , ur0= ar0j0,anduj= 0 a solution ofAx=0, but is not a solution ofBx=0. This is a Linear systemExample all solutions for the Linear system x1+2x2 x3= 12x1+x2+4x3= 23x1+3x2+4x3= the row operations: 1 2 112 1 423 3 41 R2 2R1 R3 3R1 1 2 110 3 600 3 7 2 ( 1/3)R2 R3 R2 1 2 110 1 200 0 1 2 R1+R3 R2+ 2R3 1 2 0 10 1 0 40 0 1 2 R1 2R2 1 0 070 1 0 40 0 1 2 The system is equivalent to x1= 7x2= 4x3= 2which means the system has a unique the Linear system x1 x2+x3 x4= 2x1 x2+x3+x4= 04x1 4x2+4x3= 4 2x1+2x2 2x3+x4= the row operations.