ROW_ECHELON_INTEGER
Exact Row Echelon for Integer Matrices

ROW_ECHELON_INTEGER is a FORTRAN90 library 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.

Licensing:

The computer code and data files made available on this web page are distributed under the GNU LGPL license.

Languages:

ROW_ECHELON_INTEGER is available in a C version and a FORTRAN90 version and a MATLAB version and a Python version.

Related Programs:

I4LIB, a FORTRAN90 library which contains many utility routines, using "I4" or "single precision integer" arithmetic.

R8LIB, a FORTRAN90 library which contains many utility routines, using "R8" or "double precision real" arithmetic.

Reference:

1. Howard Anton, Chris Rorres,
   Elementary Linear Algebra: Applications Version,
   Wiley, 2013,
   ISBN: 9781118879160.
2. Ward Cheney, David Kincaid,
   Linear Algebra: Theory and Applications,
   Jones & Bartlett, 2010,
   ISBN: 9781449613525.
3. Charles Cullen,
   Linear Algebra with Applications,
   Second Edition,
   Pearson, 1997,
   ISBN: 978-0673993861.
4. Gilbert Strang,
   Linear Algebra and its Applications,
   Second edition,
   Academic Press, 1980,
   ISBN: 012673660X,
   LC: QA184.88.

Source Code:

• row_echelon_integer.f90, the source code.

Examples and Tests:

• row_echelon_integer_test.f90, a sample calling program.
• row_echelon_integer_test.txt, the output file.

List of Routines:

• I4_GCD finds the greatest common divisor of two I4's.
• I4MAT_PRINT prints an I4MAT.
• I4MAT_PRINT_SOME prints some of an I4MAT.
• I4MAT_REF computes the integer row echelon form (IREF) of an I4MAT.
• I4MAT_ROW_SWAP swaps rows in an I4MAT.
• I4MAT_RREF computes the reduced row echelon form of an I4MAT.
• I4MAT_RREF_SOLVE_SYSTEM sets up an augmented IRREF linear system.
• I4MAT_U_SOLVE solves an upper triangular linear system with an I4MAT matrix.
• I4ROWS_TO_I4MAT converts a row-major vector to an I4MAT.
• I4VEC_BINARY_NEXT generates the next binary vector.
• I4VEC_IDENTITY_ROW returns the I-th row of the identity matrix.
• I4VEC_IS_BINARY is true if an I4VEC only contains 0 and 1 entries.
• I4VEC_PRINT prints an I4VEC.
• I4VEC_RED divides out common factors in an I4VEC.
• I4VEC_TRANSPOSE_PRINT prints an I4VEC "transposed".
• KSUB_NEXT4 generates the subsets of size K from a set of size N.
• R8VEC_IS_INTEGER is TRUE if the entries of an R8VEC are integers.
• R8VEC_PRINT prints an R8VEC.
• R8VEC_TRANSPOSE_PRINT prints an R8VEC "transposed".
• TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the FORTRAN90 source codes.