Skip to content

Add a typed fmpq_mat_nullspace API #2796

Description

@edgarcosta

Summary

fmpq_mat provides RREF and solving functions but no direct nullspace function. Typed nullspace functions exist for fmpz_mat and nmod_mat, and the generic matrix layer provides gr_mat_nullspace.

This was an explicit item in TODO.md, noticed while removing that file in #2795.

This is an API parity and convenience issue, not a claim that the mathematical operation is unavailable: callers can use the generic matrix layer or construct a basis from RREF today.

API decision

Before implementation, choose, and document the output convention. Two existing conventions are plausible:

  • Match fmpz_mat_nullspace and nmod_mat_nullspace: return the nullity and write basis vectors into the first nullity columns of a preallocated matrix.
  • Match gr_mat_nullspace: resize or initialize the result as an n x nullity matrix whose columns form a basis.

The typed API should follow the convention that maintainers want to support consistently. The issue does not require a particular spelling or signature before that decision is made.

Possible implementation routes

  • Clear row denominators, compute an integer nullspace with fmpz_mat_nullspace, and convert the basis to fmpq_mat. Nonzero row scaling preserves the right nullspace over Q.
  • Build the basis from fmpq_mat_rref.
  • Wrap or share code with gr_mat_nullspace over the rational context.

These should be compared for code reuse, output normalization, and performance rather than selecting one by assumption.

Tests

For an m x n input matrix A and returned basis matrix X:

  • Check A * X = 0.
  • Check rank(X) = nullity.
  • Check rank(A) + nullity = n.
  • Cover zero, full-column-rank, rank-deficient, square, tall, and wide matrices.
  • Cover zero-dimensional matrices according to the selected output convention.
  • Include entries with nontrivial and nonuniform denominators.
  • Check that the input is unchanged and that the result is canonical.
  • Do not require a particular basis unless the API explicitly promises one.

Documentation

Document:

  • whether basis vectors are rows or columns;
  • result dimensions and allocation requirements;
  • the return value or status convention;
  • behavior in nullity zero and zero-dimensional cases;
  • whether any normalization of basis vectors is guaranteed.

Acceptance criteria

  • A public typed API is declared and documented in fmpq_mat.h and the manual.
  • Tests verify the nullspace identities above across randomized and edge-case inputs.
  • The output convention is consistent with the chosen FLINT matrix API style.

Refs: #2795

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions