# Why use Gauss Jordan Elimination instead of Gaussian Elimination, Differences

Why use Gaussian Elimination instead of Gauss Jordan Elimination and vice versa for solving systems of linear equations? What are the differences, benefits of each, etc.?

I've just been solving linear equation systems, of the form Ax = B, by reducing matrix A to a diagonal matrix where every nonzero value equals 1. I'm not exactly sure if this would be considered Gaussian Elimination or Gauss-Jordan Elimination.

• I was not aware there was a difference. When I studied linear algebra, all operations involving reductions via row operations were referred to as the process of "Gauss elimination" Aug 9, 2015 at 12:13
• @AlfredYerger: Perhaps it's a new thing: Wikipedia notes a difference, too. Feb 22, 2017 at 0:33

Gaussian Elimination helps to put a matrix in row echelon form, while Gauss-Jordan Elimination puts a matrix in reduced row echelon form. For small systems (or by hand), it is usually more convenient to use Gauss-Jordan elimination and explicitly solve for each variable represented in the matrix system. However, Gaussian elimination in itself is occasionally computationally more efficient for computers. Also, Gaussian elimination is all you need to determine the rank of a matrix (an important property of each matrix) while going through the trouble to put a matrix in reduced row echelon form is not worth it to only solve for the matrix's rank.

EDIT: Here are some abbreviations to start off with: REF = "Row Echelon Form". RREF = "Reduced Row Echelon Form."

In your question, you say you reduce a matrix A to a diagonal matrix where every nonzero value equals 1. For this to happen, you must perform row operations to "pivot" along each entry along the diagonal. Such row operations usually involve multiplying/dividing by nonzero scalar multiples of the row, or adding/subtracting nonzero scalar multiples of one row from another row. My interpretation of REF is just doing row operations in such a way to avoid dividing rows by their pivot values (to make the pivot become 1). If you go through each pivot (the numbers along the diagonal) and divide those rows by their leading coefficient, then you will end up in RREF. See these Khan Academy videos for worked examples.

In a system $Ax=B$, $x$ can only be solved for if $A$ is invertible. Invertible matrices have several important properties. The most useful property for your question is that their RREF is the identity matrix (a matrix with only 1's down the diagonal and 0's everywhere else). If you row-reduce a matrix and it does not become an identity matrix in RREF, then that matrix was non-invertible. Non-invertible matrices (also known as singular matrices) are not as helpful when trying to solve a system exactly.

• What are row echelon and reduced row echelon form then? I thought row echelon form was merely defined as the result of Gaussian Elimination and the same for reduced row echelon form with Gauss-Jordan Elmination. Jul 27, 2014 at 22:18
• "x can only be solved for if A is invertible." This is not true as written. If A is rank-deficient, there are an infinite number of solutions for x. Thus it can be solved, just not uniquely. If the problem is overly constrained (size of B is greater than the size of x), then A is not invertible, but a unique solution exists—provided $A^T A$ is invertible: $A^T A x = A^T b \rightarrow x = \left( A^T A \right)^{-1} A^T b$. Feb 22, 2017 at 0:41
• @John: The difference between row echelon and reduced row echelon form is simple. Row echelon matrices doesn't have ones on the diagonal, while reduced row echelon matrices do. To calculate the reduced row echelon form, divide each matrix row by the value of that row's diagonal element: $A^{RRE}_{ij} = A^{RE}_{ij} \; / \; A^{RE}_{ii}$. Feb 22, 2017 at 0:47
• @jvriesem Good catch regarding solving for $x$. But given the OP's question and experience, I didn't feel it was necessary to introduce the concept of rank-deficiency and isolating $x$ in the "normal equation." Feb 23, 2017 at 1:56
• From an applications point of view, besides performance, an important difference is that rref is unique. May 6, 2017 at 19:43

The following example, part of Finding a sequence of elementary matrices, compliments the insight of @Xoque55

The target matrix is $$\left[ \begin{array}{cc|cc} 2 & 4 \\ 1 & 1 \\ \end{array} \right]$$

Use elementary row operations for Gaussian elimination. $\color{blue}{Blue}$ coloring denotes changed entries in the output matrix.

Row echelon form

Form the augmented matrix

$$\left[ \begin{array}{c|c} \mathbf{A} & b \end{array} \right] = \left[ \begin{array}{cc|c} 2 & 4 & b_{1} \\ 1 & 1 & b_{2} \\ \end{array} \right]$$

Normalize row 1: $$\left[ \begin{array}{cc} \frac{1}{2} & 0 \\ 0 & 1 \\ \end{array} \right] % \left[ \begin{array}{cc|c} 2 & 4 & b_{1} \\ 1 & 1 & b_{2} \\ \end{array} \right] = \left[ \begin{array}{cc|c} \color{blue}{1} & \color{blue}{2} & \frac{1}{2}b_{1} \\ 1 & 1 & b_{2}\\ \end{array} \right]$$

Clear column 1 $$\left[ \begin{array}{rc} 1 & 0 \\ -1 & 1 \\ \end{array} \right] % \left[ \begin{array}{cc|c} \color{blue}{1} & \color{blue}{2} & \frac{1}{2}b_{1} \\ 1 & 1 & b_{2}\\ \end{array} \right] = \left[ \begin{array}{cr|c} 1 & 2 & \frac{1}{2}b_{1} \\ \color{blue}{0} & \color{blue}{-1} & b_{2} - \frac{1}{2}b_{1} \\ \end{array} \right]$$

