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](..).

$\mathrm{with}\left(\mathrm{LinearAlgebra}\left[\mathrm{Modular}\right]\right)\&colon;$

$n,m,p≔6,9,97\&colon;$

$A≔\mathrm{Mod}\left(p\&comma;\left[\left[95\&comma;91\&comma;80\&comma;85\&comma;5\&comma;75\&comma;12\&comma;64\&comma;60\right]\&comma;\left[34\&comma;5\&comma;95\&comma;48\&comma;81\&comma;78\&comma;30\&comma;70\&comma;76\right]\&comma;\left[10\&comma;30\&comma;85\&comma;37\&comma;57\&comma;21\&comma;58\&comma;15\&comma;62\right]\&comma;\left[81\&comma;49\&comma;58\&comma;34\&comma;52\&comma;76\&comma;2\&comma;90\&comma;19\right]\&comma;\left[54\&comma;65\&comma;71\&comma;60\&comma;93\&comma;46\&comma;74\&comma;7\&comma;12\right]\&comma;\left[31\&comma;93\&comma;21\&comma;73\&comma;23\&comma;50\&comma;10\&comma;24\&comma;56\right]\right]\&comma;\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]$

$U≔\mathrm{Mod}\left(p\&comma;A\&comma;\mathrm{integer}\left[\right]\right)\&colon;$

$Q,\mathrm{rp},d≔\mathrm{RowEchelonTransform}\left(p\&comma;U\&comma;\mathrm{true}\&comma;\mathrm{true}\&comma;\mathrm{false}\&comma;\mathrm{false}\right)$

$Q,\mathrm{rp},d≔\left[\begin{array}{ccc}1& 2& 3\end{array}\right],\left[1\&comma;4\&comma;5\right],3$

$r≔\mathrm{nops}\left(\mathrm{rp}\right)\&colon;$

$U≔U\left[1..n,1..n\right]\&colon;$

$\mathrm{Fill}\left(p\&comma;0\&comma;U\&comma;1..-1\&comma;r+1..n\right)\&colon;$

$$\begin{gathered} \mathbf{for}i\mathbf{from}r+1\mathbf{to}n\mathbf{do} \\ U\left[i,i\right]≔1 \\ \mathbf{end}\mathbf{do}\&colon; \end{gathered}$$

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

$R≔\mathrm{Multiply}\left(p\&comma;U\&comma;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]$

$R\left[1..r,\mathrm{rp}\right]$

$\left[\begin{array}{ccc}95& 85& 5\\ 0& 38& 69\\ 0& 0& 14\end{array}\right]$

$d=\mathrm{Determinant}\left(p\&comma;R\left[1..r,\mathrm{rp}\right]\right)$

$3=3$

$U≔\mathrm{Mod}\left(p\&comma;A\&comma;\mathrm{integer}\left[\right]\right)\&colon;$

$Q,\mathrm{rp},d≔\mathrm{RowEchelonTransform}\left(p\&comma;U\&comma;\mathrm{true}\&comma;\mathrm{true}\&comma;\mathrm{true}\&comma;\mathrm{false}\right)$

$Q,\mathrm{rp},d≔\left[\begin{array}{ccc}1& 2& 3\end{array}\right],\left[1\&comma;4\&comma;5\right],3$

$U≔U\left[1..n,1..n\right]\&colon;$

$\mathrm{Fill}\left(p\&comma;0\&comma;U\&comma;1..-1\&comma;r+1..n\right)\&colon;$

$$\begin{gathered} \mathbf{for}i\mathbf{from}r+1\mathbf{to}n\mathbf{do} \\ U\left[i,i\right]≔1 \\ \mathbf{end}\mathbf{do}\&colon; \end{gathered}$$

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

$R≔\mathrm{Multiply}\left(p\&comma;U\&comma;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]$

$R\left[1..r,\mathrm{rp}\right]$

$\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$

$d=\mathrm{Determinant}\left(p\&comma;A\left[1..r,\mathrm{rp}\right]\right)$

$3=3$