Gaussian Elimination

Edited 1/26/2005

Linear Algebra Topics--Solving Systems of Equations

Matrix for a System of Linear Equations

The first step in solving a system of linear equations is to construct a matrix corresponding to the system of equations.  This is done by making the coefficients in the equations into the rows of a matrix.  This is called the coefficient matrix for the system.  The coefficient matrix for the system x+y+z=1, x-2y+3z=2, -x-y+7z=3 is

Coefficient Matrix for the system x+y+z=1, x-2y+3z=2, -x-y+7z=3

coeffientmat={{1,1,1},{1,-2,3},{-1,-1,7}}

When the right hand sides are appended to the coefficient matrix as a last column, you get the augmented matrix for the system.  This is shown next.

Augmented Matrix for the system x+y+z=1, x-2y+3z=2, -x-y+7z=3

augmentedmat={{1,1,1,1},{1,-2,3,2},{-1,-1,7,3}}

The last column consists of the right hand sides of the equations.  In solving non-homogeneous systems of equations you will always want to work with the augmented matrix of the system of equations.

Row-Echelon and Reduced Row-Echelon Forms, i.e. Upper Triangular Forms

To find solutions of systems of equations most efficiently you will want to use row operations on the augmented matrix of the system to bring it into, at least, row-echelon form.  Row-echelon form is essentially an upper triangular form for a matrix.

A Matrix is in Row-Echelon Form if the following 3 conditions are satisfied:

(1) If a row does not consist entirely of zeros, then the first nonzero number in the row is a 1--this 1 is called a leading 1.
(2) If there are any rows that consist entirely of zeros, then they are grouped together at the bottom of the matrix.
(3) In any two successive rows that do not consist entirely of zeros, the leading 1 in the lower row occurs farther to the right than the leading 1 in the higher row.

A matrix is in Reduced Row-Echelon Form if it is in Row-Echelon Form with the additional condition that every column that contains a leading 1 has zeros everywhere else in that column.

mat2, mat3, and mat4 shown below are all in row-echelon form.  If you were to add -4 times row 2 of mat4 to row 1 of mat4, the resulting matrix would be in reduced row-echelon form.

mat2={{1,2,3,4},{0,3,4,5},{0,0,2,7}}

mat3={{1,2,3,4},{0,3,4,5}}

mat4={{1,2,3,4},{0,0,0,1}}

Row Operations

Reducing a matrix to row-echelon or upper triangular form, that is performing Gaussian Elimination, is carried out by applying some combination of the three basic matrix row operations defined in this section to the matrix.  The three allowable row operations (allowable in the sense that solutions of the system of equations represented by the matrix are not changed) are:

(1) A nonzero multiple of any row may be added to any other row.

A command to carry this out is defined is defined below and has the form 
	rowadd[scalar,r1,r2,mat] 
This adds scalar times row number r1 to row number r2 of matrix mat.

(2) A row may be multiplied by a nonzero constant.

A command to carry this out is defined is defined below and has the form
	rowmultiply[scalar,r1,mat]
This multiplies row number r1 of matrix mat by scalar.

(3) Any two rows may be interchanged.

A command to carry this out is defined is defined below and has the form
	rowexchange[r1,r2,mat] 
This exchanges rows numbered r1 and r2 of matrix mat.

To use these statements, you must supply the arguments.  Examples follow.

Example:

Suppose that you would like to reduce the following matrix to upper triangular form.  The matrix represents the system of equations x+2y=3, 4x+5y=6, 7x+8y=9.

newmat={{1,2,3},{4,5,6},{7,8,9}}

To do this you would first apply row operations that result in zeros where 4 and 7 appear.  To replace the 4 by zero add -4 times the first row to the second row.  Name this new matrix newmat1.  You would use the rowadd command

newmat1=rowadd[-4,1,2,newmat]

Next, using newmat1, add -7 times row 1 to row 3 and name the resulting matrix newmat2.

newmat2=rowadd[-7,1,3,newmat1]

Now, using newmat2, add -2 times row 2 to row 3 and name the resulting matrix newmat3.

newmat3=rowadd[-2,2,3,newmat2]

Finally, to get a 1 on the diagonal where -3 appears multiply row 2 by -1/3.

newmat4=rowmultiply[-1/3,2,newmat3]

newmat4 is in upper triangular form.  At this stage Gaussian elimination is complete--the solution could be found by back-substitution.  The four steps could have been nested as follows.

