compute Basis and Nullspace of vectors stored in the rows of a mod m Matrix
MatBasis(m, A, nrow, nullflag)
mod m Matrix
number of rows containing Vectors on input
boolean; indicates whether nullspace
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](..).
An example of a three dimensional basis and a two dimensional nullspace.
p := 2741;
A := Mod(p,Matrix(5,5,(i,j)->rand()),integer):
r := MatBasis(p,A,3,true):
In the previous example, the first r rows are the basis of the input vectors, and the remaining rows are the basis of the nullspace. Check that these are orthogonal.
Construct an example with a known 2-D nullspace.
A := Mod(p,Matrix(5,5,(i,j)->rand()),float):
for i to 5 do
A[i,4] := modp(trunc(p-A[i,1]),p);
A[i,5] := modp(2*trunc(p-A[i,3]),p);
Obtain the basis and nullspace.
r := MatBasis(p,A,5,true):
Download Help Document
What kind of issue would you like to report? (Optional)