compute a row echelon transform of a mod p Matrix
RowEchelonTransform(p, A, frows, lrows, redflag, eterm)
mod p Matrix with n rows and m columns
boolean; indicate whether to compute first rank rows
boolean; indicate whether to compute last n-rank rows
boolean; indicate whether row echelon form is reduced
boolean; indicate whether to terminate early if not full rank
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](..).
n,m,p ≔ 6,9,97:
A ≔ Mod⁡p,95,91,80,85,5,75,12,64,60,34,5,95,48,81,78,30,70,76,10,30,85,37,57,21,58,15,62,81,49,58,34,52,76,2,90,19,54,65,71,60,93,46,74,7,12,31,93,21,73,23,50,10,24,56,integer
Compute an echelon transform to achieve a row echelon form.
U ≔ Mod⁡p,A,integer:
Q,rp,d ≔ RowEchelonTransform⁡p,U,true,true,false,false
r ≔ nops⁡rp:
U ≔ U1..n,1..n:
forifromr+1tondoUi,i ≔ 1end do:
The transform U:
Compute the row echelon form. P is omitted since it is the identity matrix.
R ≔ Multiply⁡p,U,A
Now compute an echelon transform to achieve a reduced row echelon form.
Q,rp,d ≔ RowEchelonTransform⁡p,U,true,true,true,false
The reduced row echelon form:
Download Help Document