newmat4=
rowmultiply[-1/3,2,rowadd[-2,2,3,
	rowadd[-7,1,3,rowadd[-4,1,2,newmat]]]]

You might want to find the solution of this system by applying further row operations to newmat4.  Only one step is needed, and this step is to produce a 0 where the 2 appears in row 1.

newmat5=rowadd[-2,2,1,newmat4]

Now, the solution y=2 and x=-1 can be read directly from this matrix.

Gaussian Elimination and Upper Triangular Form

The most efficient method for solving systems of linear equations is called Gaussian elimination.  In Gaussian elimination the coefficient matrix of the system is reduced to upper triangular form, that is row operations are performed on the matrix until it has zeros below the main diagonal of the coefficient portion.  mat2, mat3, and mat4 above are all in upper triangular form.

The solution of any upper triangular matrix can be easily found by back-substitution.  For example, the last row of mat2, represents 2z=7 so z=7/2, and then moving up one row, the middle row represents the equation 3y+4z=5, from which y can be found, and finally moving back to the first row, the first row represents the equation x+2y+3z=4, so x can be found.  

Considering mat3, the second row represents 3y+4z=5.  In this case, you can make z any real number, say z=t.  Then y=(5-4t)/3.  From the first row, x+2y+3z=4, so x=4-2y-3z=4-2((5-4t)/3)-3t.  Thus, there are an infinite number of solutions, one for each value that is assigned to t.

Looking at mat4, the last row represents 0x+0y=1.  There is no solution for this system.

Reducing a system of equations to upper triangular form provides the means to find all solutions regardless of whether there is a unique solution, an infinite number of solutions, or no solution.

Mathematica Commands for Solving Systems of Equations

Any computer algebra system should have a means of solving such a system of equations directly.  The Mathematica Solve command is one way of finding solutions.  Before Solve is used (and you should do this whenever there is a possibility that you may have previously defined values for certain symbols), the Clear command is applied to the symbols x and y.  This removes any values that the symbols may have been assigned earlier in this computer session.  Notice the double equal (==) sign used in Solve.  A single equal in Mathematica is the assignment statement, that is x=2 would assign the value 2 to the symbol x, while a double equal is the check for equality, that is, x==2 would give true if x were 2 and false if x were not 2.

Clear[x,y]

Solve[{x+2y==3,4x+5y==6,7x+8y==9},{x,y}]

A second command for finding solutions of a system of equations is the Reduce command.  It differs from the Solve command in that all special cases are considered in the solution that it produces.  For example, the Solve command applied to the equation a x=3 where a is any number gives (note that the solution is given as a "replacement rule")

Solve[a x==3,{x,y}]

However, there is certainly not a solution when a is 0.  The reduce command shown next makes this clear (a != 0 means a cannot be zero, and when a is not zero, then x=3/a)

Reduce[a x==3,{x,y}]

Applied to the system considered above Reduce gives

Reduce[{x+2y==3,4x+5y==6,7x+8y==9},{x,y}]

A third built-in command that can be used to find the solution of a system of linear equations is the RowReduce command.  It can be applied to the augmented matrix of the system that was solved above.

RowReduce[{{1,2,3},{4,5,6},{7,8,9}}]

From the output of this command, you can find the solution of the non-homogeneous system x+2y=3, 4x+5y=6, and 7x+8y=9.  The solution is x=-1 and y=2.

Exercise 1

Use a sequence of row operations to reduce the matrix for the system 3x+2y-z=-15, 5x+3y+2z=0, 3x+y+3z=11, -6x-4y+2z=30 to upper triangular form.

Exercise 2

Using the upper triangular matrix from exercise 1, find the solution of the system by applying further row operations.

Exercise 3

Find the solution of the system in exercise 1 by using the Mathematica Solve command.

Exercise 4

Find the solution of the system in exercise 1 by using the Mathematica RowReduce command.

Functions Used in this notebook

$Post=If[MatrixQ[#],MatrixForm[#] ,#]&;

rowadd[scalar_,r1_,r2_,mat_]:=
	Module[{result,mat1=mat},
  	mat1[[r2]]=(scalar mat1[[r1]])+mat1[[r2]];
	mat1
	]

rowmultiply[scalar_,r1_,mat_]:=
	Module[{mat1=mat},
	mat1[[r1]]=scalar mat1[[r1]];
	mat1
	]

rowexchange[r1_,r2_,mat_]:=
	Module[{mat1=mat,temp},
	temp=mat1[[r1]];
	mat1[[r1]]=mat[[r2]];
	mat1[[r2]]=temp;
	mat1
	]