The RowReduce function performs in-place Gauss elimination on the input mod p Matrix A. If redflag=false, it produces a row echelon form. If redflag=true, it produces a reduced row echelon form.

Generally, it is required that p be a prime, as inverses are needed, but in some cases it is possible to obtain row echelon form when p is composite. For the cases where row echelon form cannot be obtained for p composite, the function returns an error indicating that the algorithm failed because p is composite.

RowReduce can act on a sub-Matrix or augmented Matrix based on the values of rows, cols, and rcol. The parameters rows and cols can be integer values, or nonempty ranges with integer endpoints, which represent the total rows and columns (including any augmented columns) on which the row reduction should be performed.  If specified as integer values, the range is assumed to start at 1.

For a standard $nxm$ Matrix, augmented with two columns, specify $\mathrm{rows}=n$, $\mathrm{cols}=m+2$, and $\mathrm{rcol}=m$. For a partially reduced $nxn$ Matrix with one augmented column, where the first $r$ rows have leading identity, the reduction of the remaining rows can be accomplished by specifying $\mathrm{rows}=r..n$, $\mathrm{cols}=r..n+1$, and $\mathrm{rcol}=n-r+1$.

If the determinant of the Matrix being reduced is required, specify det as a name. Otherwise, specify det as the value 0. On output, the name specified for det is assigned the value of the determinant. If the input Matrix has more variable columns than rows, the determinant is computed from the square Matrix formed by removing the extra columns from the end of the Matrix. If the input Matrix has fewer variable columns than rows, an error is produced.

Note: If the determinant is not required, set det to zero to avoid unnecessary calculations.

The pseudo-determinant of a Matrix is the determinant of the Matrix formed by removing any dependent rows and parametric columns (up to sign). In cases where the input ( $nxm$ ) Matrix is of full rank with respect to the first $nxn$ submatrix, the determinant and pseudo-determinant are the same. Use this value for reconstruction of solutions of integer linear systems that are rank deficient or underdetermined.

If the pseudo-determinant of the Matrix being reduced is required, specify pdet as a name. Otherwise, specify pdet as the value 0. On output, the name specified for pdet is assigned the value of the pseudo-determinant. If the input Matrix has fewer variable columns than rows, an error is produced.

Note: If the pseudo-determinant is not required, set pdet to zero to avoid unnecessary calculations.

The signature of a Matrix is an integer checksum that represents the correspondence of the solving columns and corresponding rows in the row echelon or reduced row echelon form of a Matrix. If for two Matrices, the pattern of pivots (location of the leading 1 entries in each row) is the same, their signature is also the same. However, two signatures being equal does not necessarily mean the two Matrices have the same pattern of pivots. Use this value is rapidly detect bad homomorphisms for reconstruction of the solution of an integer linear system.

If the signature of the Matrix being reduced is required, specify sig as a name. Otherwise, specify sig as the value 0. On output, the name specified for sig is assigned the value of the signature.

If the rank of the Matrix being reduced is required, specify rank as a name. Otherwise, specify rank as the value 0. On output, the name specified for rank is assigned the rank of the Matrix.

Specifying incrow as a name accomplishes two things. Firstly, it indicates that the algorithm continues computation even if inconsistent rows are found, placing those rows immediately after the consistent rows in the Matrix upon completion. Secondly, it indicates that the algorithm assigns the number of inconsistent rows found to incrow upon completion. If you specify incrow=0, the algorithm halts with an error when inconsistent rows are found.

The redflag parameter controls whether the output should be a reduced row echelon form (true) or a standard row echelon form with no back-substitution (false). In addition to these all-or-nothing settings, one can specify that the first $i$ rows of a matrix should have back-substitution performed on them if redflag is set to $-i$.

This command is part of the LinearAlgebra[Modular] package, so it can be used in the form RowReduce(..) only after executing the command with(LinearAlgebra[Modular]).  However, it can always be used in the form LinearAlgebra[Modular][RowReduce](..).

$\mathrm{with}\left(\mathrm{LinearAlgebra}\left[\mathrm{Modular}\right]\right)\:$

$p≔2741$

$p≔2741$

$A≔\mathrm{Mod}\left(p\,\mathrm{Matrix}\left(4\,5\,\left(i\,j\right)\mapsto \mathrm{rand}\left(\right)\right)\,\mathrm{integer}\left[\right]\right)$

$A≔\left[\begin{array}{ccccc}2543& 1568& 127& 356& 581\\ 430& 1549& 2376& 1511& 1839\\ 164& 1946& 211& 49& 2418\\ 30& 1480& 754& 1049& 423\end{array}\right]$

$B≔\mathrm{Copy}\left(p\,A\right)\:$

$\mathrm{RowReduce}\left(p\,B\,4\,5\,4\,'\det '\,0\,'\mathrm{rank}'\,0\,0\,\mathrm{true}\right)\:$

$B,\mathrm{rank}$

$\left[\begin{array}{ccccc}1& 0& 0& 0& 1916\\ 0& 1& 0& 0& 659\\ 0& 0& 1& 0& 181\\ 0& 0& 0& 1& 25\end{array}\right],4$

$\det$

$82$

$\mathrm{modp}\left(\mathrm{LinearAlgebra}:-\mathrm{Determinant}\left(\mathrm{Matrix}\left(A\left[1..4,1..4\right]\,\mathrm{datatype}=\mathrm{integer}\right)\right)\,p\right)$

