LinearAlgebra[Modular] - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Linear Algebra : LinearAlgebra Package : Modular Subpackage : LinearAlgebra/Modular/RowEchelonTransform

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 n rows and m columns

frows

-

boolean; indicate whether to compute first rank rows

lrows

-

boolean; indicate whether to compute last n-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 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](..).

Examples

withLinearAlgebra&lsqb;Modular&rsqb;&colon;

n&comma;m&comma;p6&comma;9&comma;97&colon;

AModp&comma;95&comma;91&comma;80&comma;85&comma;5&comma;75&comma;12&comma;64&comma;60&comma;34&comma;5&comma;95&comma;48&comma;81&comma;78&comma;30&comma;70&comma;76&comma;10&comma;30&comma;85&comma;37&comma;57&comma;21&comma;58&comma;15&comma;62&comma;81&comma;49&comma;58&comma;34&comma;52&comma;76&comma;2&comma;90&comma;19&comma;54&comma;65&comma;71&comma;60&comma;93&comma;46&comma;74&comma;7&comma;12&comma;31&comma;93&comma;21&comma;73&comma;23&comma;50&comma;10&comma;24&comma;56&comma;integer&lsqb;&rsqb;

A:=95918085575126460345954881783070761030853757215815628149583452762901954657160934674712319321732350102456

(1)

Compute an echelon transform to achieve a row echelon form.

UModp&comma;A&comma;integer&lsqb;&rsqb;&colon;

Q&comma;rp&comma;dRowEchelonTransformp&comma;U&comma;true&comma;true&comma;false&comma;false

Q&comma;rp&comma;d:=123&comma;1&comma;4&comma;5&comma;3

(2)

rnopsrp&colon;

UU1..n&comma;1..n&colon;

Fillp&comma;0&comma;U&comma;1..1&comma;r&plus;1..n&colon;

forifromr&plus;1tondoUi&comma;i1end do&colon;

The transform U:

U

100000171000074441000734847100362572010925281001

(3)

Compute the row echelon form.  P is omitted since it is the identity matrix.

RMultiplyp&comma;U&comma;A

R:=9591808557512646000038699240912900001479357186000000000000000000000000000

(4)

R1..r&comma;rp

95855038690014

(5)

d&equals;Determinantp&comma;R1..r&comma;rp

3&equals;3

(6)

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

UModp&comma;A&comma;integer&lsqb;&rsqb;&colon;

Q&comma;rp&comma;dRowEchelonTransformp&comma;U&comma;true&comma;true&comma;true&comma;false

Q&comma;rp&comma;d:=123&comma;1&comma;4&comma;5&comma;3

(7)

UU1..n&comma;1..n&colon;

Fillp&comma;0&comma;U&comma;1..1&comma;r&plus;1..n&colon;

forifromr&plus;1tondoUi&comma;i1end do&colon;

The transform U:

U

10318100012104600033177000734847100362572010925281001

(8)

The reduced row echelon form:

RMultiplyp&comma;U&comma;A

R:=135700192548240001027824640000168511220000000000000000000000000000

(9)

R1..r&comma;rp

100010001

(10)

d&equals;Determinantp&comma;A1..r&comma;rp

3&equals;3

(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

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam