Gaussian elimination

Gaussian elimination is an algorithm for solving systems of linear equations, finding the rank of a matrix, and calculating the inverse of an invertible square matrix. Gaussian elimination is named after German mathematician and scientist Carl Friedrich Gauss.

Elementary row operations are used to reduce a matrix to row echelon form. Gauss–Jordan elimination, an extension of this algorithm, reduces the matrix further to reduced row echelon form. Gaussian elimination alone is sufficient for many applications.

Example

Suppose the goal is to find and describe the solution(s), if any, of the following system of linear equations:

The algorithm is as follows: eliminate x from all e

quations below L₁, and then eliminate y from all equations below L₂. This will put the system into triangular form. Then, using back-substitution, each unknown can be solved for.

In the example, x is eliminated from L₂ by adding 3/2

L1 to L₂. x is then eliminated from L₃ by adding L₁ to L₃. Formally:

The result is:

Now y is eliminated from L₃ by adding − 4L₂ to L₃:

The result is:

This result is a system of linear equations in triangular form, and so the first part of the algorithm is complete.

The second part, back-substitution, consists of solving for the unknowns in reverse order. It can thus be seen that

Then, z can be substituted into L₂, which can then be solved to obtain

Next, z and y can be substituted into L₁, which can be solved to obtain

The system is solved.

Some systems cannot be reduced to triangular form,

yet still have at least one valid solution: for example, if y had not occurred in L₂ and L₃ after the first step above, the algorithm would have been unable to reduce the system to triangular form. However, it would still have reduced the system to echelon form. In this case, the system does not have a unique solution, as it contains at least one free variable. The solution set can then be expressed parametrically (that is, in terms of the free variables, so that if values for the free variables are chosen, a solution will be generated).

In practice, one does not usually deal with the systems in terms of equations but instead makes use of the augmented matrix (which is also suitable for computer manipulations). For example:

therefore, the Gaussian Elimination algorithm applied to the augmented matrix begins with:

which, at the end of the first part(Gaussian elimination, zeros only under the leading 1) of the algorithm, looks like this

That is, it is in row echelon form.

At the end of the algorithm, if the Gauss–Jordan elimination(zeros under and above the leading 1) is applied

That is, it is in reduced row echelon form, or row canonical form.