# 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.

- 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