# ROW_ECHELON_INTEGER Exact Row Echelon for Integer Matrices

ROW_ECHELON_INTEGER is a C++ 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.

### Languages:

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.

### Related Programs:

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

R8LIB, a C++ 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,
ISBN: 012673660X,
LC: QA184.88.

### List of Routines:

• I4_GCD finds the greatest common divisor of two I4's.
• I4_MAX returns the maximum of two I4's.
• I4_MIN returns the smaller 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_REDUCE divides out common factors in row I of an I4MAT.
• I4MAT_ROW_SWAP swaps rows in an I4MAT.
• I4MAT_RREF: the integer row reduced echelon form (IRREF) of an I4MAT.
• I4MAT_U_SOLVE solves an upper triangular linear system with I4MAT matrix.
• I4VEC_BINARY_NEXT generates the next binary vector.
• I4VEC_IS_BINARY is true if the entries in an I4VEC are all 0 or 1.
• I4VEC_IS_ONE is true if the entries in an I4VEC are all 1.
• 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 an R8VEC is integral.
• R8VEC_PRINT prints an R8VEC.
• R8VEC_TRANSPOSE_PRINT prints an R8VEC "transposed".
• S_LEN_TRIM returns the length of a string to the last nonblank.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the C++ source codes.

Last revised on 17 September 2018.