Gauss-Jordan Elimination

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.

We will use the following notation for these row operations:

The algorithm to solve a system of linear equations can be described by the following steps:

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