# Nullspaces and Solutions of Systems

The following functions compute nullspaces of matrices (solving equations of the form $V\cdot A=0$), or solve systems of the form $V\cdot 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 ${\mathbb{Z}}$ and ${\mathbb{Q}}$, and also algorithms which take advantage of sparsity if it is present.

## `Nullspace(A): Mtrx -> ModTupRng`

## `Kernel(A): Mtrx -> ModTupRng, Map`

Given an $m \times 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\cdot 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.

## `NullspaceMatrix(A): Mtrx -> ModTupRng`

## `KernelMatrix(A): Mtrx -> ModTupRng`

Given an $m \times 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\cdot 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.

## `NullspaceOfTranspose(A): Mtrx -> ModTupRng`

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.

## `IsConsistent(A, W): Mtrx, Mtrx -> BoolElt, Mtrx, ModTupRng`

Given an $m \times n$ matrix $A$ over a ring $R$, and a vector $W$ of length $n$ over $R$ or a $r \times n$ matrix $W$ over $R$, return `true` iff and only if the system of linear equations $V\cdot A = W$ is consistent. If the system is consistent, then the function will also return:

**(a)**
A particular solution $V$ so that $V\cdot 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.

## `IsConsistent(A, Q): Mtrx, [ ModTupRng ] -> BoolElt, [ ModTupRngElt ], ModTupRng`

Given an $m \times 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\in N$ for all $i$.

## `Solution(A, W): ModMatRngElt, ModTupRng -> ModTupRngElt, ModTupRng`

Given an $m \times n$ matrix $A$ over a ring $R$, and a vector $W$ of length $n$ over $R$ or a $r \times n$ matrix $W$ over $R$, solve the system of linear equations $V\cdot A = W$ and return:

**(a)**
A particular solution $V$ so that $V\cdot 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.

## `Solution(A, Q): ModMatRngElt, [ ModTupRng ] -> [ ModTupRngElt ], ModTupRng`

Given an $m \times 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\in N$ for all $i$. If there is no solution, an error results.

## `Example: Nullspace (ex-a44c79)`

We compute the nullspace of a $301\times 300$ matrix over ${\mathbb{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.

```magma
> 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 }

```

## `Example: Solution (ex-83882a)`

We show how one can enumerate all solutions to the system $V\cdot 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.

```magma
> 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 ]

```