Gaussian elimination
In mathematics, Gaussian elimination (also called row reduction) is a method used to solve systems of linear equations. It is named after Carl Friedrich Gauss, a famous German mathematician who wrote about this method, but did not invent it.
To perform Gaussian elimination, the coefficients of the terms in the system of linear equations are used to create a type of matrix called an augmented matrix. Then, elementary row operations are used to simplify the matrix. The three types of row operations used are:
- Type 1: Switching one row with another row.
- Type 2: Multiplying a row by a non-zero number.
- Type 3: Adding or subtracting a row from another row.
The goal of Gaussian elimination is to get the matrix in row-echelon form. If a matrix is in row-echelon form, that means that reading from left to right, each row will start with at least one more zero term than the row above it. Some definitions of Gaussian elimination say that the matrix result has to be in reduced row-echelon form. That means that the matrix is in row-echelon form and the only non-zero term in each row is 1. Gaussian elimination that creates a reduced row-echelon matrix result is sometimes called Gauss-Jordan elimination.
Example
Suppose the goal is to find the answers to this system of linear equations.
- [math]\displaystyle{ \begin{alignat}{7} 2x &&\; + \;&& y &&\; - \;&& z &&\; = \;&& 8 & \qquad (R_1) \\ -3x &&\; - \;&& y &&\; + \;&& 2z &&\; = \;&& -11 & \qquad (R_2) \\ -2x &&\; + \;&& y &&\; +\;&& 2z &&\; = \;&& -3 & \qquad (R_3) \end{alignat} }[/math]
First, the system needs to be turned into an augmented matrix. In an augmented matrix, each linear equation becomes a row. On one side of the augmented matrix, the coefficients of each term in the linear equation become numbers in the matrix. On the other side of the augmented matrix are the constant terms each linear equation is equal to. For this system, the augmented matrix is:
- [math]\displaystyle{ \left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{array} \right] }[/math]
Then, row operations can be done on the augmented matrix to simplify it. The table below shows the row reduction process on the system of equations and on the augmented matrix.
| System of equations | Row operations | Augmented matrix |
|---|---|---|
| [math]\displaystyle{ \begin{alignat}{7} 2x &&\; + \;&& y &&\; - \;&& z &&\; = \;&& 8 & \\ -3x &&\; - \;&& y &&\; + \;&& 2z &&\; = \;&& -11 & \\ -2x &&\; + \;&& y &&\; +\;&& 2z &&\; = \;&& -3 & \end{alignat} }[/math] | [math]\displaystyle{ \left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{array} \right] }[/math] | |
| [math]\displaystyle{ \begin{alignat}{7} 2x &&\; + && y &&\; - &&\; z &&\; = \;&& 8 & \\ && && \frac{1}{2}y &&\; + &&\; \frac{1}{2}z &&\; = \;&& 1 & \\ && && 2y &&\; + &&\; z &&\; = \;&& 5 & \end{alignat} }[/math] | [math]\displaystyle{ R_2 + \frac{3}{2}R_1 \rightarrow R_2 }[/math] [math]\displaystyle{ R_3 + R_1 \rightarrow R_3 }[/math] |
[math]\displaystyle{ \left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 1/2 & 1/2 & 1 \\ 0 & 2 & 1 & 5 \end{array} \right] }[/math] |
| [math]\displaystyle{ \begin{alignat}{7} 2x &&\; + && y \;&& - &&\; z \;&& = \;&& 8 & \\ && && \frac{1}{2}y \;&& + &&\; \frac{1}{2}z \;&& = \;&& 1 & \\ && && && &&\; -z \;&&\; = \;&& 1 & \end{alignat} }[/math] | [math]\displaystyle{ R_3 + -4R_2 \rightarrow R_3 }[/math] | [math]\displaystyle{ \left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 1/2 & 1/2 & 1 \\ 0 & 0 & -1 & 1 \end{array} \right] }[/math] |
The matrix is now in row-echelon form. This is also called triangular form.
| System of equations | Row operations | Augmented matrix |
|---|---|---|
| [math]\displaystyle{ \begin{alignat}{7} 2x &&\; + && y \;&& &&\; \;&& = \;&& 7 & \\ && && \frac{1}{2}y \;&& &&\; \;&& = \;&& 3/2 & \\ && && && &&\; -z \;&&\; = \;&& 1 & \end{alignat} }[/math] | [math]\displaystyle{ R_2+\frac{1}{2}R_3 \rightarrow R_2 }[/math] [math]\displaystyle{ R_1 - R_3 \rightarrow R_1 }[/math] |
[math]\displaystyle{ \left[ \begin{array}{ccc|c} 2 & 1 & 0 & 7 \\ 0 & 1/2 & 0 & 3/2 \\ 0 & 0 & -1 & 1 \end{array} \right] }[/math] |
| [math]\displaystyle{ \begin{alignat}{7} 2x &&\; + && y \;&& &&\; \;&& = \;&& 7 & \\ && && y \;&& &&\; \;&& = \;&& 3 & \\ && && && &&\; z \;&&\; = \;&& -1 & \end{alignat} }[/math] | [math]\displaystyle{ 2R_2 \rightarrow R_2 }[/math] [math]\displaystyle{ -R_3 \rightarrow R_3 }[/math] |
[math]\displaystyle{ \left[ \begin{array}{ccc|c} 2 & 1 & 0 & 7 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & -1 \end{array} \right] }[/math] |
| [math]\displaystyle{ \begin{alignat}{7} x &&\; && \;&& &&\; \;&& = \;&& 2 & \\ && && y \;&& &&\; \;&& = \;&& 3 & \\ && && && &&\; z \;&&\; = \;&& -1 & \end{alignat} }[/math] | [math]\displaystyle{ R_1 - R_2 \rightarrow R_1 }[/math] [math]\displaystyle{ \frac{1}{2}R_1 \rightarrow R_1 }[/math] |
[math]\displaystyle{ \left[ \begin{array}{ccc|c} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & -1 \end{array} \right] }[/math] |
The matrix is now in reduced row-echelon form. Reading this matrix tells us that the solutions for this system of equations occur when x = 2, y = 3, and z = -1.
Gaussian Elimination Media
Animation of Gaussian elimination. Red row eliminates the following rows, green rows change their order.
