Gauss-Jordan elimination over any field
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 Java and Python 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 
Java version
Core classes:
Field.java
: Defines the constants and operations that every field must support.Matrix.java
: Represents a matrix and implements a collection of operations:Basic information: Dimensions, get/set cell, clone, transpose
Row operations: Swap rows, multiply row, add two rows, multiply two matrices
Advanced operations: Gauss-Jordan elimination, determinant, inverse
Runnable classes:
DemoMain.java
: A short demonstration program, which implements the “Rational numbers” example below.MatrixTest.java
: A JUnit test suite forMatrix
,.reducedRowEchelonForm() Matrix
, and.determinantAndRef() Matrix
– mostly using.invert() PrimeField(11)
.
Included fields:
PrimeField.java
: Integers modulo a prime \(p\), also known as \(\mathbb{Z}_p\)BinaryField.java
: Polynomial coefficients over \(\mathbb{Z}_2\) modulo an irreducible polynomial, also known as \(\text{GF}(2^n)\)RationalField.java
,Fraction.java
: Rational numbers (fractions), also known as \(\mathbb{Q}\)QuadraticSurdField.java
,QuadraticSurd.java
: Irrational fractions of the form \(\frac{a + b \sqrt{d}}{c}\), where \(a\), \(b\), \(c\), \(d\) are all integers; the special case of Gaussian rationals occurs when \(d = -1\)
Python version
fieldmath.py: The library, including the classes
Field
,RationalField
,PrimeField
,BinaryField
,QuadraticSurdField
,QuadraticSurd
,Matrix
.demo-main.py: A short demonstration program, which implements the “Rational numbers” example below.
matrix-test.py: A runnable test suite for
fieldmath.Matrix.reduced_row_echelon_form()
,fieldmath.Matrix.determinant_and_ref()
, andfieldmath.Matrix.invert()
– mostly usingfieldmath.PrimeField(11)
.
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 &≡& 1 \mod 7 \\ 5x + 2y + 6z &≡& 5 \mod 7 \\ 0x + 5y + 2z &≡& 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 \mod 7 \\ y &≡& 3 \mod 7 \\ z &≡& 0 \mod 7 \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();