$82$

$\mathrm{Multiply}\left(p\,A\,1..4\,1..4\,B\,1..4\,5\right),\mathrm{Copy}\left(p\,A\,1..4\,5\right)$

$\left[\begin{array}{c}581\\ 1839\\ 2418\\ 423\end{array}\right],\left[\begin{array}{c}581\\ 1839\\ 2418\\ 423\end{array}\right]$

$A≔\mathrm{Mod}\left(p\,\mathrm{Matrix}\left(4\,5\,\left(i\,j\right)\mapsto \mathrm{rand}\left(\right)\right)\,\mathrm{float}\left[8\right]\right)$

$A≔\left[\begin{array}{ccccc}1980.& 2533.& 1439.& 67.& 2051.\\ 2635.& 353.& 2657.& 1617.& 2198.\\ 2587.& 1857.& 827.& 1848.& 2338.\\ 1720.& 1181.& 493.& 1731.& 2264.\end{array}\right]$

$B≔\mathrm{Copy}\left(p\,A\right)\:$

$\mathrm{RowReduce}\left(p\,B\,1..2\,5\,4\,'\mathrm{det1}'\,0\,0\,0\,0\,\mathrm{true}\right)\:$

$B$

$\left[\begin{array}{ccccc}1.& 0.& 732.& 2653.& 1849.\\ 0.& 1.& 1097.& 941.& 1501.\\ 2587.& 1857.& 827.& 1848.& 2338.\\ 1720.& 1181.& 493.& 1731.& 2264.\end{array}\right]$

$$\begin{gathered} \mathbf{for}i\mathbf{to}2\mathbf{do} \\ \mathbf{for}j\mathbf{to}2\mathbf{do} \\ \mathrm{AddMultiple}\left(p\,p-B\left[2+i,j\right]\,B\,2+i\,B\,j\,B\,2+i\right) \\ \mathbf{end}\mathbf{do} \\ \mathbf{end}\mathbf{do}\: \end{gathered}$$$B$

$\left[\begin{array}{ccccc}1.& 0.& 732.& 2653.& 1849.\\ 0.& 1.& 1097.& 941.& 1501.\\ 0.& 0.& 608.& 581.& 2260.\\ 0.& 0.& 508.& 1120.& 2290.\end{array}\right]$

$\mathrm{RowReduce}\left(p\,B\,3..4\,3..5\,2\,'\mathrm{det2}'\,0\,0\,0\,0\,\mathrm{true}\right)\:$

$B$

$\left[\begin{array}{ccccc}1.& 0.& 732.& 2653.& 1849.\\ 0.& 1.& 1097.& 941.& 1501.\\ 0.& 0.& 1.& 0.& 2413.\\ 0.& 0.& 0.& 1.& 1536.\end{array}\right]$

$$\begin{gathered} \mathbf{for}i\mathbf{to}2\mathbf{do} \\ \mathbf{for}j\mathbf{to}2\mathbf{do} \\ \mathrm{AddMultiple}\left(p\,p-B\left[i,2+j\right]\,B\,i\,3..5\,B\,j+2\,3\,B\,i\,3\right) \\ \mathbf{end}\mathbf{do} \\ \mathbf{end}\mathbf{do}\: \end{gathered}$$$B$

$\left[\begin{array}{ccccc}1.& 0.& 0.& 0.& 1596.\\ 0.& 1.& 0.& 0.& 1377.\\ 0.& 0.& 1.& 0.& 2413.\\ 0.& 0.& 0.& 1.& 1536.\end{array}\right]$

$\mathrm{modp}\left(\mathrm{round}\left(\mathrm{det1}\mathrm{det2}\right)\,p\right)$

$2603$

$\mathrm{modp}\left(\mathrm{LinearAlgebra}:-\mathrm{Determinant}\left(\mathrm{Matrix}\left(4\,4\,\left(i\,j\right)\mapsto \mathrm{round}\left(A\left[i,j\right]\right)\,\mathrm{datatype}=\mathrm{integer}\right)\right)\,p\right)$

$2603$

$\mathrm{Multiply}\left(p\,A\,1..4\,1..4\,B\,1..4\,5\right),\mathrm{Copy}\left(p\,A\,1..4\,5\right)$

$\left[\begin{array}{c}2051.\\ 2198.\\ 2338.\\ 2264.\end{array}\right],\left[\begin{array}{c}2051.\\ 2198.\\ 2338.\\ 2264.\end{array}\right]$

$p≔65521$

$p≔65521$

$M≔\mathrm{Create}\left(p\,4\,5\,'\mathrm{random}'\,\mathrm{integer}\left[\right]\right)$

$M≔\left[\begin{array}{ccccc}37606& 6440& 30791& 17866& 45834\\ 55381& 6159& 7233& 13465& 42145\\ 60796& 36696& 65135& 63713& 52874\\ 49338& 50505& 50237& 6211& 46483\end{array}\right]$

$\mathrm{RowReduce}\left(p\,M\,4\,5\,4\,0\,0\,0\,0\,0\,-1\right)\:$

$M$

$\left[\begin{array}{ccccc}1& 0& 0& 0& 17540\\ 0& 1& 45645& 14195& 36912\\ 0& 0& 1& 64728& 52075\\ 0& 0& 0& 1& 41141\end{array}\right]$