|
Calling Sequence
|
|
RowEchelonTransform(p, A, frows, lrows, redflag, eterm)
|
|
|
Parameters
|
|
|
p
|
-
|
modulus
|
|
A
|
-
|
mod p Matrix with rows and columns
|
|
frows
|
-
|
boolean; indicate whether to compute first rank rows
|
|
lrows
|
-
|
boolean; indicate whether to compute last -rank rows
|
|
redflag
|
-
|
boolean; indicate whether row echelon form is reduced
|
|
eterm
|
-
|
boolean; indicate whether to terminate early if not full rank
|
|
|
|
|
|
Description
|
|
|
•
|
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 Array of k integers, where k = min(r, n-1). All entries Q[i] of Q satisfy i <= Q[i] <= n.
|
|
–
|
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'.
|
|
–
|
P may be obtained from the identity matrix by swapping row i with row Q[i], for i = 1..k 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](..).
|
|
|
|
Examples
|
|
|
>
|
|
|
>
|
|
|
| (1) |
Compute an echelon transform to achieve a row echelon form.
|
>
|
|
|
>
|
|
|
| (2) |
|
>
|
|
|
>
|
|
The transform U:
|
| (3) |
Compute the row echelon form. P is omitted since it is the identity matrix.
|
>
|
|
|
| (4) |
|
>
|
|
Now compute an echelon transform to achieve a reduced row echelon form.
|
>
|
|
|
>
|
|
|
| (7) |
|
>
|
|
|
>
|
|
The transform U:
|
| (8) |
The reduced row echelon form:
|
>
|
|
|
| (9) |
|
>
|
|
|
|
|
