The Gauß-Jordan elimination is an algorithm for solving systems of linear equations in an arbitrary field and consists of the following elementary row operations on an augmented matrix. Besides solving a linear system, the method can also be used to find the rank of a matrix, to calculate the determinant of a matrix and to find the inverse of an invertible square matrix.
- Interchange any two rows
- Multiply each element of a row by a nonzero scalar
- Replace a row by the sum of itself and a constant multiple of another row
We will use the following notation for these row operations:
- \(R_i\leftrightarrow R_j\): Interchange row \(i\) and row \(j\)
- \(\alpha R_i\): Replace row \(i\) with \(\alpha\) times row \(i\)
- \(R_i+\alpha R_j\): Replace row \(i\) with the sum of row \(i\) and \(\alpha\) times row \(j\)
The algorithm to solve a system of linear equations can be described by the following steps:
- Arrange the augmented matrix of the system
- Use the row operation in an arbitrary order to transform the
augmented matrix into the reduced row echolon form
(RREF):
- The leftmost entries in each row are 1, which are called leading entry or pivot
- If a column contains a leading entry, all entries below that leading one are zero
- In any two consecutive nonzero rows, the leading entry of the upper row occurs to the left of the leading entry of the lower row
- All rows consisting entirely of zeros appear at the bottom of the matrix
- The system is inconsistent and has no solutions if the loop in the second step generates a row with all but the rightmost element zero. For a consistent system, the solution can be back-substituted from the resulting matrix.
Lets say we have the following system of linear equations:
\[\begin{array}{rl} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n &=b_1\\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n &=b_2\\ ...&\\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n &=b_m\\ \end{array}\]
We can then create the (\(m\times n\)) coefficient matrix and the right-hand side (\(m\times 1\)) column vector:
\[\left(\begin{array}{cccc} a_{11} & a_{12} & \dots &a_{1n}\\ a_{21} & a_{22} & \dots &a_{2n}\\ \vdots & \vdots & \ddots &\vdots\\ a_{m1} & a_{m2} & \dots &a_{mn}\\ \end{array}\right)\,\,\,\,\, \left(\begin{array}{c} b_1\\ b_2\\ \vdots\\ b_m\\ \end{array}\right)\]
And finally the augmented \(m\times (n+1)\) matrix.
\[\left(\begin{array}{cccc|c} a_{11} & a_{12} & \dots &a_{1n}&b_1\\ a_{21} & a_{22} & \dots &a_{2n}&b_2\\ \vdots & \vdots & \ddots &\vdots&\vdots\\ a_{m1} & a_{m2} & \dots &a_{mn}&b_m\\ \end{array}\right)\]
The goal of the Gauss-Jordan elimination is to convert the augmented matrix into reduced row echolon form, like this:
\[\left(\begin{array}{ccccc|c} 1 & & * & & * & *\\ & 1 & \underline{*} & & * & *\\ & & & 1 & \underline{*} & *\\ \end{array}\right)\]
The first element of the nonzero rows always start with one and have zeros for all other elements in the column. The underlined elements mark free variables and all entries below the staircase are zero.
This system is consistent, as there is no leading entry in the rightmost column of the augmented matrix in row echolon form, other than the following inconsistent example:
\[\left(\begin{array}{ccccc|c} 1 & & * & & * & *\\ & 1 & \underline{*} & & * & *\\ & & & & & 1\\ \end{array}\right)\]
[1] G. Cazelais (2010). Gauss-Jordan Elimination Method