MATH 304Linear AlgebraLecture 2:Gaussian elimination.Row echelon form.Gauss-Jordan reduction.System of linear equationsa11x1+ a12x2+ ··· + a1nxn= b1a21x1+ a22x2+ ··· + a2nxn= b2·········am1x1+ am2x2+ ··· + amnxn= bmHere x1, x2, . . . , xnare variables and aij, bjareconstants.A solution of the system is a common solution of allequations in the system.A system of linear eq uations can have one solution,infinitely many solutions, or no solution at all.xyx − y = −22x + 3y = 6x = 0, y = 2xy2x + 3y = 22x + 3y = 6inconsistent system(no solutions)xy4x + 6y = 122x + 3y = 6⇐⇒ 2x + 3y = 6Solving systems of linear equationsElimination method always works for systems oflinear equations.Algorithm: (1) pick a variable, solve one of theequations for it, and eliminate it from the otherequations; (2) put aside the equation used in theelimination, and return to step (1).x − y = 2 =⇒ x = y + 22x − y − z = 5 =⇒ 2(y + 2) − y − z = 5After the elimination is completed, the syste m issolved by back substitution.y = 1 =⇒ x = y + 2 = 3Gaussian eliminationGaussian elimination is a modification of theelimination method that allows only so-calledelementary operations.Elementary operations for systems of linear equations:(1) to multiply an equation by a nonzero scalar;(2) to add an e quation multiplied by a scalar toanother equation;(3) to interchange two equ ations.Proposition Any elementary operation can beundone by app lying another elementary operation.Operation 1: multiply the ith equation by r 6= 0.a11x1+ a12x2+ ··· + a1nxn= b1············ai1x1+ ai2x2+ ··· + ainxn= bi············am1x1+ am2x2+ ··· + amnxn= bm=⇒a11x1+ a12x2+ ··· + a1nxn= b1············(rai1)x1+ (rai2)x2+ ··· + (rain)xn= rbi············am1x1+ am2x2+ ··· + amnxn= bmTo undo the operation, multiply the ith equation by r−1.Operation 2: add r times the ith equation to thejth equation.············ai1x1+ ai2x2+ ··· + ainxn= bi············aj1x1+ aj2x2+ ··· + ajnxn= bj············=⇒············ai1x1+ ··· + ainxn= bi············(aj1+ rai1)x1+ ··· + (ajn+ rain)xn= bj+ rbi············To undo the operation, add −r times the ithequation to the jth equation.Operation 3: interchange the ith and jth equations.············ai1x1+ ai2x2+ ··· + ainxn= bi············aj1x1+ aj2x2+ ··· + ajnxn= bj············=⇒············aj1x1+ aj2x2+ ··· + ajnxn= bj············ai1x1+ ai2x2+ ··· + ainxn= bi············To undo the operation, apply it once more.Proposition Any elementary operation can beundone by app lying another elementary operation.Theorem Applying elementary operations to asystem of linear equations does not change thesolution set of the system.Proof: It is easy to see t hat after an elementaryoperation we do not lose any solution. Since theoperation can be undone by another elementaryoperation, neither we get any garbage solutions.Solution of a system of linear eq uations splits intotwo p arts: (A) elimination and (B) backsubstitution. Both parts can be done by applyin g afinite number of elementary operations.Example.x − y = 22x − y − z = 3x + y + z = 6→x − y = 2y − z = −12y + z = 4→x − y = 2y − z = −13z = 6→x = 3y = 1z = 2Another example.x + y − 2z = 1y − z = 3−x + 4y − 3z = 1Add the 1st equation to the 3rd eq uation:x + y − 2z = 1y − z = 35y − 5z = 2Add −5 times the 2nd equation to the 3rd equation:x + y − 2z = 1y − z = 30 = −13System of linear equations:x + y − 2z = 1y − z = 3−x + 4y − 3z = 1Solution: no solution (inconsistent system).Yet another example.x + y − 2z = 1y − z = 3−x + 4y − 3z = 14Add the 1st equation to the 3rd eq uation:x + y − 2z = 1y − z = 35y − 5z = 15Add −5 times the 2nd equation to the 3rd equation:x + y − 2z = 1y − z = 30 = 0Add −1 times the 2nd equation to the 1st equation:x − z = −2y − z = 30 = 0⇐⇒x = z − 2y = z + 3Here z is a free variable.It follows thatx = t −2y = t + 3z = tfor some t ∈ R.System of linear equations:x + y − 2z = 1y − z = 3−x + 4y − 3z = 14Solution: (x, y, z) = (t − 2, t + 3, t), t ∈ R.In vector form, (x, y, z) = (−2, 3, 0) + t(1, 1, 1).MatricesDefinition. A matrix is a rectangular array of numbers.Examples:2 7−1 03 3,2 7 0.24.6 1 1,3/55/84, (√2, 0, −√3, 5),1 10 1.dimensions = (# of rows) × (# of columns)n-by-n : square matrixn-by-1: column vector1-by-n: row vectorSystem of linear equations:a11x1+ a12x2+ ··· + a1nxn= b1a21x1+ a22x2+ ··· + a2nxn= b2·········am1x1+ am2x2+ ··· + amnxn= bmCoefficient matrix and column vector of theright-hand sides:a11a12. . . a1na21a22. . . a2n............am1am2. . . amnb1b2...bmSystem of linear equations:a11x1+ a12x2+ ··· + a1nxn= b1a21x1+ a22x2+ ··· + a2nxn= b2·········am1x1+ am2x2+ ··· + amnxn= bmAugmented matrix:a11a12. . . a1nb1a21a22. . . a2nb2...............am1am2. . . amnbmElementary operations for systems of linearequations correspond to elementary row operationsfor augmented matrices:(1) to multiply a row by a nonzero scalar;(2) to add the i th row multiplied by some r ∈ R tothe jth row;(3) to interchange two rows.Remark. Rows are added and multiplied by scalarsas vectors (n amely, row vectors).Elementary row operationsAugmented matrix:a11a12. . . a1nb1a21a22. . . a2nb2...............am1am2. . . amnbm=v1v2...vm,where vi= (ai1ai2. . . ain|bi) is a row vector.Elementary row operationsOperation 1: to multiply the ith row by r 6= 0:v1...vi...vm→v1...rvi...vmElementary row operationsOperation 2: to add the ith row multiplied by r tothe jth
View Full Document