# Non-trivial Properties

The following functions compute non-trivial properties of sparse matrices.

## Nullspace and Rowspace

The following functions compute nullspaces (solving equations of the form $V\cdot A=0$) or rowspaces of sparse matrices.

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

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

Given an $m \times n$ sparse 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$. Since the result will be given in the dense representation, both the nullity of $A$ and the number of rows of $A$ must both be reasonably small.

The algorithm first performs sparse elimination using Markowitz pivoting ([[Duff *et al.*, 1984](../../references.md#cite-smatbook), Sec. 9.2]) to obtain a smaller dense matrix, then the nullspace algorithm for dense-representation matrices is applied to this matrix.

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

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

Given an $m \times n$ sparse matrix $A$ over a ring $R$, return a (dense-representation) 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): MtrxSprs -> ModTupRng`

This function is equivalent to `Nullspace(Transpose(A))`, but will be more efficient in space for large matrices, since the transpose may not have to be explicitly constructed to compute the nullspace.

### `Rowspace(A): MtrxSprs -> ModTupRng`

Given an $m \times n$ sparse matrix $A$ over a ring $R$, return the rowspace of $A$, which is the $R$-space generated by the rows of $A$. Since the result will be given in the dense representation, the rank and the number of columns of $A$ must both be reasonably small.

## Rank

### `Rank(A): MtrxSprs -> RngIntElt`

Given an $m \times n$ sparse matrix $A$ over a ring $R$, return the rank of $A$. The algorithm first performs sparse elimination using Markowitz pivoting ([[Duff *et al.*, 1984](../../references.md#cite-smatbook), Sec. 9.2]) to obtain a smaller dense matrix, then the rank algorithm for dense-representation matrices is applied to this matrix.