M.7 Gauss-Jordan Elimination

M.7 Gauss-Jordan Elimination

Gauss-Jordan Elimination is an algorithm that can be used to solve systems of linear equations and to find the inverse of any invertible matrix. It relies upon three elementary row operations one can use on a matrix:

  1. Swap the positions of two of the rows
  2. Multiply one of the rows by a nonzero scalar.
  3. Add or subtract the scalar multiple of one row to another row.
 

For an example of the first elementary row operation, swap the positions of the 1st and 3rd row.

\[ \begin{pmatrix} 4 & 0 & -1 \\ 2 & -2 & 3 \\ 7 & 5 & 0 \end{pmatrix}\Rightarrow  \begin{pmatrix} 7 & 5 & 0 \\ 2 & -2 & 3 \\ 4 & 0 & -1 \end{pmatrix} \]

For an example of the second elementary row operation, multiply the second row by 3.

\[ \begin{pmatrix} 4 & 0 & -1 \\ 2 & -2 & 3 \\ 7 & 5 & 0 \end{pmatrix} \Rightarrow \begin{pmatrix} 4 & 0 & -1 \\ 6 & -6 & 9 \\ 7 & 5 & 0 \end{pmatrix} \]

For an example of the third elementary row operation, add twice the 1st row to the 2nd row.

\[ \begin{pmatrix} 4 & 0 & -1 \\ 2 & -2 & 3 \\ 7 & 5 & 0 \end{pmatrix}\Rightarrow  \begin{pmatrix} 4 & 0 & -1 \\ 10 & -2 & 1 \\ 7 & 5 & 0 \end{pmatrix} \]


Reduced-row echelon form

The purpose of Gauss-Jordan Elimination is to use the three elementary row operations to convert a matrix into reduced-row echelon form. A matrix is in reduced-row echelon form, also known as row canonical form, if the following conditions are satisfied:

  1. All rows with only zero entries are at the bottom of the matrix
  2. The first nonzero entry in a row, called the leading entry or the pivot, of each nonzero row is to the right of the leading entry of the row above it.
  3. The leading entry, also known as the pivot, in any nonzero row is 1.
  4. All other entries in the column containing a leading 1 are zeroes.

For example

\[A = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 3 \\ 0 & 0 & 0 \end{pmatrix}, B = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, C = \begin{pmatrix} 0 & 7 & 3 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}, D = \begin{pmatrix} 1 & 7 & 3 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \]

Matrices A and B are in reduced-row echelon form, but matrices C and D are not. C is not in reduced-row echelon form because it violates conditions two and three. D is not in reduced-row echelon form because it violates condition four. In addition, the elementary row operations can be used to reduce matrix D into matrix B.


Steps for Gauss-Jordan Elimination

To perform Gauss-Jordan Elimination:

  1. Swap the rows so that all rows with all zero entries are on the bottom
  2. Swap the rows so that the row with the largest, leftmost nonzero entry is on top.
  3. Multiply the top row by a scalar so that top row's leading entry becomes 1.
  4. Add/subtract multiples of the top row to the other rows so that all other entries in the column containing the top row's leading entry are all zero.
  5. Repeat steps 2-4 for the next leftmost nonzero entry until all the leading entries are 1.
  6. Swap the rows so that the leading entry of each nonzero row is to the right of the leading entry of the row above it.

Selected video examples are shown below:

To obtain the inverse of a n × n matrix A :

  1. Create the partitioned matrix \(( A | I )\) , where I is the identity matrix.
  2. Perform Gauss-Jordan Elimination on the partitioned matrix with the objective of converting the first part of the matrix to reduced-row echelon form.
  3. If done correctly, the resulting partitioned matrix will take the form \(( I | A^{-1} )\)
  4. Double-check your work by making sure that \(AA^{-1} = I\).

Legend
[1]Link
Has Tooltip/Popover
 Toggleable Visibility