The system can be solved via back substitution.

Reduced row echelon form

The reduction process is $$% \left[ \begin{array}{c|c} \mathbf{A} & \mathbf{I} \end{array} \right] % \qquad \Rightarrow \qquad % \left[ \begin{array}{c|c} \mathbf{E_{A}} & \mathbf{R} \end{array} \right]$$

Form the augmented matrix

$$\left[ \begin{array}{c|c} \mathbf{A} & \mathbf{I} \end{array} \right] = \left[ \begin{array}{cc|cc} 2 & 4 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ \end{array} \right]$$

Normalize row 1: $$\left[ \begin{array}{cc} \frac{1}{2} & 0 \\ 0 & 1 \\ \end{array} \right] % \left[ \begin{array}{cc|cc} 2 & 4 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ \end{array} \right] = \left[ \begin{array}{cc|cc} \color{blue}{1} & \color{blue}{2} & \frac{1}{2} & 0 \\ 1 & 1 & 0 & 1 \\ \end{array} \right]$$

Clear column 1 $$\left[ \begin{array}{rc} 1 & 0 \\ -1 & 1 \\ \end{array} \right] % \left[ \begin{array}{cc|cc} 1 & 2 & \frac{1}{2} & 0 \\ 1 & 1 & 0 & 1 \\ \end{array} \right] = \left[ \begin{array}{cr|rc} 1 & 2 & \frac{1}{2} & 0 \\ \color{blue}{0} & \color{blue}{-1} & -\frac{1}{2} & 1 \\ \end{array} \right]$$

Normalize row 2 $$\left[ \begin{array}{cr} 1 & 0 \\ 0 & -1 \\ \end{array} \right] % \left[ \begin{array}{cc|cr} 1 & 2 & \frac{1}{2} & 0 \\ 0 & 1 & \frac{1}{2} & -1 \\ \end{array} \right] = \left[ \begin{array}{cc|cr} 1 & 2 & \frac{1}{2} & 0 \\ \color{blue}{0} & \color{blue}{1} & \frac{1}{2} & -1 \\ \end{array} \right]$$

Clear column 2 $$\left[ \begin{array}{cr} 1 & -2 \\ 0 & 1 \\ \end{array} \right] % \left[ \begin{array}{cc|cr} 1 & 2 & \frac{1}{2} & 0 \\ 0 & 1 & \frac{1}{2} & -1 \\ \end{array} \right] = \left[ \begin{array}{cc|rr} \color{blue}{1} & \color{blue}{0} & -\frac{1}{2} & 2 \\ 0 & 1 & \frac{1}{2} & -1 \\ \end{array} \right]$$ Result $$\left[ \begin{array}{c|c} \mathbf{E_{A}} & \mathbf{R} \end{array} \right] = \left[ \begin{array}{cc|rr} 1 & 0 & -\frac{1}{2} & 2 \\ 0 & 1 & \frac{1}{2} & -1 \\ \end{array} \right]$$

The solution is $$\mathbf{A} x = b \quad \Rightarrow \quad x = \mathbf{A}^{-1} b \quad \Rightarrow \quad x = \frac{1}{2}\left[ \begin{array}{rr} -1 & 4 \\ 1 & -2 \\ \end{array} \right] % \left[ \begin{array}{c} b_{1} \\ b_{2} \\ \end{array} \right] \quad \Rightarrow \quad x = \left[ \begin{array}{l} -\frac{1}{2} b_{1} + 2b_{2} \\ \phantom{-}\frac{1}{2} b_{1} - b_{2} \\ \end{array} \right]$$

Product of reduction matrices

The product of the sequence of reduction matrices is the inverse: $$% four \left[ \begin{array}{cr} 1 & -2 \\ 0 & 1 \\ \end{array} \right] % third \left[ \begin{array}{cr} 1 & 0 \\ 0 & -1 \\ \end{array} \right] % second \left[ \begin{array}{rc} 1 & 0 \\ -1 & 1 \\ \end{array} \right] % first \left[ \begin{array}{cc} \frac{1}{2} & 0 \\ 0 & 1 \\ \end{array} \right] = \left[ \begin{array}{rr} -\frac{1}{2} & 2 \\ \frac{1}{2} & -1 \\ \end{array} \right] = \mathbf{A}^{-1}$$

Gauss-Jordan elimination means you find the matrix inverse $A^{-1}$.

Gaussian elimination means you only find the solution to $Ax=b$.

When you have the matrix inverse, of course you can also find the solution $x=A^{-1}b$, but this is more work.

• Note: Gauss-Jordan elimination itself does not necessarily find $A^{-1}$, although it's really easy to construct $A^{-1}$ while performing Gauss-Jordan elimination. See this Q&A for context if interested. Feb 22, 2017 at 0:45

To build on the accepted answer, I will add an analysis. So lets say that we wanted to turn 2 rows into row echelon form.

Using RREF:

Divide all terms in first row by the leading coefficient (n operations) then find out what to multiply the first row by so that you can add it to the second row and make the second rows leading coefficient 0, finding this multiplier will take 1 operation. Then you have to divide/multiply every element of the first row by this number, and add this row to the second row, 2n operations. So out total is n+n+n+1 or around 3n

Using REF:

Find out what to multiply the first row by so that you can add it to the second row and make the second rows leading coefficient 0 (1 operation). Multiply all terms in the first row by this number, then add this row with the second row (2n operations). So our total is 1+n+n or around 2n.