# Gaussian elimination

Gaussian elimination is a systematic strategy for solving a set of linear equations. It can also be used to construct the inverse of a matrix and to factor a matrix into the product of lower and upper triangular matrices. We start by solving the linear system

Basically, the objective of Gaussian elimination is to do transformations on the equations that do not change the solution, but systematically zero out (eliminate) the off-diagonal coefficients, leaving a set of equations from which we can read off the answers.

We express the problem in terms of a set of equations, and side-by-side, we express it in terms of an equivalent matrix product. We do this to show how the manipulations in the matrix tracks the manipulations of the equations, where it is easier to see that we are not changing the solution.

The method has two parts. First triangulation'' and then back substitution''.

## Triangulation

Equations Matrix-vector representation

 Starting equation
 Equivalent matrix-vector equation

 First step: examine the coefficients of . Swap equations (1) and (3) so the largest coefficient is in the first equation (first row). This is called the pivot'' element.
 Swap the first the third rows of the matrix and the first and third elements of the vector on the right side. Note that in the matrix equation we don't interchange and .

 Next step: Divide the first equation by the coefficient to make the pivot element equal to .

 Next step: Multiply the first equation by 2 and subtract it from the second equation, putting the result in the second equation. This eliminates'' the coefficient of in the second equation.

 Next step: Eliminate the coefficient of in the third equation by subtracting the first equation from the third, putting the result into the third equation.
 Next step: Now work on the second column (coefficients ). We want the largest coefficient in the second equation (diagonal element in the matrix.) So swap the second and third equation.

 Now divide by 5/3, the pivot element in the second column.

 Now eliminate the coefficient of in the third equation by multiplying the second equation by 1/3, subtracting the result from the third equation, and putting the result in the third equation.

 To complete the triangulation'' step we divide the third equation by the coefficient of , namely .
 Notice that the matrix is now in upper triangular form - all elements below the diagonal are zero.

## Back substitution

 Next, we do back substitution.'' We start by noticing that the last equation gives us the solution for . Then we work our way up the third column, eliminating the coefficients of - this is just Gaussian elimination backwards! But it amounts to the same thing as plugging in the solution for into the other two equations and moving the resulting constant to the rhs of the equation. So multiply the third equation by and subtract from equation two, leaving the result in equation two.
 Notice that the matrix is now in upper triangular form - all elements below the diagonal are zero.

 Continuing on the third column, eliminate the coefficient of in equation 1.

 Next, work on the second column. We have only the coefficient of in the first equation to eliminate. We then get the answer.
 Notice that we now have a unit matrix, so the solution can be read off.

 The last step, of course, is to check the solution by plugging it in to the orginal system of equations.