The following functions compute nullspaces of matrices (solving equations of the form V.A=0), or solve systems of the form V.A=W, for given A and W.
Magma possesses a very rich suite of internal algorithms for computing nullspaces of matrices efficiently, including a fast p-adic algorithm for matrices over Z and Q, and also algorithms which take advantage of sparsity if it is present.
Given an m x n matrix A over a ring R, return the nullspace of A (or the kernel of A, considered as a linear transformation or map), which is the R-space consisting of all vectors v of length m such that v.A = 0. If the parent of A is an R-matrix space, then the result will be the appropriate submodule of the domain of A. The function Kernel(A) also returns the inclusion map from the kernel into the domain of A, to be consistent with other forms of the Kernel function.
Given an m x n matrix A over a ring R, return a basis matrix of the nullspace of A. This is a matrix N having m columns and the maximal number of independent rows subject to the condition that N.A = 0. This function has the advantage that the nullspace is not returned as a R-space, so echelonization of the resulting nullspace may be avoided.
This function is equivalent to Nullspace(Transpose(A)), but may be more efficient in space for large matrices, since the transpose may not have to be explicitly constructed to compute the nullspace.
Given an m x n matrix A over a ring R, and a vector W of length n over R or a r x n matrix W over R, return true iff and only if the system of linear equations V.A = W is consistent. If the system is consistent, then the function will also return:
- (a)
- A particular solution V so that V.A = W;
- (b)
- The nullspace N of A so that adding any elements of N to any rows of V will yield other solutions to the system.
Given an m x n matrix A over a ring R, and a sequence Q of vectors of length n over R, return true if and only if the system of linear equations V[i] * A = Q[i] for all i is consistent. If the system is consistent, then the function will also return:
- (a)
- A particular solution sequence V;
- (b)
- The nullspace N of A so that (V[i] + u) * A = Q[i] for u∈N for all i.
Given an m x n matrix A over a ring R, and a vector W of length n over R or a r x n matrix W over R, solve the system of linear equations V.A = W and return:If there is no solution, an error results.
- (a)
- A particular solution V so that V.A = W;
- (b)
- The nullspace N of A so that adding any elements of N to any rows of V will yield other solutions to the system.
Given an m x n matrix A over a ring R, and a sequence Q of vectors of length n over R, solve the system of linear equations V[i] * A = Q[i] for each i and return:If there is no solution, an error results.
- (a)
- A particular solution sequence V;
- (b)
- The nullspace N of A so that (V[i] + u) * A = Q[i] for u∈N for all i.
> m := 301; n := 300;
> X := Matrix(n, [Random(0, 10): i in [1 .. m*n]]);
> time N := NullspaceMatrix(X);
Time: 9.519
> Nrows(N), Ncols(N);
1 301
> time IsZero(N*X);
true
Time: 0.429
> {#Sprint(N[1,i]): i in [1..301]};
{ 452, 455, 456, 457, 458 }
> K := GF(3);
> X := Matrix(K, 4, 3, [1,2,1, 2,2,2, 1,1,1, 1,0,1]);
> X;
[1 2 1]
[2 2 2]
[1 1 1]
[1 0 1]
> W := Vector(K, [0,1,0]);
> V, N := Solution(X, W);
> V;
(1 1 0 0)
> N;
Vector space of degree 4, dimension 2 over GF(3)
Echelonized basis:
(1 0 1 1)
(0 1 1 0)
> [V + U: U in N];
[
(1 1 0 0),
(2 1 1 1),
(0 1 2 2),
(0 2 0 2),
(1 2 1 0),
(2 2 2 1),
(2 0 0 1),
(0 0 1 2),
(1 0 2 0)
]
> [(V + U)*X eq W: U in N];
[ true, true, true, true, true, true, true, true, true ]