ROW_ECHELON_INTEGER
Exact Row Echelon for Integer Matrices

ROW_ECHELON_INTEGER is a Python 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 Python library which contains many utility routines, using "I4" or "single precision integer" arithmetic.

R8LIB, a Python 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:

• i4_gcd.py, returns the greatest common divisor of two I4's;
• i4mat_is_integer.py, is TRUE if all entries of an I4MAT are actually integers;
• i4mat_print.py, prints an I4MAT;
• i4mat_print_some.py, prints some of an I4MAT;
• i4mat_ref.py, returns the integer row echelon form (IREF) of an I4MAT.
• i4mat_row_swap.py, swaps two rows of an I4MAT.
• i4mat_rref.py, returns the integer reduced row echelon form (IRREF) of an I4MAT.
• i4mat_rref_solve_binary.py, seeks binary solutions (if any) of an integer row reduced echelon form (IRREF) linear system.
• i4mat_rref_solve_binary_nz.py, seeks binary solutions (if any) of an integer row reduced echelon form (IRREF) linear system, but only consider solutions with exactly NZ nonzeros.
• i4mat_rref_system.py, considers an underdetermined integer linear system A*x=b, and uses the integer row reduced echelon form (IRREF) to find the solvable augmented linear system, with degrees of freedom indicated.
• i4mat_u_solve.py, solves an upper triangular linear system involving only integer values.
• i4vec_binary_next.py, returns the next binary I4VEC (only 0 or 1 entries).
• i4vec_identity_row.py, returns a row of the identity matrix as an I4VEC.
• i4vec_is_binary.py, is true if an I4VEC has only 0 and 1 entries;
• i4vec_print.py, prints an I4VEC;
• i4vec_red.py, divides out common factors in an I4VEC;
• i4vec_transpose_print.py, prints an I4VEC "transposed";
• ksub_next4.py, selects the next subset of size K from a set of size N.
• r8vec_is_integer.py, is true if all entries of an R8VEC are integers;
• r8vec_print.py, prints an R8VEC;
• r8vec_transpose_print.py, prints an R8VEC "transposed".
• timestamp.py, prints the current YMDHMS date as a timestamp;

Examples and Tests:

• row_echelon_integer_test.py, calls all the tests;
• row_echelon_integer_test.sh, runs all the tests;
• row_echelon_integer_test.txt, the output file;

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