The MatBasis function computes a basis of the set of vectors in the first nrow rows of A. Optionally, a basis for the nullspace can also be computed. On successful completion, the number of rows in A containing vectors (labeled r) is returned (the dimension of the basis).

Computation of the basis does not require that m be a prime, but computation of the nullspace does. In some cases, it is possible to compute the nullspace with m composite. If this is not possible, the function returns an error indicating that the algorithm failed because m is composite.

To request a nullspace, set nullflag=true. If the nullspace is requested, the input Matrix must have at least as many rows as columns, and the basis of the nullspace is specified in the trailing $n-r+1..n$ rows of the Matrix, where $n$ is the number of columns, and $r$ is the return value (the dimension of the basis for the input vectors).

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

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

$p≔2741$

$p≔2741$

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

$\mathrm{Fill}\left(p\,A\,4..5\right)\:$

$A$

$\left[\begin{array}{ccccc}2543& 1568& 127& 356& 581\\ 430& 1549& 2376& 1511& 1839\\ 164& 1946& 211& 49& 2418\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}\right]$

$r≔\mathrm{MatBasis}\left(p\,A\,3\,\mathrm{true}\right)\:$

$A,r$

$\left[\begin{array}{ccccc}1& 0& 0& 1972& 1878\\ 0& 1& 0& 1578& 1735\\ 0& 0& 1& 1724& 2166\\ 769& 1163& 1017& 1& 0\\ 863& 1006& 575& 0& 1\end{array}\right],3$

$\mathrm{Multiply}\left(p\,A\,1..r\,A\,r+1..5\,'\mathrm{transpose}'\right)$

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

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

$$\begin{gathered} \mathbf{for}i\mathbf{to}5\mathbf{do} \\ A\left[i,4\right]≔\mathrm{modp}\left(\mathrm{trunc}\left(p-A\left[i,1\right]\right)\,p\right); \\ A\left[i,5\right]≔\mathrm{modp}\left(2\mathrm{trunc}\left(p-A\left[i,3\right]\right)\,p\right) \\ \mathbf{end}\mathbf{do}\: \end{gathered}$$$A$

$\left[\begin{array}{ccccc}2635.& 353.& 2657.& 106.& 168.\\ 2587.& 1857.& 827.& 154.& 1087.\\ 1720.& 1181.& 493.& 1021.& 1755.\\ 2209.& 884.& 1207.& 532.& 327.\\ 26.& 2325.& 518.& 2715.& 1705.\end{array}\right]$

$r≔\mathrm{MatBasis}\left(p\,A\,5\,\mathrm{true}\right)\:$

$A,r$

$\left[\begin{array}{ccccc}1.& 0.& 0.& 2740.& 0.\\ 0.& 1.& 0.& 0.& 0.\\ 0.& 0.& 1.& 0.& 2739.\\ 1.& 0.& 0.& 1.& 0.\\ 0.& 0.& 2.& 0.& 1.\end{array}\right],3$

$\mathrm{Multiply}\left(p\,A\,1..r\,A\,r+1..5\,'\mathrm{transpose}'\right)$

$\left[\begin{array}{cc}0.& 0.\\ 0.& 0.\\ 0.& 0.\end{array}\right]$