|
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.
Kernel(A) : Mtrx -> ModTupRng, Map
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.
KernelMatrix(A) : Mtrx -> ModTupRng
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:
- (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.
If there is no solution, an error results.
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:
- (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.
If there is no solution, an error results.
We compute the nullspace of a 301 x 300 matrix over Z
with random entries in the range [0 .. 10]. The nullity
is 1 and the entries of the non-zero null vector are integers,
each having about 455 decimal digits.
> 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 }
We show how one can enumerate all solutions to the system V.X=W
for a given matrix X and vector W over a finite field.
The Solution function gives a particular solution for V,
and then adding this to every element in the nullspace N of X,
we obtain all solutions.
> 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 ]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|