row_echelon_integer, a C++ code which carries out the exact computation of the integer row echelon form (IREF) and integer reduced row echelon form (IRREF) of an integer matrix.
When carried out using exact arithmetic, the REF can reveal the rank of a matrix. It exhibits a set of linearly independent rows of the matrix. It can be used to solve underdetermined systems by revealing which variables can be freely assigned.
The RREF has all the properties of the REF, but moreover exhibits linearly independent columns of the matrix. The RREF of a matrix is unique. It can be used to solve a problem in combinatorics, involving the tiling of a region by a set of polyominoes.
REF and RREF algorithms rely on real arithmetic, and are susceptible to spurious results, because during the elimination process, an entry that should be zero, may instead be set to a very small, but nonzero value, which may then invalidate the entire procedure. This danger exists even if the matrix being analyzed consists entirely of integer values.
By working only with integer matrices, and using only integer arithmetic, such errors are avoided. The corresponding decompositions are termed the IREF and IRREF, respectively. Because of the restriction to integer values, the IREF and IRREF cannot be forced to have a leading 1 in each nonzero row, since we cannot divide rows by the leading entry. Also, it is likely that the procedures will produce values of increasing magnitude, especially for large, dense matrices. Hence, at some point, the exact calculation may fail because of integer overflow.
The computer code and data files made available on this web page are distributed under the MIT license
row_echelon_integer is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version and a Python version.
I4LIB, a C++ code which contains many utility routines, using "I4" or "single precision integer" arithmetic.
R8LIB, a C++ code which contains many utility routines, using "R8" or "double precision real" arithmetic.