---
title: "Nullspaces and Solutions of Systems"
canonical: "https://docs.magma-maths.org/v2.30-1/MatricesLinearAlgebra/Matrices/solution-equation.html"
source: "https://docs.magma-maths.org/v2.30-1/MatricesLinearAlgebra/Matrices/solution-equation.md"
part: "Matrices and Linear Algebra"
chapter: "Matrices"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Matrices and Linear Algebra", "source": "https://docs.magma-maths.org/v2.30-1/MatricesLinearAlgebra/index-matrices-linear-algebra.md"}
  - {"title": "Matrices", "source": "https://docs.magma-maths.org/v2.30-1/MatricesLinearAlgebra/Matrices/index-matrices.md"}
prev: {"title": "Elementary Arithmetic", "source": "https://docs.magma-maths.org/v2.30-1/MatricesLinearAlgebra/Matrices/arithmetic.md"}
next: {"title": "Predicates", "source": "https://docs.magma-maths.org/v2.30-1/MatricesLinearAlgebra/Matrices/predicates.md"}
intrinsics:
  - {"name": "Nullspace", "signature": "Nullspace(A): Mtrx -> ModTupRng"}
  - {"name": "Kernel", "signature": "Kernel(A): Mtrx -> ModTupRng, Map"}
  - {"name": "NullspaceMatrix", "signature": "NullspaceMatrix(A): Mtrx -> ModTupRng"}
  - {"name": "KernelMatrix", "signature": "KernelMatrix(A): Mtrx -> ModTupRng"}
  - {"name": "NullspaceOfTranspose", "signature": "NullspaceOfTranspose(A): Mtrx -> ModTupRng"}
  - {"name": "IsConsistent", "signature": "IsConsistent(A, W): Mtrx, Mtrx -> BoolElt, Mtrx, ModTupRng"}
  - {"name": "IsConsistent", "signature": "IsConsistent(A, Q): Mtrx, [ ModTupRng ] -> BoolElt, [ ModTupRngElt ], ModTupRng"}
  - {"name": "Solution", "signature": "Solution(A, W): ModMatRngElt, ModTupRng -> ModTupRngElt, ModTupRng"}
  - {"name": "Solution", "signature": "Solution(A, Q): ModMatRngElt, [ ModTupRng ] -> [ ModTupRngElt ], ModTupRng"}
examples:
  - "ex-a44c79"
  - "ex-83882a"
---

# 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.

<a id="function-nullspace-mtrx"></a>
## `Nullspace(A): Mtrx -> ModTupRng`

<a id="function-kernel-mtrx"></a>
## `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.

<a id="function-nullspacematrix-mtrx"></a>
## `NullspaceMatrix(A): Mtrx -> ModTupRng`

<a id="function-kernelmatrix-mtrx"></a>
## `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.

<a id="function-nullspaceoftranspose-mtrx"></a>
## `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.

<a id="function-isconsistent-mtrx-mtrx"></a>
## `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.

<a id="function-isconsistent-mtrx-modtuprng"></a>
## `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$.

<a id="function-solution-modmatrngelt-modtuprng"></a>
## `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.

<a id="function-solution-modmatrngelt-modtuprng-2"></a>
## `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.

<a id="example-ex-a44c79"></a>
## `Example: Nullspace of a Random Integer Matrix (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 }
```

<a id="example-ex-83882a"></a>
## `Example: Enumerating All Solutions of a System (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 ]
```
