The RowEchelonTransform function computes a mod p row echelon transform of the mod p input Matrix A.

Generally, it is required that p be a prime, as inverses are needed, but in some cases it is possible to obtain an echelon transform when p is composite.  For the cases where the echelon transform cannot be obtained for p composite, the function returns an error indicating that p is composite.

Note that for some cases where p is composite the row echelon form of a Matrix exists while the row echelon transform cannot be written in the required form.

A row echelon transform of A is a 4-tuple (U, P, rp, d) with rp the rank profile of A (the unique and strictly increasing list [j1,j2,...jr] of column indices of the row echelon form  which contain the pivots), P a permutation matrix such that all r leading submatrices of (PA)[1..r,rp] are nonsingular, U a nonsingular matrix such that UPA is in row echelon form, and d<>0 the determinant of (PA)[1..r,rp]. Furthermore, the matrix U is structured, with northeast block U[1..r, r+1..-1] equal to the zero matrix, and southeast block U[r+1..-1, r+1..-1] equal to the identity matrix.

Note that the rows of (UPA)[1..r, 1..-1] comprise a basis, in echelon form, for the row space of A, while the rows of (UP)[r+1..-1, 1..-1] comprise a basis for the left nullspace of A.

For efficiency, the RowEchelonTransform function does not return an echelon transform (U,P,rp,d) directly, but rather the expression sequence (Q,rp,d), where Q is an integer Array with i<=Q[i]<=n for 1=1..r.  The input Matrix A is modified inplace and used to store U.  Let A' denote the state of A on completion.  Then U may be obtained from the identity matrix by replacing the first r columns with those of A', and P may be obtained from the identity matrix by swapping row i with row Q[i], for i=1..r in succession.

Let (U, P, rp, d) be as constructed above. If frows=false, the first r rows of U will not be correct.  If lrows=false, the last n-r rows of U will not be correct.  Setting one or both of these flags to false can speed the computation by up to four times.

If redflag=true, the row echelon form is reduced, that is (UPA)[1..r, rp] will be the identity matrix. If redflag=false, the row echelon form will not be reduced, that is (UPA)[1..r, rp] will be upper triangular and U is unit lower triangular.  If frows=false then redflag has no effect.

If eterm=true, then early termination is triggered if a column of the input matrix is discovered that is linearly dependent on the previous columns.  In case of early termination, the third return value d of the return sequence (Q, rp, d) will be 0 and all components of the echelon transform will be incorrect.

This command is part of the LinearAlgebra[Modular] package, so it can be used in the form RowEchelonTransform(..) only after executing the command with(LinearAlgebra[Modular]).  However, it can always be used in the form LinearAlgebra[Modular][RowEchelonTransform](..).