Gauss-Jordan Elimination

Performing row operations on a matrix is the method we use for solving a system of equations. In order to solve the system of equations, we want to convert the matrix to reduced row echelon form ("rref"), in which there are ones down the main diagonal from the upper left corner to the lower right corner, and zeros in every position below the main diagonal. Here are some examples of matrices in rref:

${\begin{bmatrix}1&3&1\\0&1&-1\\0&0&1\end{bmatrix}}$ , ${\begin{bmatrix}1&3&1\\0&1&-1\\\end{bmatrix}}$ , ${\begin{bmatrix}1&0&0&3\\0&1&0&0\\0&0&1&2\\\end{bmatrix}}$ , ${\begin{bmatrix}1&7\\0&1\\\end{bmatrix}}$ , ${\begin{bmatrix}1&3&0\\0&1&1\\0&0&0\end{bmatrix}}$ , ${\begin{bmatrix}1&0&0\\0&0&0\\0&0&0\end{bmatrix}}$

We use row operations corresponding to equation operations to obtain a new matrix that is row-equivalent in a simpler form. Here are the guidelines to obtaining row-echelon form.

In any nonzero row, the first nonzero number is a 1. It is called a leading 1.
Any all-zero rows are placed at the bottom on the matrix.
Any leading 1 is below and to the right of a previous leading 1.
Any column containing a leading 1 has zeros in all other positions in the column.

To solve a system of equations we can perform the following row operations to convert the coefficient matrix to row-echelon form and do back-substitution to find the solution.

Interchange a row $R_{i}$ with another row $R_{j}$ . (Notation: $R_{i}\longleftrightarrow R_{j}$ )
Multiply a row by a constant. (Notation: $cR_{i}$ )
Add the product of a row multiplied by a constant to another row. (Notation: $R_{i}+cR_{j}$ )

Each of the row operations corresponds to the operations we have already learned to solve systems of equations in three variables. With these operations, there are some key moves that will quickly achieve the goal of writing a matrix in row-echelon form. To obtain a matrix in row-echelon form for finding solutions, we use Gaussian (also called Gauss-Jordan elimination, a method that uses row operations to obtain a 1 as the first entry so that row 1 can be used to convert the remaining rows.

The steps to perform Gaussian elimination on an augmented matrix (and thus convert the matrix to reduced row echelon form) are as follows.

The first equation should have a leading coefficient of 1. Interchange rows or multiply by a constant, if necessary.
Use row operations to obtain zeros down the first column below the first entry of 1.
Use row operations to obtain a 1 in row 2, column 2.
Use row operations to obtain zeros down column 2, below the entry of 1.
Use row operations to obtain a 1 in row 3, column 3.
Continue this process for all rows until there is a 1 in every entry down the main diagonal and there are only zeros below.
If any rows contain all zeros, place them at the bottom.

Example of Gauss-Jordan elimination:

${\begin{bmatrix}1&3&1&9\\1&1&-1&1\\3&11&5&35\end{bmatrix}}\to {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&2&2&8\end{bmatrix}}\to {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{bmatrix}}\to {\begin{bmatrix}1&0&-2&-3\\0&1&1&4\\0&0&0&0\end{bmatrix}}$

First, we subtract 1 of the first row from the second row ( $R_{2}-R_{1}$ ) and 3 of the first row from the third row ( $R_{3}-3R_{1}$ ). Then, we add the new second row to the new third row ( $R_{3}+R_{2}$ ). Lastly, we multiply the new second row by $-{\frac {1}{2}}$ to make the diagonal entries equal to 1 ( $-{\frac {1}{2}}R_{2})$ . Our matrix is now in reduced row echelon form, since all nonzero diagonal entries are equal to 1, the all-zero row is at the bottom of the matrix, and all entries under the diagonal are zero.