Project Nayuki


Gauss-Jordan elimination over any field (Java)

While it’s typical to solve a system of linear equations in real numbers, it’s also possible to solve a linear system over any mathematical field. Here is some Java code that defines various fields and provides a version of Gauss-Jordan elimination that works on any field. The basic Gauss-Jordan elimination algorithm can be adapted to solve systems of linear equations, invert matrices, calculate determinants, calculate ranks, and more.

Source code

Core classes:

Runnable classes:

Included fields:

Ideas for more fields you can implement:

Examples

Rational numbers

Suppose we want to solve this system of linear equations in rational numbers:

\(\begin{cases} 2x + 5y + 3z &=& 7 \\ x + z &=& 1 \\ -4x + 2y - 9z &=& 6 \end{cases} \)

First we convert the system into an augmented matrix:

\(\begin{bmatrix} 2 & 5 & 3 & 7 \\ 1 & 0 & 1 & 1 \\ -4 & 2 & -9 & 6 \end{bmatrix}\)

Then we perform Gauss-Jordan elimination on the matrix:

\(\begin{bmatrix} 1 & 0 & 0 & 67/27 \\ 0 & 1 & 0 & 35/27 \\ 0 & 0 & 1 & -40/27 \end{bmatrix}\)

And as long as the left side is the identity matrix, we can read the answer off the rightmost column:

\(\begin{cases} x &=& 67/27 \\ y &=& 35/27 \\ z &=& -40/27 \end{cases} \)

Here is the code to perform this example:

// Nice-looking matrix
int[][] input = {
    {2, 5, 3, 7},
    {1, 0, 1, 1},
    {-4, 2, -9, 6},
};

// The actual matrix object
Matrix<Fraction> mat = new Matrix<Fraction>(
        input.length, input[0].length, RationalField.FIELD);
for (int i = 0; i < mat.rowCount(); i++) {
    for (int j = 0; j < mat.columnCount(); j++)
        mat.set(i, j, new Fraction(input[i][j], 1));
}

// Gauss-Jordan elimination
mat.reducedRowEchelonForm();
Integers modulo a prime

Suppose we want to solve this system of linear equations modulo 7:

\(\begin{cases} 3x + 1y + 4z &\equiv& 1 \mod 7 \\ 5x + 2y + 6z &\equiv& 5 \mod 7 \\ 0x + 5y + 2z &\equiv& 1 \mod 7 \end{cases} \)

First we convert the system into an augmented matrix:

\(\begin{bmatrix} 3 & 1 & 4 & 1 \\ 5 & 2 & 6 & 5 \\ 0 & 5 & 2 & 1 \end{bmatrix}\)

Then we perform Gauss-Jordan elimination on the matrix:

\(\begin{bmatrix} 1 & 0 & 0 & 4 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & 0 \end{bmatrix}\)

And as long as the left side is the identity matrix, we can read the answer off the rightmost column:

\(\begin{cases} x &=& 4 \\ y &=& 3 \\ z &=& 0 \end{cases} \)

Here is the code to perform this example:

// Nice-looking matrix
int[][] input = {
    {3, 1, 4, 1},
    {5, 2, 6, 5},
    {0, 5, 2, 1},
};

// The actual matrix object
Matrix<Integer> mat = new Matrix<Integer>(
        input.length, input[0].length, new PrimeField(7));
for (int i = 0; i < mat.rowCount(); i++) {
    for (int j = 0; j < mat.columnCount(); j++)
        mat.set(i, j, input[i][j]);
}

// Gauss-Jordan elimination
mat.reducedRowEchelonForm();