RowEchelonTransform - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim


LinearAlgebra[Modular]

  

RowEchelonTransform

  

compute a row echelon transform of a mod p Matrix

 

Calling Sequence

Parameters

Description

Examples

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)

(5)

(6)

Now compute an echelon transform to achieve a reduced row echelon form.

(7)

The transform U:

(8)

The reduced row echelon form:

(9)

(10)

(11)

See Also

LinearAlgebra

LinearAlgebra/Modular/Adjoint

LinearAlgebra[Modular]

LinearAlgebra[Modular][Basis]

LinearAlgebra[Modular][Determinant]

LinearAlgebra[Modular][Inverse]

LinearAlgebra[Modular][Rank]

LinearAlgebra[Modular][RowReduce]

 


Download Help Document