RowEchelonTransform - Maple Help

LinearAlgebra[Modular]

 RowEchelonTransform
 compute a row echelon transform of a mod p Matrix

 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 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

 > $\mathrm{with}\left(\mathrm{LinearAlgebra}\left[\mathrm{Modular}\right]\right):$
 > $n,m,p≔6,9,97:$
 > $A≔\mathrm{Mod}\left(p,\left[\left[95,91,80,85,5,75,12,64,60\right],\left[34,5,95,48,81,78,30,70,76\right],\left[10,30,85,37,57,21,58,15,62\right],\left[81,49,58,34,52,76,2,90,19\right],\left[54,65,71,60,93,46,74,7,12\right],\left[31,93,21,73,23,50,10,24,56\right]\right],\mathrm{integer}\left[\right]\right)$
 ${A}{≔}\left[\begin{array}{ccccccccc}{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}\end{array}\right]$ (1)

Compute an echelon transform to achieve a row echelon form.

 > $U≔\mathrm{Mod}\left(p,A,\mathrm{integer}\left[\right]\right):$
 > $Q,\mathrm{rp},d≔\mathrm{RowEchelonTransform}\left(p,U,\mathrm{true},\mathrm{true},\mathrm{false},\mathrm{false}\right)$
 ${Q}{,}{\mathrm{rp}}{,}{d}{≔}\left[\begin{array}{ccc}{1}& {2}& {3}\end{array}\right]{,}\left[{1}{,}{4}{,}{5}\right]{,}{3}$ (2)
 > $r≔\mathrm{nops}\left(\mathrm{rp}\right):$
 > $U≔U\left[1..n,1..n\right]:$
 > $\mathrm{Fill}\left(p,0,U,1..-1,r+1..n\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}i\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{from}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}r+1\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{to}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}n\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}U\left[i,i\right]≔1\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$

The transform U:

 > $U$
 $\left[\begin{array}{cccccc}{1}& {0}& {0}& {0}& {0}& {0}\\ {17}& {1}& {0}& {0}& {0}& {0}\\ {74}& {44}& {1}& {0}& {0}& {0}\\ {73}& {48}& {47}& {1}& {0}& {0}\\ {36}& {25}& {72}& {0}& {1}& {0}\\ {92}& {52}& {81}& {0}& {0}& {1}\end{array}\right]$ (3)

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

 > $R≔\mathrm{Multiply}\left(p,U,A\right)$
 ${R}{≔}\left[\begin{array}{ccccccccc}{95}& {91}& {80}& {85}& {5}& {75}& {12}& {64}& {60}\\ {0}& {0}& {0}& {38}& {69}& {92}& {40}& {91}& {29}\\ {0}& {0}& {0}& {0}& {14}& {79}& {35}& {71}& {86}\\ {0}& {0}& {0}& {0}& {0}& {0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}& {0}& {0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}& {0}& {0}& {0}& {0}& {0}\end{array}\right]$ (4)
 > $R\left[1..r,\mathrm{rp}\right]$
 $\left[\begin{array}{ccc}{95}& {85}& {5}\\ {0}& {38}& {69}\\ {0}& {0}& {14}\end{array}\right]$ (5)
 > $d=\mathrm{Determinant}\left(p,R\left[1..r,\mathrm{rp}\right]\right)$
 ${3}{=}{3}$ (6)

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

 > $U≔\mathrm{Mod}\left(p,A,\mathrm{integer}\left[\right]\right):$
 > $Q,\mathrm{rp},d≔\mathrm{RowEchelonTransform}\left(p,U,\mathrm{true},\mathrm{true},\mathrm{true},\mathrm{false}\right)$
 ${Q}{,}{\mathrm{rp}}{,}{d}{≔}\left[\begin{array}{ccc}{1}& {2}& {3}\end{array}\right]{,}\left[{1}{,}{4}{,}{5}\right]{,}{3}$ (7)
 > $U≔U\left[1..n,1..n\right]:$
 > $\mathrm{Fill}\left(p,0,U,1..-1,r+1..n\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}i\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{from}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}r+1\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{to}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}n\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}U\left[i,i\right]≔1\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$

The transform U:

 > $U$
 $\left[\begin{array}{cccccc}{10}& {31}& {81}& {0}& {0}& {0}\\ {12}& {10}& {46}& {0}& {0}& {0}\\ {33}& {17}& {7}& {0}& {0}& {0}\\ {73}& {48}& {47}& {1}& {0}& {0}\\ {36}& {25}& {72}& {0}& {1}& {0}\\ {92}& {52}& {81}& {0}& {0}& {1}\end{array}\right]$ (8)

The reduced row echelon form:

 > $R≔\mathrm{Multiply}\left(p,U,A\right)$
 ${R}{≔}\left[\begin{array}{ccccccccc}{1}& {3}& {57}& {0}& {0}& {19}& {25}& {48}& {24}\\ {0}& {0}& {0}& {1}& {0}& {27}& {8}& {24}& {64}\\ {0}& {0}& {0}& {0}& {1}& {68}& {51}& {12}& {20}\\ {0}& {0}& {0}& {0}& {0}& {0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}& {0}& {0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}& {0}& {0}& {0}& {0}& {0}\end{array}\right]$ (9)
 > $R\left[1..r,\mathrm{rp}\right]$
 $\left[\begin{array}{ccc}{1}& {0}& {0}\\ {0}& {1}& {0}\\ {0}& {0}& {1}\end{array}\right]$ (10)
 > $d=\mathrm{Determinant}\left(p,A\left[1..r,\mathrm{rp}\right]\right)$
 ${3}{=}{3}$ (11)