LinearAlgebra[Modular]
MatBasis
compute Basis and Nullspace of vectors stored in the rows of a mod m Matrix
Calling Sequence
Parameters
Description
Examples
MatBasis(m, A, nrow, nullflag)
m
-
modulus
A
mod m Matrix
nrow
number of rows containing Vectors on input
nullflag
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.
with(LinearAlgebra[Modular]):
p := 2741;
p≔2741
A := Mod(p,Matrix(5,5,(i,j)->rand()),integer[]):
Fill(p,A,4..5):
A;
25431568127356581430154923761511183916419462114924180000000000
r := MatBasis(p,A,3,true):
A,r;
1001972187801015781735001172421667691163101710863100657501,3
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.
Multiply(p,A,1..r,A,r+1..5,'transpose');
000000
Construct an example with a known 2-D nullspace.
A := Mod(p,Matrix(5,5,(i,j)->rand()),float[8]):
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); end do: A;
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.
Obtain the basis and nullspace.
r := MatBasis(p,A,5,true):
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.,3
Check orthogonality.
0.0.0.0.0.0.
See Also
LinearAlgebra/Details
LinearAlgebra[Modular][Fill]
LinearAlgebra[Modular][Mod]
LinearAlgebra[Modular][Multiply]
Download Help Document
What kind of issue would you like to report? (Optional)